Google Hash Code 2021 Online Qualifications 参加記

2/26 2:30-6:30 (日本時間) に開催された Google Hash Code 2021 に参加しました。

codingcompetitions.withgoogle.com

Hash Code への参加は初めてでしたが、とても楽しかったです。

結果は 4510位/9004チーム中でした。同じ点数のチームがたくさんいたのできっと同じ解法だったのでしょう。

Google Hash Code とは

Google Code Jam と同じく、Google 主催のプログラミングコンテストです。個人戦のアルゴ系のコンテストである Code Jam とは異なり、チーム戦の短時間マラソンマッチです。 1つの問題と複数のテストケースが示され、2-4人のチームでできるだけ高いスコアを目指します。あまり他のコンテストでは見ない形式で、今回参加してみても独特の面白さを感じました。

これでせめてもう少し早い時間帯の開催だと嬉しいのですが、世界中に参加者がいることを考えるとあまり我儘も言えないですね……。

Google Hash Code についてもう少し知りたい方は、公式サイトや診断人さんの記事を読んでみてください。 shindannin.hatenadiary.com

チームについて

FORTIUS というチーム名で、matsu7874 さんとの2人チームでした。

言語は matsu7874 さん製ソルバーが Rust、Noimin 製ソルバーが C++、その他共用スクリプトに Python、という感じに特に統一はしていないのですが、統一したほうが良かったのかもしれないと思いました (後述) 。

問題について

道路と交差点、車とその辿るべき経路が与えられます。

各交差点の信号機の切り替えスケジュールを指定して、できるだけ多くの車ができるだけ早く目的の経路を辿り切れるようにするという問題でした。

f:id:noimin:20210228151749p:plain (問題文 pdf より引用)

問題の制約は

シミュレーションの最大秒数 $D \leq 10^4$
交差点の数 $D \leq 10^5$
道路の数 $S \leq 10^5$
車の数 $V \leq 10^3$

など、何も考えずにシミュレートしていると現実的な時間で計算が終わらなくなりそうなものになっていました。マラソン形式のコンテストではありますが、そういう意味ではアルゴっぽい面白さもあったように思います。

実際に解いてみたい！という方はジャッジシステムのページから問題文がダウンロードできます。

競技前・競技中の動き

前々日〜当日 1:30

リポジトリを用意しました。

提出物はソースコードの zip および各テストケースに対する出力であるということはわかっていたので、複数のソルバーの中で各テストケースに対する最高スコアの出力を判定し、ソースコードを zip に固めるスクリプトを書きました。

これらの準備は matsu7874 さんと私の両方で行いましたが、個人的な準備としてはコンビニで夜食とモンスターを買って、帰宅後に仮眠を取りました。

2:30

問題文はまだ公開されていません。事前準備として matsu7874 さんとGoogle Meet の通話を繋ぎ、Google による配信を見て問題が公開されるのを待ちました。私が英語が得意ではありませんが、 Google Map がどうこうとか言っていたように聞こえたのでもしかしたらグラフ系の問題か？なんて思ったり思わなかったりしました。

2:45

問題文が公開されました。私がリポジトリにテストケースを追加している間、matsu7874 さんが問題文を読んでくださっていました。

テストケースを push 後に合流したのですが、このときに matsu7874 さんが問題の概要を簡潔に口頭で伝えてくださったので私が問題を読むのはその続きからでよく、効率が良かったです。

問題文を読んで認識を合わせたあと、最初はmatsu7874 さんがビジュアライザを、私がスコア計算のスクリプトを書いていくことになりました。

5:00 頃

この辺りでスコア計算が完成し、時間も時間なのでいい加減 solver を書き始めないとな〜と焦りだしました。

書くのが簡単そうでそれなりのスコアが出そうな、「各交差点の全部の信号を1秒ずつ青にする」solver を書いてみることにしました。

5:30 頃

「各交差点の全部の信号を1秒ずつ青にする」solver での解を提出しました。

スコアは以下の通り。

A – An example 1,001 points
B – By the ocean 4,565,642 points
C – Checkmate 1,231,878 points
D – Daily commute 969,685 points
E – Etoile 661,797 points
F – Forever jammed 455,737 points

ここで私たちは重大な事実に気付いてしまいます。ビジュアライザは用意されていたのです。

これはやってしまいました。もちろん、リッチなビジュアライザではないので自前のビジュアライザを用意すると言う手もあるにはあります。ただ私たちは2人チームであり、ビジュアライザが一応用意されているとなると、ビジュアライザの優先度は下がります。例えば私が思いついた最初の解法以外のシンプルな解法のソルバーをお願いするなどしておいたほうがよほど matsu7874 さんの実装力が活かせるというものでした……。

残り時間はあと1時間を切りました。ここで 0 から新しいソルバーを作るのは難しいので、最初に提出したソルバーをそれぞれの方針で改良することにしましいた。

6:30

最後の悪あがきでテストケース A のスコアのみが上がりましたが、そもそもテストケース A は小さなテストケースなので全体のスコアにはあまり寄与せず。

楽しかったのですが、まだまだ不完全燃焼なまま競技時間が終わってしまいました。4時間はあまりに短く、必死だったので、コンビニで買っておいた 500ml 缶モンスターがほとんど消費されていませんでした (ただしそのモンスターはその日の仕事中に大いに役に立ちました) 。

良かった点

初参加でなかなか勝手が掴めませんでしたが、やって良かったな思ったこともいくつかありました。

スコア計算・ソースコード圧縮を行うスクリプトを事前に用意しておいたこと。
チームで通話を繋ぎながら問題文を読み、認識を合わせられたこと。私は英語の問題文を読むときに誤読しがちなので、認識を合わせることで安心してすこけいさんを書き始めることができました。
過去の参加者のブログを読みながら当日に有効になりうる立ち回りについて勉強していたこと。 (まだまだ情報の少ないコンテストのはずですが、日本人の記事は結構簡単に見つかってすごかったです)

反省点

問題文を読み終わったら、とりあえず早めに提出をしてみるべきでした。提出していればもっと早くビジュアライザの存在に気づけたでしょうし、各テストケースで出せるスコアのスケールの違いについても考えやすかったはず。
言語は合わせたほうが良かったかもしれません。スコア計算部分は焼きなまし等を行うときに必要になるので、使いまわせたほうが便利です。(チーム全員が化物みたいな実装力を持っていれば別ですが少なくとも私は違うので……)
最大スコアを取るソルバーの出力を判定するスクリプトを書きましたが、なくても良かったかもしれません。チームのスコアは「各テストケースに対するスコアの最大値」の総和なので、最新の提出であるテストケースについてのスコアが下がったところで最終スコアには影響しません。今回はソルバーを書く時間が十分に取れなかったのがスコアを伸ばしきれかった要因なので、とりあえず各テストケースに対する出力を出して提出して、提出回数 (≒書く solver の種類数）を増やすべきでした。このあたりは来年ルールが変わったらまた違うかもしれませんが。

おわりに

個人的には、ICFPC のようなプロコン総合格闘技みを残しつつ、 ICFPC よりもアルゴの人にとっつきやすくなっていてとても楽しいコンテストでした。

来年度もスケジュールと睡眠の調整を頑張って、なんとか出たいですね。