HACK TO THE FUTURE 2022 参加記（259位）

HTTF2022 に出たが悔しい結果で終わった。

久しぶりの競プロコンテストで張り切って参加したが、スコアを伸ばせないまま 10 日間が終わった。

やったこと

システムテスト前の点数で言えば、10万点を超えると 20 位くらいに入る。11 万点を取った人はいなかった気がする。

とりあえずタスクを分散させて割り当てるコードを書いた。手が空いたらできるタスクを割り当てる。タスクの順番は番号順である。この時点で 7 万点ぐらいとった。

次に、タスクの順序を変えたり、スキルの予測をしたりした。スキルの予測では、難しいことをごにょごにょ考えて無駄な時間を過ごした。最終的にはスキルをランダムに生成し、完了タスクの情報を使ってそのスキルがどのくらい近いかを判定するようにした。

タスクの順序では意味のないことを長々と試していた。依存関係を解決する必要があるので、後継タスクが多いものから優先して行うようにしたり、タスクのレベルが低いものを優先したりしていた。

コンテスト開始から 5日、なんだかんだで 8.9 万点を取った。

そこから 5 日はまったくスコアが伸びす、提出の 30 分前に 9 万をとって終了。最後に投げたコードでは、タスクの順序は番号順、日数が 500 に到達したあたりでタスクの要求技能ベクトルの合計が多いやつを優先してやるようにした。こうすると終盤に簡単なタスクをこなすことができ、誰かひとりが担当している難しいタスクの完了を待つことがなくなって若干スコアが上がった。

反省点

状況に合わせた評価ができなかった

この問題では、手をつけられるタスク×チームメンバー という組み合わせのうち、もっとも良いものを採用する必要があった。しかし自分は「このタスクどう割り当てると最も良いのか」「このメンバーにはどのタスクを割り当てると最も良いのか」のように、1 対多で考えてしまっていた。

また、タスクの優先順位を考えるときも、タスクの依存関係や変化していくチームメンバーの状態などを考慮する必要があったが、最初に何らかの基準で優先度を決めて、それを実行していくという形式しか取っていなかった。

ビジュアライザを見て、取れるタスクが多いので能力を発揮できるように割り当てるのが良い場合と、取れるタスクがないので依存関係の解消を優先した方が良い場合があるのは知れていた。ただ、それを見ても「依存関係やチームメンバーの状態で優先すべきタスクを変えないといけないよね」という認識ができなかった。

対策：状況や盤面によって、取れる操作の嬉しさが変わることを認識しておく。 全部を考慮した評価関数をどう作るか？ みたいなのを考えておけばいいのかな。

難しく考えてしまった

スキルの予測は最終的にランダム生成→ランダムにずらすという探索でよくある方法を取ったが、それに辿り着く前に複雑なことを考えて時間を使ってしまった。

対策：まずランダムや貪欲でできないか考える。その次にランダムや貪欲でできないか考える。最後に本当にランダムや貪欲でできないか考える。

中途半端に高速化しようとした

探索回数を増やせばスコアが上がるという状況でなら、最後のひと押しに高速化が有効かも知れない。ただ、考察でスコアを伸ばす余地が十分にあったし、探索回数の増加がスコアの増加に繋がらない状態だったので、高速化を考えるのは間違っていた。

対策：（今の自分には意味がなさそうなので）高速化はしない。

履歴