GoogleHashCode2020参加記

02/21の2:30~6:30に行われたGoogleHashCode2020予選にleaf1415、edamame88、nayutaの3人とチーム「lens1503」で参加しました。

当日まで

  • チーム名を決める。4人のニックネームの頭文字を並び替えたもの+ニックネームに含まれる数字の合計でlens1503になる。（名前を決めるのって難しくありませんか…？なんかの法則に従って決めようとしてしまう）。
  • AtCoderで日本橋ハーフマラソンがあったので参加する。B問題が貪欲をしっかり実装することで高得点になると知り、基本をしっかり考えることは大事だなあなどと思う。
  • JudgeSystemに公開されていた練習用問題を解いて、提出の方法やルールを知る。あったほうが便利だと思い、提出ファイルを自動生成するスクリプトを書くなどする。 問題は部分和問題そのもので、一瞬dpで解けるやんけ！となるが制約を見て察する(リンク先の例で1<=N<=105,1<=A<=109だった)。ここでビームサーチのような何か（解を少しずつ変えながらpqueに突っ込んで回す）と焼きなましを書く。初期解の質によって最終的なスコアが激変してなるほどなあとなる。頑張ったら理論値が出てうれしくなった。

当日

緊張して眠れなかった（小学生かな？）

糖分補給用に飴を持って大学に行く。一人一台ディスプレイがあり感動した。メンバーの方と合流後なんだかんだで開始まで2時間くらい時間が空いたので、三人+大学に残っていた方たちの前で書いてきたプログラムの解説をすることになる。無事テンパってしまい早口オタクになった（説明がうまくなりたい…）。その後ファイルの共有とかルールの確認とかしていると2:30になる。

問題が見れるのが15分後ということに気づかず「こどふぉった？」みたいな会話をする（ルールを確認したとはいったい…）
15分後

問題を見て、正の点数を得る方法を考える。とりあえず図書館を先頭から見ていって未コピーの本をコピーするコードを書いてAC。誤読してないようでほっとする。
サインアップする図書館の順番を固定すると、その状態での最適なスコアが求まると感じ、本の順番を受け取って最終スコアを計算するコードを書く…が、この処理が最悪でO(LB)ほどかかり（多分）、ほとんどのテストケースで破滅してしまった。状態をpqueにpushしつつ探索するコードを書いたのだが、6秒間かけてpqueの更新が8回くらいしか起きず変な笑いが出る。
残り1時間でスコアは2200万くらいだったと思う。このあたりでりーふさんから「図書館の順番を蔵書のスコア/手続き日数で降順ソートすると伸びそう」といったことを教えてもらう（うろ覚えです…）。その後いろんな基準でソートすると、何かの基準でFのテストケースだけ100万近く伸びた。この時点で貪欲ガチャをすることを決意し、残りの時間でひたすらいろんな基準を試しつつ伸びたものを提出していた。残り時間3分ほどになってえだまめさんがスコアを更新し、最終的に2600万台に乗ることができた。
感想戦でそれぞれのテストケースがランダム生成でないことを知り、無限チームがそれに気づいていたことにつらくなる。

感想

  • 事前に準備をしていて、当日に使いそうな関数やスクリプトを用意できていたので、落ち着いて取り組めた（当社比）と思う。
  • 途中から方針を転換できたのがよかった。ガチャを回さず高速化を頑張っていたら多分冷えていた。
  • テストケースの偏りに気づけなかったのは悔しい。テストケース名がおしゃれだなあとか思いつつ、どうせ中身はランダム生成だろ！という思いがあった。
  • 気づいた/考えたことを共有するのは大事だなあと思った。コンテスト後Twitterを見てるとスプレッドシート使って書き込んでいるチームがいて、とてもよさそうと感じた。

初めてのチームで行うマラソンコンテストだったので緊張しましたが、みんなで集まって問題に取り組むことができてとても楽しかったです。深夜にも拘わらず一緒に参加してくれたりーふさん、えだまめさん、なゆたさん、本当にありがとうございました！