概要

Googleが主催しているプログラミング技術を競うコンテストで、2~4人チームで与えられた最適化問題のスコアを約4時間の制限時間のもと競います。

参加チーム数は、正のスコアを得たチームに絞っても9031チームあったようです。

49Kというチーム名で、@tomoya__20、@shikixyx と参加し、3285744点で131位でした。ほぼチームメンバーのおかげですが、期待よりかなり良い結果でした。

ただ、World Final進出には30~50位くらいに入る必要があるようなので、残念ながら予選落ちです。

問題の概要

https://codingcompetitions.withgoogle.com/hashcode/round/00000000008caae7

いくつかのプロジェクトと人員が与えられるので、プロジェクトに人員をアサインしていってスコアを稼ぐ問題です。

各プロジェクトには得られるスコア・かかる時間・締切があり、締切をすぎると得られるスコアが1点ずつ減っていきます。また、プロジェクトには複数の役割があり、1つの役割には1人の人員をアサインしなければいけません。各人は同時に複数のプロジェクトに従事することはできません。

スキル

各人は（言語、レベル）のペアで表されるスキルを複数持っています。これらは、プロジェクトの役割にアサイン可能かどうかを判断するために使われます。

メンター

役割の要件にスキルレベルが1足りなくても、同じプロジェクトに要件を満たす人員がいればアサイン可能となります。

ラーニング

役割の要件が自分のスキルレベル以上であれば、プロジェクト終了時にスキルレベルが1上がります。

本番の流れ

Discordで通話しながら進めました。

チーム戦としての基本方針

実装は各自で行うが方針の共有などは適宜行う、という感じでした。

実装を分ける意図としては、実装を役割分担すると事故る可能性があったり言語を統一する必要が生じたりしてリスクやデメリットが大きいためです。

ちなみに、言語はC++2人とRust1人でした。

やったこと

仮眠を取る
お菓子などの買い出しをする
問題を各自読む
適当に提出して、ビジュアライザ等があるか確認する
入力のパーサーを書く
6つのデータセットの分析をする
各自でGreedyを実装する
適宜方針を議論しながら改善していく

解法（貪欲）

メインループ

アサイン可能なプロジェクトが無くなるまで
- 残っているプロジェクトそれぞれについて
  - プロジェクトの全てのロールが現在のメンバーリストでアサインできる場合
    - メンバーリストからメンバーを除外する
    - （プロジェクトの終了日時、プロジェクト）のペアをキューに入れる
- 進行中のプロジェクトのうち、一番先に終わるプロジェクトまで時間を進める（プロジェクトをキューから取り出す）
  - プロジェクトメンバーをメンバーリストに再追加する
  - 適宜レベルアップを行う

プロジェクトへのアサイン可能判定

準備

(言語、レベル）をキーとしてメンバーIDのsetを持つ
- 注意点として、メンバーがスキルを持っていない場合でも0レベルとして追加する
- レベルアップ時に更新する

実装

プロジェクトの各役割について
- 要件を満たすメンバーのうちレベルが低いメンバーを優先してアサインする
  - メンター可能な場合は要件-1のレベルを確認する
- メンター判定のため、アサイン済みのメンバーの（スキル、最大レベル）のmapを更新する

アサインするプロジェクトの優先順位

「得られるスコア / roleの数」で優先順位付け

パフォーマンス改善

上記のものを愚直に実装すると時間内に終わらない（特にF問題）ので、以下の改善を行う。

メインループの回数削減
- 進行中のプロジェクトを終わらせる場合
  - 締め切りが同じ日付のプロジェクトは全て同時に終わらせる
  - 最低でもN（eg. 10）個のプロジェクトを終わらせる
プロジェクトへのアサイン可能判定回数の削減
- 得られるスコアが0のものはスキップする

スコア

復習時点ではありますが、バグ無しで（これが一番難しい）実装すると、以下のスコアとなりました。

A 20
B 800958
C 255727
D 173626
E 1598605
F 651117

20 + 800958 + 255727 + 173626 + 1598605 + 651117 = 3480053

これで56位相当です。

解法の改善

プロジェクトへのアサイン可能判定

今は、プロジェクトの複数ある役割について、先頭から順にメンバーをアサインしていっています。しかし、これでは簡単な役割に貴重な人材をアサインしてしまう可能性があります。

これを、単純に要件のレベルが高い順に人員をアサインしてみます。

スコア

A 20
B 901156
C 245226
D 276367
E 1598605
F 658362

20 + 901156 + 245226 + 276367 + 1598605 + 658362 = 3679736

これで26位相当です。

今後の改善余地について

得られるスコアが0のプロジェクトについて

時間経過につれ得られるスコアが0になってしまうプロジェクトが生じますが、ラーニング目的であれば利用価値があります。

F問題では1つのプロジェクトが同じスキルの人員を大量に要求するので、ラーニングが重要な可能性があります。（特に、4位チームが1194515を獲得しているので、改善余地はかなりありそうです）

アサインするプロジェクトの優先順位

「得られるスコア / roleの数」だと、プロジェクトにかかる日数は無視してしまっているので、序盤で大量に日数を消化してしまう可能性があります。

また、本当は締切に余裕があるプロジェクトは後で行いたいところです。

また、データセットによってはラーニング可能なプロジェクトを優先するのが重要となりそうです。

プロジェクトへのアサイン可能判定

現状は実装をシンプルにするために愚直に書いていますが、本当であれば「メンバーリスト」と「プロジェクトの役割」のマッチング問題なので、かなり改善の余地はあります。

例えば

できる限りメンタリングが生じるようにアサインする（プロジェクトの複数の要件を満たすメンバーを優先してアサインする）
要件を満たすメンバーのうち、スキル数が少ないメンバーを優先してアサインする

所感

気づき

データセットの分析は、統計値を出すことも有意義ですが、目視で確認するのも十分に有効でした。

反省

実装が重く、最初に想定したGreedyを実装し終えた時点で時間をかなり消費してしまいました。チーム戦であることを活かすためにも、（もちろんある程度行ってはいましたが）実装を始める前に擬似コードの共有などを行って、最善の実装を最短で行えるように力を合わせるべきでした。
深夜2:30から始まるコンテストなので、可能であれば前日の22時には寝たいところです。しかし、いつも深夜に寝ているのに前日だけ早く寝るのはほぼ不可能なので、前々日から睡眠調整するべきでした。

全体

問題が現実の問題に近いのと、チーム戦なこともあって、非常に楽しむことができました。

また、Hashcodeは問題が複雑なので、如何に、バグを生みにくく、早く効率的なコードを実装できるか、を鍛える良い場になります。

来年以降もメンバーが集まれば是非出たいです。