HACK TO THE FUTURE 2022 予選に参加しました

HACK TO THE FUTURE 2022 予選に参加しました. 結果は暫定テスト40位,システムテスト39位でした. 個人的に良い順位が取れて,気分がいいので,解説を書きます. やったことは,公式の解説放送で解説されていることがほとんどなので,解説放送を見た人向けに書きます. 参考になるかわかりませんが,個性を出した部分はアンダーラインを引いています

ちなみに,最終提出版のseed=0のビジュアライザーはこんなかんじになりました.

Share Visualizer

問題概要

  • メンバー数20人のチームがあり,完了すべきタスクが1000個ある.メンバーにタスクを割り振って,なるべく早くすべてのタスクを終わらせよう.
  • タスクには依存関係がある.
    • 例) タスク aはタスク bとタスク cを終わらせないと始めることができない.
  • あるタスクが完了するまでの日数は,タスクを割り振られたメンバーの技能レベルとタスクが必要とする技能レベルによって決まる.
  • メンバーの技能レベルは与えられないので,推定する必要がある.

立てた方針

問題を大雑把に以下の3つに分けて考えた.

  1. メンバーの技能レベルの推定
  2. タスクの優先順位の決定
  3. タスクの割り振り

2番目,3番目の問題は1番目の問題に依存している. メンバーの技能レベルの推定値が変わることで,タスクの優先順位は変わるはずだし,各メンバーがタスク完了までにかかる推定日数も変わる. よって,計算の流れは以下のようにした.

  1. いくつかタスクを実行
  2. 実行したタスクからメンバーの技能レベルを推定
  3. タスクの優先順位を更新
  4. タスクを割り振り,実行
  5. 2に戻る

これを全タスクが完了するまで繰り返した.

やったことの解説

メンバーの技能レベル推定

  • 各メンバーが完了したタスクとかかった日数を記録しておく.
  • (タスク完了までにかかった日数)と(技能レベルから予想される日数)の差の2乗の和が小さくなるような技能レベルを推定した.
  • 推定には遺伝的アルゴリズムに似た方法を使って最適化した.
    • 突然変異のみで,交叉はない方が精度が良かった.
      • ほぼランダム探索?
    • 現世代の中から優秀なものを選び,技能レベルのいくつかを変更したものを次世代にした.
      • 変更は(現在の技能レベル) +N(0, \sigma^{2})で,世代が進むたびに \sigmaの値を小さくした.
      • 技能レベルの値は0–49に収まるようにした.
        • 技能レベル生成のアルゴリズムを1万回回して最大値が49だったから.
        • ちなみに技能レベルの平均は7–8だったので,技能レベルの初期値は8にした.
  • 技能レベルの推定は,前回の推定からこなしたタスクの数が30個を超えるたびに行った.
    • あまり高い頻度で推定しても意味がない気がしたから設定した.

タスクの優先順位の計算

  • 技能レベルが更新されるたびに,着手されていないタスクについて,各メンバーの実行時間を計算.
  • 優先順位の決め方は公式解説と同じで,パスの重みを少し工夫した.
  • パスの重みはタスク実行にかかる時間の短い5人の実行時間の平均(総和)
    • 5人いたら1人ぐらいは手が開いてるんじゃない?という想定

タスクの割り振り方

  • 大きく分けて2つの段階に別れている.
    • 一番早くタスクを終わらせることができる人にタスクを与える段階
    • タスクを持っていない人へ強制的にタスクを与える段階

一番早くタスクを終わらせる事ができる人にタスクを与える段階

  • 着手可能なタスクを優先順位の高い順に見る.
  • 一番早く,そのタスクを終わらせることのできる人を選ぶ.
    • (かかる日数) =(現在処理中のタスクが終わるまでの日数) +(新たに着手するタスクにかかる日数)
    • 現在処理中のタスクがある人は,かかる日数に3日加える
      • 実際にかかる時間は(能力から決まる日数) \pm3なので,3日程度早くならないと美味しくない気がしたから加えた.
  • 一番早く,そのタスクを終わらせることができる人の手が空いていたら,そのタスク与える.
  • 手が空いていない場合は,そのタスクを実行しない.

