思考過程

初手
- WA（お約束）
  - 何もしない時の出力を忘れていた
初手2
- 4439点
  - とりあえず、メンバー1がタスク1から順に消化するようにしただけ
- ここまででわかったこと
  - インタラクティブなので、繰り返しで精度を上げていくことができない
    - 一回のイテレーションの中で詰めていかないといけない？！
      - え、初手の選び方どうすんだこれ？
        
        運ゲーだったりする？
        
        タスクの依存関係があるから、それほど自由度もなかったりする？
      - 1000タスクしかないのに精度上げられるのか？
      - 一回のイテレーションしかできないということは、その中で多くの処理ができるということでもある
  - 精度を上げるためにはメンバーの技能を類推しなければならない
    - 要求レベルはわかっているから、メンバーがタスクにかけた時間で所持技能の傾向はわかる
      - わかると思うけど、どれくらい詰められるのかが未知数
- ここからやるべきこと
  - とりあえず全メンバーを可能な限りアサインしていく
  - タスクの要求技能レベルの傾向を判断する
    - どうやって？
  - タスクの依存関係を速やかに解決する方法は？
    - そこは実は気にしなくてもよかったりする？
      - 計算量的に誤差の可能性
    - とりあえず、タスクAが依存するタスクのリストと、タスクAに依存するタスクのリストをマップで持っておけばgreedyでもなんとかなりそう
二投目
- とりあえずgreedy
  - 全メンバーをアサイン
  - タスクの依存関係はみる（それはそう
  - どちらも小さい方からみる
    - 以上を実装して、みんな大好き81084点を得た
    - 雑にgreedyでも63msなので、とりあえず時間計算量は大丈夫
- ここからやること
  - 所持技能の類推
    - どうやって？
    - メンバーの強さの類推ならできる？
      - 早く仕事を終わらせられるほど強いと仮定
三投目
- priority_queueを使って、終了タスクの多いメンバーを優先して採用することにした
  - 87087点
  - え、予想外に伸びたｗ
- ここからやること
  - 時間かかりすぎてるメンバーの優先度を下げる？
    - これはできそう
  - 所持技能の類推
    - これはどうやればいいのかまだわからない・・・
    - 消化した要求技能と消化日数から予測するしかないが・・・
  - 要求技能から優先順位を計る？
  - 依存関係から優先順位を計る？
    - ボトルネックを解消できるような順番で消化できるとよい
      - ただし、ほとんど待ちが発生していないっぽいので、有効性は疑問
四投目
- タスクを「子供が多い順」「難しそうな（要求技能の最大値だけ見た）タスク順」で並べ替えてみた
  - 84498点
  - 下がっとるやないかいｗ
- わかったこと
  - タスクに何らかの優先度づけをして並べ替えると、効率が上がるが空きメンバーが発生する可能性が増えそう
    - それゆえ、ボトルネックを解消できるような順番で消化することは実は思ったより有効そう
      - 今回は「子供が多い順」でボトルネックを広げたつもり
  - 直感的に、難しいそうなタスクを優先すると効率悪そうだと思ったけど、やはり悪かった
    - シード0でテストしたらこっちのほうがいい結果が出たから・・・
      - 面倒がらずにたくさんのシードでテストしろってことだ！！
- 今すぐやること
  - とりあえず「簡単そうなタスク順」に並び替えて確認してみる
- ここからやること
  - 所持技能の類推
    - 未だ全く案が浮かばない
五投目
- 84062点
- 更に下がったｗｗｗ
- （ここからしばらくぐだぐだする）
十投目くらい
- 87524点
- やっと伸びた
  - 四投目以降に実装したものは全部捨てた
    - つまりタスクに優先度をつけないように戻した
  - かわりに各メンバーの費やした時間とこなした仕事量を雑に考慮した
    - 費やした時間は少ないほうがいい
    - こなした仕事は多いほうがいい
十一投目
- 87317点
- 上記二点の評価バランスを調整しただけ
  - 減ってる・・・
  - ローカルでは微増だったんだがなー
結局十投目のやつを投げ直して終了

感想

なんかまだヒューリスティックのスタート地点にも立ててないなーっていう事実を改めて突きつけられた感じでした・・・。

Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

HACK TO THE FUTURE 2022 予選

思考過程

感想