Codeforces過去問解き。A,B,Cは簡単。D,EはうまくやらないとTime limit exceededになってしまうので工夫が必要。なにをやればいいかわからないということにはならない問題セット。でもD,Eは解けなかった…。問題はこちら。

A: Vanya and Cubes

n 個のキューブが与えられる。1段目は1個、2段目は1+2個、…、という風にピラミッドを組んでいったとき最大何段目まで組めるか答える問題。

n = int(raw_input())
ans = 0
for h in range(1,100000):
    need = h*(h+1)/2
    if n >= need:
        n -= need
        ans += 1
    if n <= 0: break
print ans

B: Vanya and Lanterns

区間 [0,l] の長さの通りに街灯がいくつか並んでいる。街灯は半径 d を照らすことができるとするとき、通り全体を照らすのに最低限必要なdを答える問題。

街灯が位置 0 と l にない場合を忘れないように注意。また n=1 のときはsplit()を使えないのでこれも注意が必要。

n,l = map(int,raw_input().split())
if n > 1:
    a = sorted(map(int,raw_input().split()))
    d = max(aj-ai for ai,aj in zip(a[:-1],a[1:]))/2.0
    if a[0] != 0: d = max(d,a[0])
    if a[-1]!= l: d = max(d,l-a[-1])
else:
    a = int(raw_input())
    d = max(a,l-a)
print d

C: Vanya and Exams

n 個の単位とそのグレード、グレードを1ポイントあげるのに必要なエッセイ数が与えられる。グレードの上限値をrとしたとき、グレードの平均値が avg 以上になるのに書く必要があるエッセイ数を答えよという問題。平均値は必ず avg を越えられるという条件です。

まず単位情報を必要なエッセイ数の小さい順にソートして、はじめの方からグレード上限に達するまでエッセイを書き、平均値が avg 以上になったら終了という方針でOK。

n,r,avg = map(int,raw_input().split())
need = n*avg
ab = [map(int,raw_input().split()) for _ in range(n)]
ab = sorted(ab,key = lambda x:x[1])
now = sum(a for a,b in ab)
ans = 0
for a,b in ab:
    if now >= need: break
    ans += min(need-now,r-a)*b
    now += min(need-now,r-a)
print ans

D: Vanya and Computer Game

2人のプレイヤーがそれぞれ 1/x 秒, 1/y 秒ごとに体力aの敵モンスターに1ずつダメージを与えるとき、最期に攻撃するのはどちらのプレイヤーであるか（もしくは同時か）を答える問題。Both は2回続くことに注意が必要。

モンスター数 n の上限10⁵、各 a の上限値が10⁹であるから単純に体力を減じていくのは間に合わない。同時に攻撃が起きるまでの攻撃者リストを作成するのがスタンダードだと思います。小数は扱いたくないので、それぞれの攻撃間隔の比をとるといいです。

def gcd(a,b):
    while b: a,b = b,a%b
    return a

n,x,y = map(int,raw_input().split())
g = gcd(x,y)
x,y = y/g,x/g
#攻撃者の時間順リストを作成
at = sorted([x*i for i in range(1,y)]+[y*i for i in range(1,x)])
at = [0 if ele%x == 0 else 1 for ele in at] + [2,2]
l = len(at)
for roop in range(n):
    a = int(raw_input())
    print ["Vanya","Vova","Both"][at[(a-1)%l]]

解答作成途中に気付いたのですが python はつぎのような2つの処理に倍くらい速度の差がありました。処理速度がシビアな時は zip を使った方がよさそうですね。

# [[x,1],[2x,2],…]というリストを作るとき
x = 123456789
R = 1234567
a = [[x*i,1] for i in range(R)]　# 約1.2秒
b = zip([x*i for i in range(R)],range(R)) # 約0.5秒

E: Vanya and Field

n×nのグリッドが与えられる。そのなかの m個の(x[i], y[i])にはりんごの木が植えてある。プレイヤーは任意の点からスタートし、今いる座標から ((x+dx)%N, (y+dy)%N) に移動していく。訪れるりんごの木の本数を最大にするのには、どの点からスタートすればいいか答える問題。なお x と N、y と N はそれぞれ互いに素である。条件から、

N 歩進むとスタート位置に戻る。
全部で N 通りのコースが有る。
１つのコースでは各 x 座標、y 座標を１回ずつ通る。

ことがわかる。n, m はそれぞれ最大10⁶, 10⁵だから、各スタート位置に対して単純に訪れる点を調べていると時間が足りない。各 x 座標を１回ずつ通るから、スタートの x 座標は0としておく。各りんごの木に対して、そこを訪れるのに必要なスタート位置 (0, y) を計算し、y ごとに数え上げを行えば、その最大値が答えとなる。各 x 座標に対してスタートから何歩目であるかを先に求めておき、それを使ってスタート位置の y を求める。

n,m,dx,dy = map(int,raw_input().split())
step = [0]*n
for i in range(n): step[dx*i%n] = i
starty = [0]*n
for roop in range(m):
    x,y = map(int,raw_input().split())
    starty[(y-dy*step[x]%n+n)%n] += 1
print 0,starty.index(max(starty))