Approach 貪欲法 + 焼きなまし法 を使いました。

  • 貪欲法
    • オーダーを並べ替える。
      • 納期が早い、数量が多い、最早開始日時が早い、(納期 - 最早開始日時) が短いオーダーを優先する。
    • 最早開始日時 から使える枠(リソースと時間のペア)を探す。
      • 同じパンの枠がある場合はその枠を優先する。
      • 同じパンの枠に追加するとき、追加した後のキャパシティの小さい枠を優先する。
      • 枠が空のとき、キャパシティの大きい枠を優先する。
  • 焼きなまし法
    • 近傍1 : オーダーを納期に間に合うように移動する。
      • 別のパンがあって、無効な移動なことがあります。
    • 近傍2 : オーダーを同じパンの別の枠に移動する。
      • 納期に間に合わなくても気にしない。
    • 近傍3 : オーダーを同じパンの別の枠のオーダーと交換する。
    • 近傍4 : ある枠の全てのオーダーを、別の枠の全てのオーダーと交換する。
      • 別の枠は、リソースはランダムで、時間は前後 ± 1。
      • 枠のオーダーの最早開始日時の最大値と数量の和を持つと、有効な交換かどうかO(1)で判定できる。
      • 時間は前後 ± 1なので、スコアの差を、事前に計算できます。
    • 近傍5 : ある枠の全てのオーダーを、同じパンの別の枠に移動する。
  • 高速化
    • 構造体のメンバーを vector にコピーして、vector を使いました。