HACK TO THE FUTURE 2022 予選 å‚åŠ è¨˜

結果としてはシステムテスト前で94890点で、100位ちょうどの順位でした。

問題

atcoder.jp

解法

問題を以下の３つに要素に分解して考えました。

1. タスクに依存関係があるので、重要度をつける

2. メンバの技能レベル推定を行う

3. 各タスクに対し、適切なメンバを割り当てる

1. タスクの実行優先度付け

タスクに依存関係があるので、依存関係の多いタスクを早めに実施しないとタスク詰まりがおきます。 クリティカルパスを探すという作業に近い気がします。 最終的には依存関係にあるタスクの中で足し上げた合計技能レベルが最大となる値をタスクの重要度とおき、重要度順にタスクを実行するようにしました。 括弧外がタスクid、括弧内がタスクの合計技能レベルとして、タスク１の重要度を求める以下の例だと合計技能レベルが最大となるパターンは３番目で、その値は45というようにしました。

1(5)→2(10)→3(20)：計35

1(5)→2(10)→5(10)→6(10)：計35

1(5)→4(30)→5(10)：計45

他にも下記のようなことを試しましたが↑が一番スコアが良くなりました。

• 依存関係にあるタスクの最大ホップ数

• 依存関係にあるタスクの合計数

• 依存関係にあるタスクの合計数*合計技能レベル

2. スキル推定

タスクの実行結果の履歴をすべて保存し、タスクが40個終わる毎に全メンバの技能レベルを更新します。 更新頻度は実行時間制限にあわせて調整しています(このへんpythonによる不利はどれくらいあるんだろう？)。 更新方法は技能スキルをランダムに増減させて、実際値の誤差が小さくなったら更新するという焼きなましです。 山登りで良いような気がしたのですが、少し戻り要素を入れた方がスコアは上がりました。

推定方法を考えるにあたってAHC003の解法を参考にしてもう少し解析的な方法を取りたかったのですが、maxが入っている式の扱いをどうしたらよいかわかりませんでした…。

3. 各タスクに対し、適切なメンバを割り当てる

最初この部分を全く行わず、来た順に処理するという形にしてタスク順調整をしていたのですが、スコアが初期貪欲解から全く向上しませんでした。 クリティカルパスがわかっていても、そのパスに適切に技能レベルの高い人を当てられないと意味がないという問題設定みたいでした。

ここのロジックは手が空いている人の中で最もタスク処理時間が早い人を割り当てるようにしました。 また、途中で手が空いていても実行にかかる時間が最速で処理できる人に対して一定以上かかる人に対してはタスクを割り当てないという仕組みを入れたらスコアが伸びました。

その他

• 3の部分はもう少し良い方法がありそうと思いつつ貪欲でしか考えられなかった。
• スコアは手元でseed0~49の50回分の合計で評価していた。ただ提出時との乖離が4000点くらいあり不安だったので、終盤は1000ケース回した値を利用していた。（ただし1000ケース回すのには１時間弱かかっていたが…）
• コードの整理をあまりしなかったせいで最後の方高速化しようとしたときにかなりバグらせた。
• アイデアの多くはビジュアライザを見ていて思いついたものだったので、可視化は大切