Goolge Hash Code 2021 予選参加記

この記事は何？

2/26の早朝(日本時間で2:30~6:30)に行われたGoogle hash code 2021の参加記です。

僕自身にとっては初めて真面目に参加したマラソンマッチでありましたが、友人と二人でseijo9というチーム名で参加し、後述のように予選通過までは行かないもののそれに迫る望外の成績を修めることができました。

この記事では、問題と自分のチームの振る舞いの振り返りつつ、どうして自分のチームが割りに高得点を得ることができたのかを自分なりにまとめてみます。

また、初のマラソンマッチ、チーム戦ということもあり、チームでのファイルの共有、結果の共有に改善の余地もあったのでそれについても少し記します。

*注:素人なので間違ったことや検討外れなことを書いている可能性があります

Google Hash Code 概要

Hash Codeは簡単にまとめるとGoogle が主宰する世界最大級(？)のマラソンコンテストです。(URL:https://codingcompetitions.withgoogle.com/hashcode/)

コンテストの特徴として、チーム戦であり2~4人のチームを組んで出場すること、短時間のコンテスト(今回の予選は4H)であることがあげられると思います。

また、スコアリングの特徴として、テストケースが5~6つほど与えられ、与えられたテストケースに対して、良いスコアを出す回答をテキストファイルで提出するというスコアリングです。

また、各テストケースの最高得点の和がチームのスコアになるので、与えられたそれぞれのテストケースに対して、それぞれ最適化をかけることができます。

問題概要

URL:https://hashcodejudge.withgoogle.com/#/rounds/5879728443490304/

現実に近いような問題設定で詳細に問題内容を説明することはできそうないので詳細は省略しますが、渋滞を緩和するような信号機のスケジューリングをする問題です。

締め切り時間内に目的地まで到達するような車の数とその到達までの時間の和がスコアとなり、これを最大化するような信号機のスケジューリングをすることが目的になります。

与えられるパラメータとして、締め切り時間、交差点の数、交差点間をつなぐ道路の数、車の数が与えられ、1つの道路は始点、終点、長さが与えられ、道路は重み付き有向グラフとして表現されます。また車にはそれぞれ、始点から目的地までのパスが与えられ、その通りに移動する必要があります。

自分のチームの立ち振る舞いとスコア遷移

当日まで

大会１週間ほど前にマラソンコンテストの解き方を学ぶ、かつhash code の方式を知るためにhash code のホームページに公開されていたpractice round 2021を友人と解きました。

友人は今までにマラソンマッチに参加した経験が何度かあるため、マラソンマッチの定石という事で愚直回の実装、スコア関数の作成、山登り方の実装、焼きなましの実装までを教えてもらいながら行いました。

その後、自分でも実装する経験を積むためにHack To The Future 2021の予選の問題を友人にアドバイスしてもらいながら行いました。

コンテスト当日

~2:30

友人と一緒に自宅に集まりダラダラ過ごす。

2:30~2:45 準備

2:30から開始かと思いきや開幕式が始まりヤキモキしながらフォルダの作成などをする。

2:45~3:15 問題文読解

二人とも英弱だったので、問題文を30minかけて読む。
30minほどかかるのは想定外というほどではなかったものの、問題設定が難しく、どうやるのかイメージが立たないまま読み終わる。

3:15~3:45 初期解の実装(信号間隔均一)

友人が初期解として、全ての信号を等間隔で切り替えれば締め切り時間は無視すれば全ての車が目的地まで到達するコードはかけるというので書いてもらう。

信号の間隔を最初は20sec とかにしていたが、1sec まで縮めて次々に切り替えた方が良さそうという事で変更してもらう。

3:45~4:05 初期解のバグとり

複数テストケースをfor ループで回しているのに、配列のclearを忘れるというミスを犯し、最初のテストケース以外エラーが起きるというバグに気づかず20minほどバグとりを行う

4:05　初期解のsubmit(7,885,740点)

出遅れたと思ったものの、この時点では上位100位くらい（たしか）だったので、今回の問題はやっぱり難しいんだなという感触をえる。

次にスコア関数を実装して2optで山登りに移行しようと考えるが、スコア関数の実装がめんどくさい。

締め切りまでの全時間を1秒ずつシミュレーションして、全ての時間で車、信号の状態を保持すると、計算量がO(DV)(車がいる交差点のみを考える、ある交差点に何台の車がいるかはmapを使うとlogVだが、unordered_mapを使うとO(1)でできそう)とかになり、一回のスコアの計算に10**7くらいのオーダーになることからこのままでは山登りを回すことも難しいと考え、とりあえずスコア関数の実装は後回しにして初期解をよくする方針に切り替える。

4:12 改善1(入ってこない道路の割り当て排除)(8,925,614点)

各交差点には複数の道路が繋がり、車が入ってくるが、どの車も入ってこない道路もある。
そのため、flagで使われていない道路を記録し、その道路に対しては信号機を青にしない（割り当てない）ようにした。

D,Fが大幅に上がり100万近い向上、8925614点

4:12~27 改善2(totalの交通量によるスケジューリング)(9,185,447点)

これまでは交通量によらず全ての道路に対して均等に1秒ずつ信号機の時間を割り当てていたが、その道路を通る車の数に応じて信号機の時間を変える事でE,Fのスコアが改善した。

単純に比で割り当てると、特定の道路の時間が長くなりすぎて逆にスコアが落ちたので提出デバッグならぬ提出ハイパラ調整を繰り返し、それぞれの道路の通行量が適当な閾値を超えた時に2秒間割り当て、それ以外は1秒だけ割り当てるという処理を行った。

結果として、密な頂点があるE,Fでスコアが改善した。
E 20k up
F 128k up

4:29 改善3(終端点処理の改善)(9,200,059点)

実装上の改善として、道路の全体の交通量を考える時に、車がその交差点を目的地とする場合は、その交差点からさらに出ていく必要はないため、その車はその道路の交通量としてカウントしなくて良い。
以上の実装を行い、全体的に少し改善した。

total 15k up

4:33~4:45 改善4(totalの交通量によるスケジューリング2：階段状)(9,589,712点)

初期解の改善2のさらなる改良として、閾値を１つではなく複数持たせ、階段状にすることにした。
実装上はある値で割った商を割り当て時間とした(線形的な割り当て)
階段状にすることで交通量の多い道路に対しては、多い時は10sec ほど割り当てることもあった。

残り2時間を切ったこの段階で一桁順位くらいだった。
上がり幅としては、初期の入ってこない道路の割り当て排除につぐ上がり幅となった。

total 389k up

4:52 改善5(dead車の判定)(9,605,075点)

Fのケースを考えると、全ての車が200の道路を通り、かなり長い距離を走る。

一方で車の数は少ないため信号の前で何台もスタックすることは少ないと考えられる。
このことから、Fにおいて、信号で待つ時間は基本的に自分の道路に対するシグナルが青に変わるのを待つ時間と見做せると考えられる。

そこで信号で止まる時間を入ってくる道路の数に対応する値(入次数/3)にし、基本的に車ごとのtotalの走行距離のみを考えて、明らかに締め切りに間に合わないものを通行量としてカウントしないことにした。

total 15k up

4:52~5:05 お互いのハイパラのマージ(9,609,117点)

お互いの改善点をマージしてハイパラをさらに調整する

total 4k up

5:07 改善6(信号機の割り当ての順番)(9,610,118点)

信号機の割り当ての順番は初めはindexが小さい順に割り当てていたのだが、これを通行量が多い順にソートすることでAのみが1001->2002に改善した。
これは、おそらくソートが効果あったというよりは順番を変えることが大事だっただけ。
この後、信号機に割り当てる道路の順番をシャッフルして見たものの、点数は上がらず

total 1k up

5:10~5:59 停滞期

ひたすらハイパラをいじるものの点数が上がらず、テストケースを見ながらなぜ上がらないかを考える。
残り1時間半でスコア関数を書いて山登りまで実装することができるか相談するものの、僕が実装面で完璧に役立たずなこともあり諦める。

テストケースとスコア結果を眺める中で残り１Hを切った段階でビジュアライザの存在と簡単なサマリーが見れることに気付きショックを受ける。

しかし、ビジュアライザの見方があまり分からずあまり考察できず悲しい時間を過ごす。

total 0.1k up

5:59 改善7(dead車の判定2)(9,622,558点)

dead車の判定ではFのスコア上昇をターゲットにしていた。
Dのケースを考えると、 Fとは対照的に車の数がひたすら多く、信号機でスタックしている。
そのため、信号機での待つ時間の推定を変更(入次数/3 -> 入次数/10)することでDのスコアが上昇した(その時はそう考えていたが、後述のようにこれは誤解釈で、ハイパラのマージの影響だったっぽい)

total 13k up

6:00~6:30 これまでのハイパラを組み合わせ探索(9,649,573点)

順位表凍結前段階で一気に順位が落ち、29位まで落ちる。
A,B,Cは点数が上がりそうにないので、D ,E,Fに絞ってケースに特化したハイパラを作り点数を上げることを目指す。

しかし、あまり有効な考察が得られず今までのハイパラをひたすら組み合わせを変えてジャッジに投げ続けて少しずつ点数を上げる。

最後に6:29に友人が提出したものが16kの改善がされたのはチーム的に熱かった。
この時のハイパラは

信号待ち時間の期待値: 1+(交差点の入次数-1)/3
信号機のスケジューリング：1+(車の交通量-1)/35

で結局、信号待ち時間の期待値は車の数が多いDでは高めにするのがよかった（理屈にもあう）

total 27k up

結果

7000チーム以上が参加した中で全体で62位という結果になった。
日本人のチームとしては、上位３チームには大きく点差が離れているものの4位という結果であり、明らかに出来過ぎの結果だったと思う。
二人参加のチーム、一人（僕）が緑コーダーということを考えると、奇跡的な検討だった。

原因としては、問題設定が難しく、スコア関数の実装も手間がかかったため、上位陣でも（おそらく）きちんと山登りや焼きなましを回せないチームが多かったこと。
シミュレーションの計算量が多く、あまり回数を回せないこと、が最大の原因だとは思う。

一方で、早々に実装を諦め、アドホックな最適化に拘ったことが他のチームに対する優位性になった気がする。

特に、dead車の判定や、通過時間を無視した合計の通行量によるスケジューリングに早めに気づいてハイパラ調整に時間をかけれたことはかなりアドバンテージだった気がする。

反省

初のチーム戦ということもあり、反省もいくつかあった。

ファイルの共有

例えば、二人で同じ場所でコーディングしていたこともあり、なんとなく相手のPCを見たり、適宜話をしてやっていることを把握することはできていた。一方で、システマティックに共有していなかったために、相手の最新版のコードとのマージが遅れたり忘れたりしていた。（最後の30minで点数が上がったのはそのおかげでもあるが、常に相手の最新版のコードを把握していればもっと時間に余裕ができて他のことをやれた気はする）

また、残り1時間を切った段階で、各テストケースに対して現在のbest scoreを持つコードをダウンロードして、それをいじり始めたので、さら二バージョンがぐちゃぐちゃになった。

改善策

• ハイパラはベタ書きでなくて先頭にまとめて、すぐにハイパラがどんな値かをわかるようにする
• 古いバージョンのファイルを直接いじるのはバージョン管理的に危険。コード読んで差分を考えた方が結果的に早い（多分）

スコアの挙動の記録

今回の記事のように、どういう調整を行ったら、スコアがどう動いたかを記録をつけて共有するべきだったがやらなかった。
そのため、十分に最適化を行ったハイパラを別の人が再びいじったり、複数のハイパラが存在した終盤でどの組み合わせを試したのか分からなくなって作業が中断したりした。

改善策

• Goolge Docsなどのお互いに同時編集できるツールを使ってsubmitするたびに、コードの変更点とスコアを書くのが良さそう

焦りによるコミュニケーション不足

序盤ではハイパラに思いつくたびに思いついた人がそのハイパラの最適化を担当する、後半ではテストケースごとに担当者がハイパラを調整する、という風に役割分担をした。

序盤の余裕があったときは、今何をしているか、どういう意図でやっているかをお互いに共有していたが、予想外のスコアが取れ、他のチームから猛追を受ける中で焦りが生まれ、次第に疎かになった。

役割をきっちり分けることはおそらく戦略的によかったものの、終盤でもコミュニケーションはとるべきだった

改善策

• せっかくのチーム戦なので最後までコミュニケーションをとる。