2011/10/02(Sun)Google Code Jam Japan 2011 予選 参加記録
2011/10/02 11:49 Google Code Jam 初参加。
10月1日土曜日は13時から19時と。
てっきり6時間張り付いてなきゃいけないのかと思ってたのですが、
実はそうじゃないことは開始直前になって知りました。
ルール把握してから参加しろって感じですね！
朝。
10時ごろむくり。準備何にもしてね。目を覚ますためにシャワー。
事前
とりあえず頭を蟻さんモードに切り替えるべく、ヘッダを羅列したテンプレートを用意する。
練習は素数とか出てたし、エラトステネス作る。バグる。直す。先が思いやられる……。
部分エラトステネス作る。バグる。直す。頭を抱える。
これは largeが事故るパターン来たで……。
せっかくなので bigint とかも用意してみる。BCD書くの久しぶり。
足し算だけできるようになった。
あとは、バッチファイルを用意しておく。
run.bat に、
GCJJ.exe < %1 > %1.out & start notepad %1 & start notepad %1.out
とだけ書く。notepad してるのは、あからさまにおかしい出力、雰囲気の怪しい出力を目で見て気づくチャンスを増やすため。
ICPCでも、これをしてればWAを止められてたはずだ、という幾度かの経験から。
とかやってる間に予選開始15分前。幾何が来たら詰む。
13時。予選開始。
参加するボタンをぽちっ。
問題数は3問。あれ少ない！
A: Hanafuda Shuffleカードシャッフル
問題
簡単に言うと、M枚のカードがあって、上から順に1...Mが書いてあって、ここにC回のカット操作「上からA[1..i..C]番目からB[1..i..C]枚を引き抜き、束の上に乗せる」をした後、上からW番目のカードが何であるか知りたい。ただし、カード枚数は10^9以下。カット回数は100回以下。
所感
Hanafuda Shuffle！？ いきなりの苦手問題出た！
しかもやべぇ、カードの厚みが1枚0.1mm だとしても、厚み100km！
どんなデッキだよｗｗｗｗ
考
と、まぁ、冗談はさておき。アルゴリズムはどーってことない。
カードの束を順番に連なってる「区間」で扱ってのカット操作だけ。区間の分割とかがちとめんどくさいけど、あとはカットするだけだな。というとこまでは、問題読み終わってから10秒、というよりも制約条件*1が教えてくれる。さぁ、問題はそっから。
「やべーlistとかうまく扱う自信ねーわ。spliceとか使ったことあるくらいで覚えてねーわ＞＜；」
実装
結局、イテレータでパニクり「ぇぁー……後回しにしようかー」とかBとかCの問題を読んだりして。
BとCを一通り読んで、やっぱAから確実に解いた方がいいよなと思い直してAに戻る。
またしばらく右往左往した挙げ句に、「よし、わからないものは使わなければいい！」と開き直ってvectorでやることにする。
この時点で30分くらいは無駄にしてる。もったいない。
そっから20分くらいでvectorをごりごりするコードを書き提出。
smallはあっさり通過。よしよし。まずは5点。
そのままlargeも提出。これで18点！かな？ と、
ドキドキしながら、次は解いてる人が多いCへ。
C ビット列
問題
数を2進数で表したときに立ってるビットの数を返す関数を f とする。
f(5) = 2, f(7) = 3, f(8) = 1, f(31) = 5 と言った具合。
Nを与えたときに、a+b=N となるような、非負整数(a, b)の組について、
k = f(A)+f(B) を最大にするものを見つけてそのときの k を答えなさい。
ただし N は 10^18 以下。
所感
でたよ、10^18！ 64bit変数ギリギリ。全探禁止問題！
数値の足し算と立ってるビットの数との間にどんな関係があるというのか……。
考
少し考えてさっぱり解放の糸口が見えなかったので、手作業でいくつか解いてみることにした。
4のとき、5のとき、6のとき、8のとき、10のとき、31のとき。……貪欲？
0が来たらそれは1と1で作った方がおいしい。1が来たらそれはもう1で作るしかない。
んじゃ、全桁繰り上がるように下から貪欲にとっていけばいいのかな。
実装
ってとこで書いてみる。→ テスト「1」で無限ループ！
あぁそうか、最下位ビットが1だったら繰り上がれないわ！
7も111だから、繰り上がれない……！
んじゃ、0であるビットのうち最下位のとこから処理だなぁ。
よし、できた。サンプルも……通った。small通った。
うーん、なんか理論的にいまいち自信ないけど、largeも出してみるかー。ぽちっ。
30分程度。さて最後はBか。
B 最高のコーヒー
問題
ヘインさんは毎朝1杯のコーヒーを飲む。
ヘインさんはN種類(100以下)のコーヒーを持っている。
N種類について、現在の在庫c[1..i..N]杯分、消費期限t[1..i..N]日後、ヘインさんがこのコーヒーを飲んだときの満足度 s[1..i..N]が与えられる。
消費期限が過ぎたコーヒーは飲めない。
ヘインさんはこの中から毎朝コーヒーを選んで飲める。
飲めるコーヒーが存在しないときはその日はコーヒーは飲めない。
K日後の合計満足度の最大を求めなさい！ ただし、Kは10^12以下。
所感
むはー、またでかい数値きた。
ヘインさんとか知らないけど勝手にコーヒー飲んどけよ！
しかもやべぇ、今回は単位が日。ヘインさん27億歳になってるよ！
そういうところに「いかにもプロコン」っぽさを感じてしまう問題だなぁと思った。
考
さて冗談はさておきどうするか。
満足度最大化。シンプレックス法？ 貪欲法？ 動的計画法？
貪欲……はだめだな、消費期限あるし。動的計画法もいまいちピンとこない。
うーん、こういうときは手作業で解いて雰囲気をつかむのがいいんだよ！
これから3日間を2種のコーヒーですごそう。
A 在庫2 消費期限2 満足度1。
B 在庫1 消費期限3 満足度2。
貪欲なら、BAxだからだめ。
っていうか、フツーAのコーヒーから飲むだろ。消費期限早いんだし。
おっと、ちょっと待って、私は今何を考えた？ 消費期限早い順に飲む？ これ？
消費期限が早いものから消費したい、逆に消費期限が残ってるなら残しておきたい。
んじゃ、全部のコーヒーを消費期限ギリギリで飲みたい。
消費期限ギリギリ……日付をひっくり返して、K日後から手前に見てく中で、
飲めるやつのうち一番満足度の高いものを選んでけば、最適解が出るか？
あーうん、これでいけそーな気がするなぁ？
なんか貪欲っぽい。google貪欲だな！
しかもKがでかいからまた区間か……。
K日後から手前方向に見てく。
今飲んでるコーヒーの在庫を消費しきるか、他のコーヒーの消費期限が来るかで、
ともかく飲めるコーヒーの種類が変わる次の瞬間を調べる。
そこまでは毎日同じコーヒーを飲むことにしよう。
うわわ、めんどくさ。
まぁ、書くか。
実装
ごりごり書く。
というわけで、コーディング時間が約30分、C提出から約1時間後、Bも提出。
ふぅ。
個人的には開始から2時間半で全部の提出が終わって、スコアボードなどをぱらぱら眺める。
twitterでよく絡んでた人とかのスコアも眺めつつ。
ああ、こっから自分の提出見られるのか。
変なソースコード提出してねーよなぁ。
まぁ、出してたとこで後の祭りだけど。
一応見とくかー。と、おさらい。
Aのコード眺める。眺めるうちに何か違和感。
おや……。おやおやおや。
あれここバグってるような……。うん、バグってるバグってる。large落ちたか……。ひとまず、自己チャレンジしてみよう。チャレンジ失敗！ あれ、なんか知らんけどちゃんと動く？ え、なんで動く？ げげ、うわ……。←今ここ
2つのバグが互いをうまくカバーし合っているという奇跡の図。
以降、30分くらい一人チャレンジフェーズしてたんですが、落とせず。
まぁ、明らかにまずいんで、うっかりテスト通っても個人的には不正解扱い。
方針が迷走したコードはバグを孕みやすいんですよねー。３倍気をつけないと……。
うーん。large通ってれば儲けもんかぁ。まぁ、落ちてもしゃーなし。間違ってるし。
あな悔し。
BとCは、提出時にファイルを間違えてないことだけ確認して終了。
飲み会の予定が入ってたので出かける。
終了後
当日は飲み会の予定が入っていたので出先から結果を確認。
暫定49位だったのが、案の定A-largeは落ちて41点172位。
ほんとは、A-smallも間違ったコードでうっかりテスト通っちゃっただけなので、36点の275位がより妥当な順位かなと思います。
問題のレベルとしては僕でも全完できるレベルだったのでちと悔しいです。
こういうしょーもないところで焦ってミスをしないようにしたい。
予選全体としての印象としては、区間で貪欲って感じになりました。
googleが、日頃とってもでかいデータを扱ってるせいなのかどうかはわかりませんが、
とってもでかいデータをまとめて扱うような問題が2つも出たわけで。
ここ苦手な人にとっては辛かったんじゃないかなぁと思いました。
とまぁ。そんな感じで、予選が終わりまして、来週はいよいよ決勝！
決勝はどんな問題が出るのか今から楽しみではあります。
ぐーぐるくいーんTシャツを目指してがんばらう。
参加者の提出コードはこっから見られるらしいです。
http://code.google.com/codejam/contest/scoreboard?c=889487
172位のttsukiが僕です。smallもlargeも全部同じコードを出してます。
つまり、A-smallは思いっきり間違ってるワケですが、テスト通っちゃったので落とせます。
晒し者みたいでめっちゃ恥ずかちぃ。