HACK TO THE FUTURE 2022 予選 参加記

HACK TO THE FUTURE 2022 予選

久々のヒューリスティックコン記事です。前回参加したRECRUIT 日本橋ハーフマラソン 2021〜増刊号〜で序盤に根を詰めすぎて後半虚無と化した反省を活かし、今回はのんびりと楽しむ、を目標に掲げました。

結果的に今回も10日間あるうちのラスト数日はアイデアが枯れやることがほぼなくなったのですが、初日はコーディングせずに問題文の条件を噛み砕く作業に時間を割けたり、比較的人生とコンテストを両立できたりしたので成長だと思います。

ちなみにこれまでは「○○(コンテスト名)　受験記」というタイトルにしてましたが、PAST以外はやっぱ明らかに受験ではないよなと思ったのでついに根負けして「参加記」に変えました。

問題概要

問題本文はこちら。

• あなたはプロジェクトリーダー(以降PL)。$M=20$人のメンバーに$N=1000$個のタスクを適切に割り振り、最小日数で全タスクを終えるのが目標。
• 各タスクには要求技能レベル$\bm{d}$として$K$個のパラメータがあり、各メンバーも同じく技能レベル$\bm{s}$という$K$個のパラメータを持つ。ただし$K=\rm{randint}(10,20)$で、各パラメータは0以上の整数。各タスク処理にかかる日数は、要求技能レベルと技能レベルの差分から算出される(各パラメータを比較して、要求技能レベルを上回る技能レベルが多いほど日数減、逆なら日数増)。
  より正確には、あるメンバーがあるタスクを処理する際の所要日数$t$は、
  $w=\sum_{k=1}^{K} \rm{max}(0, d_{k} - s_{k})$として$w=0$なら$t=1$日、そうでない場合$t=\rm{max}(1,w+r)$日　ただし$r=\rm{randint}(-3,3)$となる。
• PLはとても優秀なので各タスクの要求技能レベル$\bm{d}$は前もって分かるが、新任のため各メンバーの技能レベル$\bm{s}$は分からない。
• タスクには依存関係$(u,v)$が$R$個あり、$v$のタスクを始めるには$u$のタスクが終わっている必要がある。ただし$R=\rm{randint}(1000,3000)$。
• PLには毎日、その日タスクを終えたメンバーが伝えられるので、残っているタスクを手が空いているメンバーに適宜振り分けていく(誰にもタスクを振らない日があってもOK)。

タイトルと問題文を見た瞬間に過去の様々な記憶がフラッシュバックして意識を持っていかれそうになりましたが、既のところで持ちこたえました。

最終的な自分の戦略

この問題は大きく分けて、①各メンバーの技能レベル推定フェーズ、②タスクアサインフェーズに分かれます。僕は最終的に以下のような戦略をとりました(最終提出コードはこちら)。

技能レベル推定フェーズ

• 各メンバーがそれまでに処理したタスクと実際にかかった日数から各メンバーの技能レベルを推定する。推定にはNRMSD (normalized root-mean-square deviation)を使用した(つもり)。
  具体的には、メンバーの技能レベル$\bm{s}$の要素をrandint(-1,1)の乱数でぶらしながら、以下の数式を最小化する$\bm{s}$を山登り法で推定した(数式書き慣れてないので間違ってたらごめんなさい…)。
  $\rm{RMSD} = \sqrt{\frac{\sum_{i \in T_{fin}}^{} \sum_{k=1}^{K} (t_{i,k}^{actual} - t_{i,k}^{estimate})^{2}}{N_{fin}}}$ , $\rm{NRMSD} = \frac{\rm{RMSD}}{max(1,t_{max}-t_{min})}$
  $t^{actual}$が各タスクの実所要日数、$t^{estimate}$が$\bm{s}$を基に算出した当該タスクの予測所要日数、$T_{fin}$、$N_{fin}$が当該メンバーがそれまでに処理したタスク番号の集合とその要素数、$t_{max}$、$t_{min}$がそれまでの処理したタスクの最長及び最短所要日数です(後で考えるとNRMSDになってない気がする…)。

  ⇒このアイデアはTERRYさんのAHC003参加記を参考にさせて頂いたものです。技能レベル推定フェーズでどうやったら尤もらしい技能レベルを推定できるか考えた際、AHC003で強い人が似たようなことやってたよなと思い記事を漁りました。余談ですがHTTF期間中本ブログのAHC003記事にもアクセス増えてて、「みんな同じこと考えるんやなぁ。情報量少ない上に乱雑な記事ですまねぇ…」と思ってました。

• 各メンバーのスキルの初期値は全て1とするのが一番いいスコアとなったが理由は不明(初期値を大きくすると、要求技能レベルを超える技能レベルのパラメータは区別がつかなくなる(要求を1超えてようが5超えてようが、導出される予測所要日数が変わらなくなる)からズレが大きくなるのかな？)。

タスクアサインフェーズ

• タスクの依存関係を基に、あるタスクの後続タスクの階層(深さ)をBFSで算出。深さの大きさ(=後続タスクの多さ)をタスクの優先度として、優先度の高い順にタスクをソートして頭から処理していく。

• メンバーの手が空いたらすぐさま次のタスクにアサインする。休ませない(ブラック企業)。タスクは常に優先度順に処理していき、アサインするメンバーはその時点で手が空いているメンバーのうち最も要求技能レベルと技能レベルのギャップが少ないメンバーとする。

  ⇒振り返ってみると、常にタスクの優先度順に処理するのをやめて、メンバーを基準に考えて最も技能がフィットするタスクを処理させたり、メンバーを意図的に休ませてより適切なメンバーの手が空くのを待つとかした方が良かったかもしれませんね。PLとしての手腕の無さが浮き彫りになりますね。

ビジュアライズ結果

最終提出コードでseed=0のテストケースをビジュアライズしたものが以下です。

スキル推定結果は以下。ぼちぼち正しく推定できてそうに見えます。

コンテスト中の思考/試行記録についても書こうと思ったのですが、力尽きました。もしかしたら後で加筆するかもしれません。

まとめ

HTTF2022予選、700位まで飛び賞でプレゼントがあったり、ちょっとした改善でいいスコアが出るように工夫されていたりと、新規参入者を増やそうという試みが随所に感じ取れました。実際700人以上が参加されたようで、マラソンコンテストとしては大盛況だったように感じています。開催ありがとうございました。

AHC003と似てる気はしてましたが、途中からeivourさんがトップ争いをしてるあたりで、「あっこれ統計強い人が勝つやつか？」って思ってました。まだ読めてませんがeivourさんの解説記事にも後で目を通そうかと思います。

ここのところAtCoderで企業主催のヒューリスティックコンが増えてきたり、就活に役立つのでは説が流れていたりで明らかに競プロerのマラソン参加意欲が高まっているように見受けられます。喜ばしいですね。これからどんどん優秀な若者が参入してきて…レート上がりにくくなるやんけ！やめてくれ！！！(カス)

以上です。