タスクを持っていない人へ強制的にタスクを与える段階

  • 上記の方法だけだと,能力の低い人に仕事が回らないので,強制的にタスクを与えた.
  • 上記と同様に着手可能なタスクを優先順位の高い順に見る.
  • そのタスクをこなす早さが,早い人達と大差がないときは,そのタスクを与える

    • 優先順位の計算のときに使った,タスク実行時間の短い人5人の実行時間の総和 /3と比較した.
    •  /3を選んだのはスコアが良かったからで特に意味はない.
  • 最終盤では,強制的にタスクを与えない

    • 最終盤で技能レベルの低い人にタスクを与えるとスコアが悪くなることが多いため.

時間があったらやりたかったこと

タスクの割り振り方に幅をもたせる

  • ビームサーチ的なことがしたかったけど,実装が重くて諦めた.

タスクの依存関係の数でパラメタや方法を変える

  • タスクの依存関係の数とスコアに関係があることはコンテスト中にわかっていたが,なにかする時間と気力がなかった.



解説はここまでで,あとは日記と感想です.


コンテスト中の日記

1 – 4日目

  • 技能レベルをを推定しながらタスクの優先順位を決めていくという方針はすぐに立った.
  • 技能レベル推定は面倒なので,とりあえず,優先順位をいい感じに決めていく方針で,プログラムを書き始めた.
    • タスクの優先順位の決め方は解説部分とほぼ同じで,パスの重みはタスクの必要技能レベルの合計にした.
  • なんかバグってるような気がしつつも,人並みに点数が取れていたので,気にしなかった.
    • 実際に優先順位計算部分にバグがあり,番号の若い順番にタスクが実行されていた.
    • 番号の若い順番に実行するのはそれなりに強いので,人並みに点数が取れていた.

6 – 7日目

  • 能力推定を始めた.
  • 思ったよりもスコアが伸びないので,あれこれ考え始めた.
  • なんか初期化する値やパラメタを変えたらスコアが伸びた.
    • スコアが伸びると気分がいいので,パラメタ調整に執心する.
  • 明らかに適切でないパラメタを入れてもスコアが伸びたので,バグがあることを確信し,デバッグ開始.

8 – 9日目

  • 野球を見ていたので,あまり作業が進まなかった.

最終日

  • 00:00ごろに,デバッグが終わったものを提出すると,96kだった.
  • 朝起きてからは,適当に思いついたアイデアを実装&人力でパラメタ調整.
  • 100k点に乗せたかったが数百点足りなかった.
  • 暫定テストのテストケースに偏りがあることに気づいていたので,最終提出はseed=0–149で実行したときに,スコアが一番高いものを提出し,コンテスト終了.

感想

最初に立てた方針がよかったようで,公式解説と同じような事はできていたが,デバッグに時間がかかり,つらかった. デバッグをもうちょっと早く終わらせたら,色々できた気がする. 暫定順位が40位で,3000円がもらえるかと思ったけど,システムテストで1つ順位があがって39位になった. 順位があがったのは嬉しいけど,3000円ほしかったな…

上位の人はMCMCを使っているようなので,ベイズ統計学の勉強をして,ベイジアンになりたい. なんかいい本ないかな?PRMLは一度挫折したからなぁ…

良かった点として,長期コンテストで2桁順位になれたこと. 短期コンテストではAHC004で一度だけ2桁順位になったけど,運でなった感じがしていた. 今回のコンテストは運ではなく実力で取った感じがして,すごく気分がいい.

もう一つ良かったのは,Golangでコンテストに出るのに慣れてきたこと. Pypy3やPython3 + Numba + Numpyでやっていたときより,やりやすい気がする. コードを書く量はGolangのほうが長くなってしまうけど,実行速度を気にしないでかけるのは楽だ. Pythonだと,書き方によって実行速度が変わったりして,よくわからないところに気を使わなければいけなかった. アルゴリズムのコンテストもGolangに乗り換えたいけど,乗り換える労力が大きいので,Python3のままかな.

あと京セラプログラミングコンテスト(AtCoder Heuristic Contest 006)のレート増加と合わせて,Heuristicのレートが2000を超えました.アルゴリズムのレートの倍近くになってしまった.

余談

技能レベルの推定に遺伝的アルゴリズムを使ったのは,chokudaiさんが「遺伝的アルゴリズムがコンテストで勝ったのを見たことない」的なことをtwitterでつぶやいていたのを見て,使いたい気分になったからです. 変な遊び心を出さずに普通に焼きなましすべきだったかな?