Codeforces Round #340 (Div.2) - 君はまるで砂漠に咲く、一輪の花。

A. Elephant

ざっくりと大意

・位置0から位置xへ移動したい。移動の仕方は1,2,3,4,5のいずれか。最小回数はいくつか？
・サンプル1は0から5へ移動5で1回で移動できる。サンプル2は0から12へ3,5,4で移動して3回必要。

Python2

print (int(raw_input())+4)/5

Noteの説明は別に嘘じゃないのですが混乱するような。。移動に必要な最小回数は5で割って余りがあるなら1繰上げですね。

B. Chocolate

ざっくりと大意

・長さnの数列aでそれぞれの部分が1を1つだけ含むような分け方は何通りあるか？

Python2

n=int(raw_input())
s=''.join(raw_input().split()).lstrip('0').rstrip('0')
chk=[]
ans=tmp=1
for i in s:
    if i=='1':
        ans*=tmp
        tmp=1
    else:
        tmp+=1
if len(s)==0:
    ans=0
print ans

左右両端の0はいらない子。1と1の間にある0のぶんだけ分け方が増える。1を｢1つだけ｣含むなので連続した1 1を分けないというパターンは計算に含めなくて良い。

C. Watering Flowers

ざっくりと大意

・x1,y,1とx2,y,2にある水撒きポイントから1と2の半径の2乗の和が最小になるようにしてn箇所に水を撒く。
・半径の2乗という数を使うために解は整数のみで実数になるケースは発生しない。

Python

#!/usr/bin/env python
# -*- coding: UTF-8 -*-
import time
import sys
import io
import re
import math
import itertools
import collections
#sys.stdin=file('input.txt')
#sys.stdout=file('output.txt','w')
#10**9+7
mod=1000000007
#mod=1777777777
pi=3.141592653589
xy=[(1,0),(-1,0),(0,1),(0,-1)]
bs=[(-1,-1),(-1,1),(1,1),(1,-1)]
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b/gcd(a,b)
#def euclid_dis(x1,y1,x2,y2): return ((x1-x2)**2+(y1-y2)**2)**0.5
def euclid_dis(x1,y1,x2,y2): return ((x1-x2)**2+(y1-y2)**2)
def choco(xa,ya,xb,yb,xc,yc,xd,yd): return 1 if abs((yb-ya)*(yd-yc)+(xb-xa)*(xd-xc))<1.e-10 else 0

#n=int(raw_input())

#    WA!!!!!!

n,x1,y1,x2,y2=map(int,raw_input().split())
a,b,h=0,0,0
l=r=0
memo=[(0,10**8)]
for i in range(n):
    x,y=map(int,raw_input().split())
    a=euclid_dis(x1,y1,x,y)
    b=euclid_dis(x2,y2,x,y)
    l=max(l,a)
    memo.append((a,b))

memo.sort()
ans=l
#print ans,memo
p=range(-1,-n-1,-1)
for i in p:
#    print memo[i],memo[i-1]
    tmp=memo[i-1][0]+max(r,memo[i][1])
    if tmp<=ans:
#        print l,r
        l=memo[i-1][0]
        r=max(r,memo[i][1])
        ans=tmp
print ans

テストケース4でWA。。。あとで考える