問題

結果

最終6,155,200点で25位。暫定は20位。

f:id:assy0000:20211213141641p:plain — seed=0, score=2145

解法

技能レベルの推定

タスクが終了する毎に山登り法で推定した。

近傍は一つの技能のレベルを+1 or -1するのと、一つを+1しもう一つを-1する、の2種類
評価値は実際にタスクにかかった日数と予測日数との差の2ノルム

タスクの割り振り

割り振るタスクの選択

依存関係のDAGを見たときに、深さが深いものがボトルネックになるので、深い方から100個程度を割り振りを考えるタスクとする。これだけだと序盤にタスクが割り振られない人が出てくるので、完了したタスクが200個未満の時点では、すぐに割り振り可能で深さが浅くないタスクも選択する(これをやるとビジュアライザの見た目は良くなってそうだったが、スコア的にはあまり変わらなかった)。

タスクの割り振りと処理順序

考慮するタスクを選択したら、タスクを誰に割り振るのか、どの順番でタスクを処理するのか、の二つを考える。処理順序については依存関係に矛盾しない範囲で任意性がある。この二つを同時に焼きなます。考慮するタスクを処理する順序に1列に並べて、それぞれ誰に割り振るかが決まれば、各タスクの処理開始日が計算でき、選択した全てのタスク完了までシミュレーションが可能である。

近傍

近傍は以下の二つ。

一つのタスクを選択し、別の人に割り振る
タスクの列において距離が10以下の二つのタスクを選択し、依存関係に反しなければ順序を交換する

評価関数

評価指標は以下の四つ。

全てのタスクが完了するまでの日数
各人のタスクを処理していない(暇をしている)日数の平均
各人のタスクが完了するまでの日数の平均
各人のタスクを処理している日数の平均

1がスコアそのものに直結するが、1のみだと探索が上手く進まないので、効率が良いタスク割り当ての指標として2〜4を採用した。

実行時間

終了したタスクがあるターンはこの焼きなましを実行する訳だが、あと何ターンでタスクが全て完了するか不確定なので、使ってもよい時間を推定しなければいけない。今までの1日あたりのタスク処理個数(= 完了タスク数 / 経過日数)と残タスク数から、残りの日数を単純に計算する。序盤ほど予測日数が長くなり、終盤ほど正確になるので、適当に補正値をかけるようにした。

初期解

一番最初の初期解は深さが深い順に並べて、ランダムに人を割り振る。それ以降は、前回の焼きなまし結果を復元し、新しいタスクは後ろに追加する。

その他

パラメータ調整やバグチェックにAWSの36コアのインスタンスを使用した。滅茶苦茶快適だったので、長期のコンテストでは次回以降も使っていく。
問題初見で、統計分からないとダメなやつか？と思ったけど探索すれば大丈夫だったので良かった。とはいえ統計勉強しないと…。
最初はタスクに人を割り振るのではなくて、人にタスクを割り振るように考えていて、実装も複雑になるしスコアは伸び悩むし苦戦していた。本格的に実装し始める前に、方針の検討を十分しないとダメ。