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

A. Vanya and Fence

ざっくりと大意

・高さhのフェンスに沿って歩いている。
・それぞれの高さ\(a_i\)で歩く我々は高さhを越えるものは折り曲げさせて高さh以内にさせて2人分の幅を使わせる。
・aのメンバー全員が歩くのに何人分の幅が必要か。

Python2

n,h=map(int,raw_input().split())
a=map(int,raw_input().split())
ans=chk=0
for i in a:
    ans+=1
    if i>h:
        ans+=1
print ans

コンテスト当時は違う謎な計算方法をしていてよくわからず。。\(a_i\)の最大値が2 * hなのでhより大きいときだけもう一人分加算というイメージで処理した。

B. Vanya and Food Processor

ざっくりと大意

・Vanyaは縦型のフードプロセッサでマッシュポテトを作る。
・フープロ内のイモは高さhを超えない、フープロは秒間kセンチのイモを潰す。中のイモがk以下なら全て潰す。
・イモaを順番通りに使って潰し終わるのは何秒後か？？

Python2

n,h,k=map(int,raw_input().split())
l=map(int,raw_input().split())
ans=chk=0
for i in l:
    if chk+i<k:
        chk+=i
    elif chk+i<=h:
        chk+=i
        ans+=chk/k
        chk%=k
    else:
        ans+=chk/k
        chk%=k
        if chk+i>h:
            ans+=1
            chk=i
        else:
            chk+=i
ans+=chk/k
if chk%k:
    ans+=1
print ans

もう少し短く出来る気がするんだが。。。
イモをaの先頭から取り出して、容器内との合計がk未満なら追加だけして次を取り出す。
合計がh未満なら追加してから潰す。追加後の合計とkの商を解に加算して、kとの余りがイモの容器内の残りになる。
合計がhを越えるなら、既に容器内にある量とkの商を解に加算して、kとの余りがイモの容器内の残りになる。その残りと取り出したイモの合計がhを越える(取り出したイモの大きさとhが等しい場合など？)なら解に1加算して容器を空にして取り出したイモを入れる。入れた状態がk以上でも次の取り出しや最終の出力前に処理できるので特に考慮しなかった。

C. Vanya and Label

ざっくりと大意

・0-9はそのまま、A-Z,a-z,-,_ が63まで数に割り当てられている。
・zになる論理積の組合せはz&z, z&_, _&zの3つで、V_Vになる組み合わせはVがV&V, V&_, _&Vの3つで_は_&_のみ合わせると9通りになる。
・文字列sになるような組合せがいくつあるかをmod10⁹+7で出力する。

Python2

mod=1000000007

s=raw_input()
ans=chk=1
d={i:3**i for i in range(7)}
for i in s:
    if i.isdigit():
        t=bin(int(i))[2:]
    elif i.isupper():
        t=bin(ord(i)-55)[2:]
    elif i.islower():
        t=bin(ord(i)-61)[2:]
    else:
        tmp=[62,63]
        t=bin(tmp[i=='_'])[2:]
    chk=t.count('0')+6-len(t)
    ans*=d[chk]
    ans%=mod
print ans

論理積で1になるのは互いに1の時だけである。2進数に置換して1が立っていない桁は0&0, 1&0, 0&1の3通りがあり得る。注意？するのは_の63が111111であるので6桁目まで考慮して計算すること。