HACK TO THE FUTURE 2022 予選 に参加し、プレテストが 82,569点 の 399位/823人 でした。
今回は機械学習やってくださいと言わんばかりの問題でしたね。
AHC003の時も食らったのですが、私は機械学習的なアプローチ技法を持っていないので、この手の問題は手の出し用がありませんでした。。
なので今回は、基本方針を「チームメンバーの区別をせずにできること」だけに絞った、 レートの下支えと飛び賞賞金だけを目指した参加の仕方にしました(逃亡)。
やったこと
手が空いたチームメンバーに対して、タスク番号の最も若い未着手タスクを割り当てる、というシンプルな方針を取りました。
タスクの依存関係 (u_i, v_i)
は、 u_i < v_i
を満たすので、この優先度で割り当てるだけで、依存によるブロックは生じずらくなっています*1。
ただし、次数が0のタスク(他のタスクをブロックしないタスク)だけは割り当てを一番後に回し、さらにその中でも要求技能レベルの合算値が大きいものから順に見ていくようにしました。 こうすることで、ゲーム終盤での依存解決待ち発生の軽減を目指しています。
感想
今後もこの手の機械学習寄りの問題がRatedに来る感じなんですかね?流石に対策しないと不味い気がしています。。 とりあえず今回分の復習を頑張ってみようと思います。ありがたいことに解説放送もあるっぽいですし。
そして飛び賞ほしい!!
*1:はず