Google Code Jam 2010 Qualification Round

なんだか毎年レベルがどんどん上がっていってる気がする。

A. Snapper Chain

• 問題長い。長いのは気にならないけど、GCJの問題はいつも語彙が難しかったり文体が垢抜けていたりして読みにくいという印象がある。
• 1回目の snap で最初の snapper が反転して、
• 2回目の snap で両方の snapper が反転して、
• 3回目の snap で最初の snapper が反転して、電球が付く。
• そんな感じで K 回繰り返す。
• ………どゆこと？
  • 「両方」って、どれを指して言ってるの？
  • いやまぁ、ここでは最初の2つっていうのは読み取れるけど。一般的にどうなの？
    • 「両方」って言うからには「2つあるうちの2つとも」という意味なんだろうけど、そもそも「N = 2 のケースを例に取って説明してますよ」とか書いてないよね
    • 'both' == 'all' だったっけ？
      • ALC先生に聞いてもLongman先生に聞いても違うって言われた。
• ぜんぜんわからん。
• ...
• とりあえず 'both' == 'all' で書いてみよう。それでもsampleは出てくるっぽいので。
• K === 3 mod 4 をチェックすればいいや。カタカタカタカタ。
  • あ、N = 1 は例外扱いしないと。
• できた。submit. Incorrect...
• なるほど、この解釈は間違いなのか....
• ...
• ...で？
• ...他の解釈は？
• ...
• ...あ。
• もしかして、「すべての通電している snapper を反転させる」という意味なのか？
  • それってものすごく規則性がありそうな気がする。手で書いてみよう。
    • 2進数ですね。
• K === 2^N-1 mod 2^N かどうかをチェック。
• 書けた。submit.
• Correct!
• この解釈でよかったんだ...
  • もう一度問題文を読み直す。そんな感じに読める...のかなぁ？
• とりあえずlargeも出そう。
  • 2³⁰とか怖いのでlong longで。
    • 冷静にチェックするよりも何も考えずlong longを選ぶ、それが私のジャスティスです。
• submit.
• scoreboard見てみよう。
  • LayCurse先生は5分足らずでこの問題の意味を把握したのか...。すごすぎる。
  • WAってる人多いなぁ。バグる問題とは思えないので、やっぱりみんな問題読解に苦労してるんだよね。
• そういえば、本当に2進数でいいのかな？
  • 「nの最下位から連続するすべての1ビットを0にして、その次の0ビットを1にすると n+1 が得られる」ってオートマトンの授業で習った記憶があるけど、それと同じことだよね。だからOK,と。

B. Fair Warning

• id:iakasTがBigIntegerうんぬん騒いでいたのはこういう意味だったのか。
  • 自作のBigIntegerは BigInteger / int はできるけど BigInteger / BigInteger ができない...
  • しかし今日の私には Ruby のご加護がある！無敵！
    • Emacs に ruby-mode が入っていませんでした...
      • え、なに、aptitude で入れられるの？
      • aptitude install ruby-elisp
      • できた。いい時代になったものだ...
• はい。周期っていうのはつまりGCDですよね。
  • もっとも近いeventから周期 T ずつ進めていって、未来になるような最初の年を求めればよい、と。
  • 算数ですね。こういうの超苦手。
  • 現在に近い候補の年を3つほど挙げて、その中でもっとも近い未来を探しました。
• 算数も大変だったけど、入力を取るのも地味に面倒でした。
• それはそうと submit. Correct!
• 調子に乗って large も送ろう。
• ...え？
• 「Zero Divisionで落ちました」だと？
• ...同じ年に2回以上 event が起きてるのか！
• 入力の数列に unique を掛けよう。答え出てきた。
  • よしsubm...
  • ...待て。
  • こういうケースってどうするのが正しいんだ？
  • 周期 T = 0で毎年起こって答えは 0 になる？
  • まだ5分あるし、とりあえずそっちも書いてみよう。
    • ほとんどのケースで0が返ってきた。
  • どっちが正解なのかなぁ...
• ...
• 周期 T = 0 => 毎年起こる、って何か違う気がする。
• Constraintsに「t[i] != t[j] for some i != j」ってわざわざ書いてあるのも気になる。
• uniqueの方が自然な気がするなぁ。
  • どうせ A-large は通ってるだろうし、腹くくっちゃえ。submit.

C. Theme Park

• なんかBより簡単そうな気がする。BigIntegerを差し引いたとしても。
• g[i]を先頭に乗せたとき、一緒に何人乗せられるかと、次にどのグループを先頭に乗せることになるかをあらかじめ覚えておく。
  • ここlargeだと面倒くさいかと思ったけど、largeでもN = 1000なのでO(N²)で簡単に書ける。よかった。
• で、これを使ってR回ループ回して計算できる。
  • O(N² + R) かな。
• smallはこれでいいとして、largeの R = 10⁸ってちょっと不安だなぁ。
  • たった50ケースだし間に合うのかもしれないけど。
  • とりあえずアルゴリズムだけ考えてみよう。
• えーと、1回運転したときに何人乗るか、次に誰が乗るかが全部分かってるんだから、それを使って2回運転したときのも求まるはず。
  • ってことは4回運転したときのも、8回のも、16, 32, ... も全部求まる。
  • これらを使って、p乗を log(p) で計算する時のように計算できる。
  • O(N² + log(R)). 完璧だ。
    • なんとなく The First KMCMonthly Contest の Problem A の id:wata_orz先生による解説記事を思い出しました。
• って、これ書くの...？面倒くさい。
  • えぇい、愚直なのを書いて、遅かったらその時考えよう。そうしよう。
• あとはコーナーケースみたいなのがないだろうか？
  • 答えは64bitに収まる。
  • 一緒に何人乗せられるかループ回して計算していくとき、うっかり同じ人を一度に2回以上乗せたりしないように注意。
    • これは撃墜ポイントだなぁ。
      • 後でsampleに入ってたことに気づきました。
• さて実装だ。
  • BGMはシンフォニック・ラブ (橋本みゆき)を1曲エンドレスで。
• かたかたかたかた。書けた。バグったけどすぐに直った。
• large最大ケースを突っ込んでみよう。
  • 出てきた...けどオーバーフローしてる？
    • long longのはずがintになってました。それも3ヶ所ぐらい。
    • 直したらそれっぽい値が出てきた。
• 1ケース0.6秒ぐらい。 -O2 付けて0.3秒。
• これなら大丈夫だよね。smallをsubmitしよう。
• Correct!
• largeは全50ケース4秒ぐらいで終わった。意外と速い。
  • それっぽい値が出ていることを確認してsubmit.
• お疲れさまでした。

結果

• B-largeだけ落ちた。
  • 算数が間違ってたのかな。
• まぁいいや。通ったし。