Google Code Jam Japan 2011 予選

参加！！！
Tシャツがもらえるらしいのでがんばりたいけど、、、

問題A. カードシャッフル

解けた。

JOI過去問で解いたことあるような気がするけど、シミュレーションする方法しか思いつかなかったので、6時間もあるしまったり愚直に書いた。largeは範囲で考えないと無理。

問題B. 最高のコーヒー

解けた。

なんとなくDPっぽい、、、？
消費期限が長いものは後のほうで使うことができるから、消費期限の長くて満足度の高いものを期間の後ろからいれていくgreedyでよさそう。largeは1日ずつやると間に合わないので、期間を範囲で考える。

問題C. ビット数

解けた。

2進数で1,11,111,1111,...みたいな数字は立っているビット数が多いので、入力されたN以下で最大の2進数が11...11となる数字aを探して、残りをbとしてf(a)+f(b)を計算することを考えてみる。
aのほうの数字のあるビットが1なものをbに移すと、b側の同じビットが0なら個数は変わらないし、1なら1つ繰り上がってそのビットは0で繰り上がりでそのビット以上のところが1になるかもしれないけど、1の数は結局増えない。それでよさそう。
念のため、小さいケースはシミュレーション版と比較して一致するのを確認した。

反省

明らかにだらだらやってしまった。
問題Aは応用が効くので、汎用的に使えるようにしたい。他の人のソースを見たら範囲の扱い方が違っていたり、そもそもシミュレーションの仕方が違っていたので、どうやってるか見直したい。