[HACK TO THE FUTURE 2022 予選] A - Project Leader

[Q] https://atcoder.jp/contests/future-contest-2022-qual/tasks/future_contest_2022_qual_a

解説V https://www.youtube.com/watch?v=H_MuLN6L-r4

Q. result?
A. [173位/766] 91157score
https://atcoder.jp/contests/future-contest-2022-qual/submissions/27152459

Q. 81084点？
A. 手が空いている人を、タスク1番から順番に消化する。

- 依存関係数が大きいタスクから処理
70000点台に落ちる。
「若いタスクから消化する」が有効だったらしい。

- ダイクストラでクリティカルパスを見つける。
「タスクの総合値の総和」を要素にし、大きい値から処理を実装したら、85000点台に伸びた。
数字が若いほどクリティカルパスの可能性が高い傾向がある。

こんな感じの値になってた。
task[1] = 4500
task[2] = 4480
task[3] = 0    // 依存関係がないタスク
task[4] = 3990
task[5] = 4200
...
task[500] = 2000
...
task[990] = 80
task[991] = 110

- ダイクストラでクリティカルパスを見つける2。
「平均的な人が着手した場合にかかる日数」を要素にしたら、91000点台に伸びた。

- ステータス予測どうしよう？
精度上げられなかった。「タスクの総和」と「かかった日数」をもとに「ステータスの総和」を予測しただけ。
ステータスごとの予測ができないので、戦略を広げられず、絶望して闇堕ちしました。

- 忙しいとき(依存関係のあるタスクの消化に詰まってきているとき)に、ステータスの低い人にお休みを与える。
seed32など、依存関係の厳しいタスクで1200 -> 1600スコアにのる。
91000点台に伸びた。

社会は、有能な人だけで回っているんだ。

- 解説Vを見て
個別ステータス予測は
1. なんかランダムな値を見込む。
2. 近いのが見つかったら、+-1して、評価を繰り返すだけで、案外ピタッといけるらしい。

・Rが大きい場合はクリティカルパス優先。小さい場合は効率のいいタスクを振る

・(終わった人+終わりそうな人) * (優先度の高いタスク指定) で最小費用流やれば10万点いく

・状態によって評価のつけ方を変える必要がある。 

                  人 > タスク      タスク > 人 
1. パスの重み         UP              DOWN     // クリティカルパス
2. 向いてる仕事      DOWN              UP      // タスクの消化平均日数に対して、その人がかかる日数

・日数「１」は、その人にタスクふりまくれば早いかな？

（くやしいけど、全部全部、発想の範疇にあったんだ。10回くらい、やろうかな、無理そうだな、を繰り返してあきらめたことだった。実行力、本当に大事。ちゃんと実行する。）

最終 91157score
https://atcoder.jp/contests/future-contest-2022-qual/submissions/27152459

マラソンならではの工夫した試みもいくつか。
1. Makefileつくった
コンパイル時にdefineを指定できる -DTESTER=0 で動作を変えるようにした。
2. toolsをローカル導入した
あるの知ってたけど見ていなかったから、自前で質の悪いデバッガ作ってしまった。
3. 変数名と関数名ちゃんとつけてみたが、本当に難しいね。
https://github.com/syamashi/atcoder/tree/main/HTTF2021