Google Code Jam Round 1A

Google Code JamのRound 1Aが日本時間で今日の朝10時から12時30分まで行われました．
結果は49点で281位でした．点の割には順位はひどくなかったので驚きです．
とはいえ，あまりにひどい内容で自己嫌悪．

A. Multi-base happiness

ちゃんと読まずに「各桁を2乗して和をとるという操作を何回繰り返せば1になるか」という問題と勘違い
ループに入って止まらない．．．

気を取り直して，とりあえず各ベースについて1からMまでの数がhapinessかどうかの配列を作るという戦略をとる．
これでsmallは通った．
largeもこれでいいやと思ってやってみるもM=10^6ではうまく行かない．
しょうがないのでM=10^7にしてみてもまだ足りない．
M=10^8にしてしまうと今度はメモリが足りない．
ということでTime expired

結局，答えの最大は11814485だったのでM=1.2*10^7としていれば2分ぐらいかかるがいけた．
配列用意しないでその場で計算しても3分ぐらいかかるがいけた．
すぐに解くためには，はじめにベースの組み合わせ2^10通りすべての答えを用意しておくぐらいしか思いつかない．

B. Crossing the Road

最短経路探索．
サイズが小さいのでBellman-Fordで十分そう．
ただし，問題文がややこしくて英語が苦手だとつらい．
あと実装力も必要．
時間切れ．

C. Collecting Cards

クーポンコレクター問題を一般化したもの．

C種類のカードがありbooster packにはそのうちN種類が入っている．どのN種類かは等確率．
全種類のカードを集めるには何回booster packを買う必要があるか期待値を求めよ．

まずは残りi種類集めるときの期待値について漸化式を立てる．

これをについて解いてを使えばが求まる．

ここまでできればあとは簡単なはずだったのに途中にバグが入ってしまい駆除に1時間近く使ってしまう．
答えの精度が悪いのかと思っていろいろいじってみたが，うまくいかず．
原因は不等号の向きが違ったことでサンプルインプットの場合は等号でしか評価されないから偶然あってただけだった．

総括

今回は各subroundで1000人通過できるらしいので順位的には問題ないが，もうすこしいい内容にしたかった．
てか，1000位の人が9点だから合格点は低い．
次は3000人から500人だから，おそらく実力的にはぎりぎりというところなのでミスをしないようにしたい．