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のイメージ。
・問題文を訳すとそういう意味でもないっぽいけど多分大丈夫。
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。
・イモは左から順番にしか使えない??
方針のようなもの
・無駄なループとかしないようにする。
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で割った余りを出力。
方針のようなもの
・そうだ、埋込しよう!!と思ったけど別に埋込は関係なかった。
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倍ずつ増えていく。