Google Hash Code 2020予選 参加記

Posted on 3 mins read

Google Hash Code 2020という競技プログラミングのコンテストの予選に参加しました。 Hash Codeは競技プログラミングの中でもマラソンというできるだけ最適解に近いものを求めるコンテストで、その中では4時間という比較的短めで2-4人のチーム戦という少し特殊な形式になっています。 参加チームが非常に多いコンテストで、今年も1万チーム以上参加したようです。 人数は2-4人の条件を満たせば当然多いほうが有利なのですが、予選通過(30-50チーム)は到底できるレベルではないだろうと思っていたので楽しむつもりでICPCのチームGirigiriで3人で参加しました。

コンテスト

問題はここから見れます。 図書館の集合とそれらに所蔵されている本(図書館同士でかぶることもある)・本のスコアが与えられるので、指定された期間内に利用できる本のスコアの合計を最大化するために、図書館の登録の順番とそれぞれの図書館で本を利用する順番を最適化するというものでした。

開始10分前ぐらいにpracticeの問題を見ようとしたがもう消えていた… 開始後10分ぐらいで問題を理解した後、joeが入出力の確認のため愚直解提出、自分とおぎのがテストケース分析をすることに。 テストケースはA~Fの6つあり、それぞれのテストケースに対して最もスコアが高かった提出の合計が得点になります。 このあと具体的な動きを書こうと思っていたんですが時間がたち忘れてしまいました…

全体的には、僕が山登りの部分、joeとおぎのがケースごとの初期解の作成をやった気がします。 ソースコードはこちらで公開しました。

反省

短時間でチームで開発するということもあって、ソースコードのマージが大変でした。 はじめはGitなどは使っていなかったのですが、結果的に各自それぞれ別のGitを使って管理することになり、はじめに共有のレポジトリを作っておくと効率がかなり上がったと思います。

グローバル変数は実行中に書き換えないなどの方針も先に共有しておくとスムーズに進んだかもしれません。

結果

結果は55位でした。

46位までがFinal Round進出だったので、かなり(少なくとも想像していたよりは)惜しい結果になりました。 悪くない解法の方針を引けたという運の良さもあったと思いますが、決勝進出のチャンスがあるとは予想していなかったので終了直後は悔しさが大きかったです。 来年はしっかり準備してリベンジしたいと思います。