Google Hash Codeに参戦しましょう。
メリークリスマス！アドベントカレンダー25日目の記事です。
adventar.org
Google Hash Codeとは、
Googleの競技プログラミング大会、Google Code Jamはとても有名ですが、Google Hash Codeという大会もあります。2019年より、世界各国からも参加できることになりました。解答提出チームだけみても6640チームと、おそらく現時点でも世界最大規模のコンテストの１つといえます。しかし、今までの競技プログラミングコンテストとは、いろいろ違うので、その参加の記録をシェアしたいと思います。チーム戦で、マラソンマッチ系のコンテストですが、データ量が膨大で、独特の面白さ・難しさがあります。
Hash Code 2019 ルールなど
・時間
4時間。ただし、問題公表まで15分ぐらいあるため、実働は3時間45分ぐらい。
・参加資格
決勝にいけるのは18歳以上。Google Code Jamと同じです。Googleの人は参加できません。
・メンバー
2～4名です。1名での参加は不可能なので、注意。同地域の仲間を探すサイトもありましたが、twitter等で探したほうが早いと思います。
・開催時刻
日本時間の夜中2:00～でした。
・練習
ジャッジシステム
https://hashcodejudge.withgoogle.com/#/home
ただし、いつでも使えるようではないようです。あと、確か一部の過去問だけだった気がします。
・過去問
https://codingcompetitions.withgoogle.com/hashcode/archive
・決勝大会
決勝に進出できたのは、上位41チームでした。何チーム進出できるかは、予算の都合なのか、少しあいまい。世界大会にでた場合の交通費は大半はでるらしいです。
体験記
チームメンバー
4名で参加しました。全体のバランスが良いチームだったと思います。
たんざくさん（@_tanzaku_）
近年は、特にマラソンマッチ系コンテストの活躍が素晴らしく、今年のTopCoder Open 2019のマラソンマッチ部門で、初の世界大会に進出、世界8位の成績を収めました。
宇宙ツイッタラーXさん（@kenkoooo）
twitterのフォロワー7万人、みなさんご存知のAtCoder Problemsの制作者。過去の所属会社で競プロイベントを必ず開催してきた、日本の競プロ界なら、だれでもご存知なはず。一般開発に強いので頼れますし、AtCoder黄色です。
きゅうりさん（@kyuridenamida）
競プロ界で10年以上にわたり、幅広い世代に人気のある（いじられている？）競技プログラマー。短期コンテストも長期コンテストも両方できるバランスタイプ。簡単な問題の手の早さには、定評があります。
準備
１回だけチーム戦の練習を行いました。また、バラバラですが、全部の問題に目を通しておきました。練習結果は、決勝にいけない成績ではあったのですが、その際に、いろいろ学べました。
- 4人同時のインターネット通話は不自由が多いので、集まったほうが良い。
- 全員で協力して1つの良い解法を作るのを狙うよりは、解法をバラして、あたり解法を逃さないことが有効
など。練習は少なくとも1回はやっていくのをお勧めします。
本番
- 問題
ざっくりいうと、写真を並べてスライドショーをつくることで、得点を最大化する問題です。写真にはタグがあります。縦写真を２枚組み合わせるか、横写真を１つ使うと、スライドが作れます。スライドを一列に並べたものがスライドショーになりますが、となり合うスライドをA,Bとすると、min{Aのみのタグ, Bのみのタグ, AとBの共通のタグ}だけの得点が入ります。
- データは以下のようにバラバラですが、一部のサイズがかなり大きいです。
- 深夜にもかかわらず、自分以外の3人は同じ場所に集まって行い、自分だけ通話する形で行いました。
- Slackとgithubを使用しました。ビジュアライザは各自用意しました。
- まず問題を全員すぐ理解できるように、情報をシェアして、お互い誤読してないか確認しました。
- サンプルケースについて、どんなデータが入ってるかは説明されておらず、データファイルをみて分析する必要があります。
- データサイズが違うということは、得られる得点も全然違います。得点が正規化されるTopCoderマラソンマッチとは全く違うので、入力データがどんなものか、最大で何点とれるかを調べるのは、非常に有効だと思います。
結果
Hash Code - Google’s Coding Competitions
199位/6640で、決勝に進むことができませんでした。日本のチーム内では3位でした。
日本のチームでは
- 16位 Gifted Vookies
- 17位 AtCoder
が、ダブリンでの世界決勝進出の権利を得られましたが、AtCoderチームは辞退されていて、Gifted Vookiesのみ世界大会に参加したようです。
反省点
- データサイズが大きすぎるので、良い貪欲法を作るのが最重要なのですが、データを絞ったうえで、軽い焼きなまし・軽いビームサーチっぽいのも、差をつけるために有効なのかなと思いました。
- チーム戦しかも数時間のコンテストだと、他のメンバーが良さげな方針を引いた場合、ハズレ方針っぽいの実装に集中するのはなかなか難しいことが分かりました。しかし、それでも集中すべきでした。ハズレ方針をつぶせただけでも立派な貢献ですし、今回は自分がやってた方針が、外れではなかったので…。
- たんざくさんのマラソン形式の実装がとても速いのが分かったので、来年はたんざくさん希望の言語にそろえるのもアリかなと思いました。
個人的な技術的には以下
AtCoderチームのchokudaiさん
来年に向けて
他のコンテストとは違い、攻略法がまだ定まっていない（例えば計算資源をどう使うか、そのためにどのようなアルゴリズムを使うかなど）ので、楽しいですし、開拓のしがいがあります。ぜひみなさんも参加しましょう！
