Codeforces Round #355 (Div.2) 参加記

はい。 ox---(0/0)
コンテスト中はB問題がTLE解決できず、C以降はさっさと諦らめ。。だが翌朝に考えなおしてみればB,C両方できるチャンスあったと思う。。
http://codeforces.com/contest/677

A. Vanya and Fence

ざっくりと大意

・n個のグループがある。それぞれ\(a_i\)人いる。一緒に移動できる制限?がh。違うグループは一緒に移動できない??

方針のようなもの

・入力例1が1+1+2=4になるのは、7以内で1回+7以内で1回+7以内になるよう2回に分かれるで4のイメージ。
・問題文を訳すとそういう意味でもないっぽいけど多分大丈夫。

python

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

答えになる数にhで割ったものを足し続ける。hで割って余りがない場合は商をそのまま。h未満かhより大きいで余りが出る場合は余りの分も1追加する。

B. Vanya and Food Processor

ざっくりと大意

・イモを潰す。潰す動作ができる高さ制限はh、h以内なら複数のイモを重ねられる。一度の動作で潰せる大きさはk。
・イモは左から順番にしか使えない??

方針のようなもの

・無駄なループとかしないようにする。

python

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:
        tmp=chk+i
        ans+=tmp/k
        chk=tmp%k
    else:
        ans+=1
        chk=i
        if chk>=k:
            ans+=chk/k
            chk%=k

print ans+1 if chk else ans

現在のイモの高さからkを減算しようとすると無駄になる。イモの高さ/kで潰す回数、イモの高さ%kで残る高さになる。現在のイモと取り出したイモの合わせた高さがhより大きくなる場合には1回潰す動作をしたことにして動作は+1、イモの高さは取り出したもののみとなる。取り出したイモに対してもkで潰す回数と残り大きさが幾つになるか見るのを忘れずに。全てのイモを見終わった、forループを回し終わった時にイモが残っていたら動作を+1する。

C. Vanya and Label

ざっくりと大意

・0-9A-Za-z-らの文字を問題文で割り当てられらた数の通りに使う。
・0から9はそのまま、Aは11でBは12...で、aは36...となっている。
・0から63同士を2つ組み合わせて&論理演算(論理積)をしてzになる組み合わせは何通りか?という時はz&
と_&zとz&zの3通りである。 ・組み合わせを1000000007で割った余りを出力。

方針のようなもの

・そうだ、埋込しよう!!と思ったけど別に埋込は関係なかった。

python

mod=1000000007
s=raw_input()
l=[3**((6-(len(bin(i)[2:])))+bin(i)[2:].count('0')) for i in range(64)]
ans=1
for i in s:
    if i=='-':
        ans*=l[-2]
    elif i=='_':
        ans*=l[-1]
    elif i.isdigit():
        ans*=l[int(i)]
    elif i.isupper():
        ans*=l[ord(i)-55]
    else:
        ans*=l[ord(i)-61]
    ans%=mod
print ans

&は、論理積はbitが共に1の時のみ1になる。0と1、1と0、0と0はいずれも0になる。極端に両端を見ると0は0が6桁で何と&しても必ず0になる。は1が6桁で同士での&でないと別の文字になってしまう。zは35が割り当てられていて6桁のbitで表すと111101である。右から2桁目の0の箇所だけが0&0, 1&0, 0&1が許される。6桁の中に0がある分だけ組み合わせが3通り、3倍ずつ増えていく。