HACK TO THE FUTURE 2022予選　参加記

November 15, 2021

HACK TO THE FUTURE、名前は何度か耳にしていたのですが、今回 Rated のヒューリスティックコンテストということで初参加しました。

問題概要

あなたはプロジェクトリーダーである。プロジェクトは $N$ 個のタスクからなり、プロジェクトチームメンバーは $M$ 人である。あなたは、チームメンバーに毎日タスクを割り当てていくことでプロジェクトのなるべく早い完遂を目指す。

チームメンバーは高々 1 つのタスクしか同時に行うことはできない。また、タスクの中には依存関係があるものが存在する。このようなタスクは、依存するタスクが完了している状態でなければ着手することはできない。

各タスク $i$ には、 $K$ 種類の各技能 $k$ について、技能レベル $d_{i,k}$ が設定されている。また、入力としては与えられないが、各チームメンバー $j$ も各技能 $k$ について技能レベル $s_{j,k}$ を持っている。

メンバー $i$ がタスク $j$ を行う時、完了までの日数 $x_{i,j}$ は以下の式のようになる。

$w_{i,j} =\sum_{l=0}^{K} {\rm max}(0,d_{j,k}-s_{i,k})$

$x_{i,j} = \Biggl\{ \begin{array}{cc} w_{i,j} =0のとき & 1 \\ w_{i,j} =1のとき & {\rm max}(w_{i,j}+r,1) \\ \end{array}$

(＊) r は $(-3\leq r \leq 3)$ の範囲の整数値をとる一様乱数。

プロジェクトは、 2000 日が経過するか全てのタスクを終了した時点で終了する。2000 日以内の $D$ 日で全てのタスクを完了できた場合、得点 $p$ は以下のようになる。

$p = N+2000-D$

一方、2000 日でタスクを完了できなかった場合の得点は以下のようになる。

$p = N$

点数を最大化するよう、毎日の初めにメンバーへのタスクの割り振りを出力せよ。

自分の解法

暫定テスト 95980 点で、89/823 でした。

seed0 の結果は以下のようになっています。

主に以下のパートでやったことを書きます。

メンバーのスキルの予測
メンバーへのタスク割り振り

メンバーのスキルの予測

タスクが完了するたびに焼きなまし法を行い、メンバーのスキルの推定値を更新しました。

タスク完了時に(タスク,完了までにかかった時間)の組が得られるので、この情報をメンバーごとに記録しておきます。各タスク完了記録との誤差が最小になるように、メンバーの推定スキルを上下させました。また、メンバーの推定スキルの L2 ノルムが[20,60]を外れた場合にペナルティをつけるようにしたところ、序盤の予測精度が若干改善されました。

近傍は単純に、(スキル, UP)、(スキル, DOWN)という形で表現し、一定の変動幅で[0,30]の幅で変化させました。

余談ですが、近傍を受理後に最小値 0 もしくは最大値 30 に達したとき、その近傍自体を

(スキル, UP) => (スキル, DOWN) または (スキル, DOWN) => (スキル, UP)

と更新してしまうことで近傍のサイズを固定したまま探索でき、イテレーションの回数を稼ぐことができました。

メンバーへのタスク割り振り

まず、あらかじめ各タスクについて、子孫の数を計算し、記録しておきます。そして各ターンごとに、空いているメンバーと着手可能なタスクを列挙後、その全ての組合せについてメンバーがタスク完了までにかかる日数の予測を計算し、(タスクの子孫の数, タスク完了にかかる日数予測)を優先度付きキューに入れます。この優先度付きキューから、「タスクの子孫の数」が多く、「タスク完了にかかる日数予測」が少ないものを順次 pop していってメンバーにタスクを仮のスケジュールに割り当てるということを、全ての空いているメンバーにタスクが割り振られるまで行いました。

仮のスケジュールではタスク数>メンバー数の場合に全ての空きメンバーにタスクが割り当てられますが、あるメンバー $x$ のタスク $i$ を他のタスク $j$ を担当している別のメンバー $y$ が、 $x$ が $i$ を終わらせるより早く $i$ と $j$ の両方を完了させてしまうという予測が出た場合は、メンバー $x$ へのタスク割り当てを取り消すようにしました。この仮スケジュール取り消し処理は精度がある程度信頼できる状況でないと解が悪化したため、200 日以降に行うようにしました。

解法までの時系列

70k

問題文を読み、概要を把握。この時点ではアイデアが何もなかったので、依存の解消だけ行った解法として、タスクのトポロジカルソートを行い、着手可能なスキルを空きメンバーに単純に割り当てる解法を提出した。

78k

依存関係の多いタスクを早く解消する方がいいと思い、タスクに依存しているタスクの数が多いものを優先して割り当てるようにしたら、8000 もスコアが増えた。

85k

ようやくメンバーのスキルの推定を始めた。予測は単純な局所探索法で行い、推定結果を使ったタスクの終了予測もタスク割り当て時に使うようにした。この時はタスクの終了が早い順に割り当てを行っていた。

90k

AHC003 の時に解法として挙げられていた UCB1 アルゴリズムやベイズ推定の要素を取り入れようとしてみるが、うまくいかず。

特にアイデアもなかったため、局所探索から焼きなましに変えた。AHC003 の時は近傍が悪かったのか推定を局所探索=>焼きなましに変えてもそこまで効果がなかったのだが、今回は目に見えて効果があった。

91.1k

優先度付きキューに入れる値を「タスク完了までにかかる時間」にしていたのを、「(そのタスクに依存しているタスクの数,2000-タスク完了までにかかる時間)」に変えた。(つまり、基本的にはタスクに依存しているタスクの数が多いものを優先し、それが同数の場合はタスク完了までにかかる時間が小さいものを優先)なぜか 78k の時に良かった方法を消していたので、マージしている。

92.2k

あるメンバーが 1 つのタスクを終わらせる間に、他のメンバーがそのタスクを含む 2 つのタスクを終了できる場合は割り当てを行わないようにした。ローカルではあまり効果がなかったが、提出してみると点が上がった。

95.4k

seed0 では、上位陣の seed0 の結果とそこまで差がついていなかったため、依存パスが多い問題例がボトルネックになっているのではと思い、seed5、seed26 ばかり見ていた。これらの問題では空きタスクが全然用意できずに暇になるメンバーが多いという状況になっており、このような状況を改善できる手法を考えていた。

タスクに依存しているタスクの数(つまりそのタスクから出ている辺の数)が多い順というのがあまりに近視眼的すぎることに気付き、代わりにそのタスクの子孫の数に変えてスケジューリングを行うようにしてみた。点がはっきりと上がった。

95.9k

アイデアが尽きたので AHC003 の参加記などを漁ったが、特に成果なし。

空きタスク数>メンバー数となることが多い問題ではメンバーの空きが出次第すぐにタスクが割り当てられてしまうため、試しに空きメンバーが 2 人以上いない時は何もしないようにしてみた。これで多少スコアが増えた。

これ以降は色々試すも改善できなかった。

感想

業務シーンでとても既視感のある、極めて実務的な内容ながらとても面白い問題でした。ビジュアライザでスキルの低い人が暇してるのを見ると複雑な気持ちになります。ただ、この問題に登場するメンバーは必ずタスクをミスなく完遂するぶん、皆有能の部類に入るのではと思いました。

コンテスト終了後解説放送や他の参加者のツイートを見て、自分の解法はスケジューリングパートに大幅に改善の余地があるなと思いました。子孫の数ではなくパスの最大長を見る、クリティカルパスを計算して大局的にスケジューリングを行うなどの手法は全然思いつけませんでした。

一方、推定の部分はそれなりにうまくいっていたようで、推定スキルと実際のスキルのギャップもまあまあ小さく抑えられていました。

また、実行時間については 1 秒近く余らせていたので、この時間で何か別のことができないか検討するべきだったかもしれません。

今回、10 日間と今までで最も長いコンテストでしたが最終日までほぼ毎日点を上げていくことができ、非常に楽しかったです。成績もプレテストの結果を見る限りこれまでのヒューリスティックコンテストで一番良く、達成感のあるコンテストでした。

HACK TO THE FUTURE 2022予選 参加記