メモジャンボ

良い感じのブログタイトル募集中

Google Hash Code 2020に参加しました

競技プログラミング
こんにちは、モジャンボです。
sim(simkaren)、モジャンボ(Mojumbo)、じゅっぴー(juppy)、ぴーよ(holeguma)の4人でチーム名SiMoJapPiyoとしてGoogle Hash Codeに初参戦しました。とても楽しく、貴重な体験ができたので参加記を残しておきます。

コンテスト前

19:30から22:30まで仮眠をとって、0:00ちょうどくらいに大学に行くとsimとjuppyが待っていました。ぴーよはその一時間後くらいに来ました。その日simはバイト、ぴーよはインターンがあったらしいです。お疲れ様です…
こんなに夜遅くに大学に集まるのはさすがに初めてだったのでテンションが上がりました。研究室に配属されると珍しくなくなるんですかね
集合が早く、コンテストが始まる2:30までかなり時間を持て余しました。僕はじゅっぴーが持ってきてくれたRealforceをしばいて、simはまちカドまぞくを観て、juppyはASMRを聴いて などして時間をつぶしていました。ぴーよが来た後はコンテスト開始後の流れや4人の役割分担を相談しました。
キーボード3台で同時コーディングするのがSiMoJappyの基本スタイルです


コンテスト

2:30コンテスト開始だと思っていましたが、2:45まで謎の待機時間がありました。
問題が公開されました。まずは全員で問題文を読んで、誤読を防ぐために問題内容を共有しました。
問題の概要はこんな感じです

\(B\)種類の本(それぞれ価値\(S_{i}\))と\(L\)個の図書館があり、期間は全体で\(D\)日間です。
各図書館\(j\)には、蔵書の集合(冊数\(N_j\)と本のIDの列)と、サインアップにかかる日数(\(D_j\))と、その図書館の本を1日に最大何冊までスキャンできるか(\(M_j\))のパラメータが定められています。
図書館は一度サインアップされた後、毎日\(M_j\)冊まで本を選んでスキャンします。(スキャンは並列に行えるがサインアップできる図書館は常に1つまで)。
サインアップする図書館とその順番、またスキャンする本をうまく選んで、スキャンされた本の価値の総和を最大化してください(ただし同じIDの本を複数回スキャンしても一度しかカウントされない)。

まずはぴーよとじゅっぴーがデータセットの中身を詳しく調べてくれました。
この問題は図書館をサインアップする順番を決めるパートとスキャンする本を選ぶパートに分かれるので、本を選ぶパートはsimにお願いして、僕は選ぶ図書館とその順番を焼きなますことにしました。

コンテスト中のコードの共有などはslackで行いました。
3

図書館の焼きなましは2点swapとdelete/insertを近傍として交互に行いました。
本を選ぶsimパートは、ゲインの小さい図書館から順に、価値が高い本を選ぶ貪欲をやってるっぽかったです(よさそう)(違ったらごめん)。

BDはそれぞれぴーよとjuppyが最適解を求められると言っていて両方かなり高いスコアが出ていてすごかったです。

バグらせながらもなんとか実装ができたのですが、凍結前の順位は1600万点くらいで順位は4000位くらいとかなり悪かったです。

終了10分前にsimがC問題の貪欲解を提出したら144万→564万に伸びて何事！？と思いつつその解をもらって初期解にしたら終了2分前にEFもめっちゃ伸びて大騒ぎになりました。

4

最終的なスコアが合計26711218で、全体598/10724位、国内15/43位になりました。


コンテスト後

Twitterを見ながら感想戦をしました。
反省点としては、コード片以外にも各自の進捗や情報をslackで共有すべきだったかなと思いました。
自分の場合は近傍の取り方や初期解(これが悪くてスコアが伸び悩んでいたことが後でわかった)をどう作ったかなどを共有したほうが良かったですね。とはいえコンテスト時間が短いのでなかなか難しいですが…
来年もまた出たいです。お疲れさまでした。