問題の性質と焼きなまし法の適用

問題を読むと、以下の性質から焼きなまし法（Simulated Annealing）を効率的に適用できそうだと予想が立ちます。

• (0,0)から出発し、いくつか箱を拾って(0,0)まで戻る操作を1手と見なせる
  • この1手内の再計算のみでスコアの更新が済みます。
    （以下、この1手で拾う箱の集合を「グループ」と呼ぶ）
• グループの箱の数は平均4.5～5.0個程度に収まるため、スコア再計算が速い
  • これは手元で実験して予想します
• 2グループ間での1点移動、スワップなどシンプルな操作で改善を繰り返すことで良い状態へ到達できそう

スコアの再計算を差分計算によって十分に高速化でき、かつ「良い解の近傍もまた良い解である」ならば、焼きなまし法が有効なことが多いです。このため、この問題でも焼きなましで高得点が狙えると考えました。

操作したグループごとのスコア再計算、1点移動・2点スワップ（2近傍）を使って焼きなましを実装したところ、約1,850,000点が取れました。

---

コンテスト後の改善点

コンテスト後に焼きなましを改良し、1,870,000点を超えたので、得点向上に効果的だった工夫を挙げます。

スコア再計算の高速化（+1,000）

グループのスコア再計算では「移動距離」と「箱の潰れ判定」の2つが必要です。
実は、スコア計算は後ろから計算することで高速化できます。

• 箱が潰れるかの判定は d[i][j] <= 移動ごとの荷重の和
• 後ろから見ることで「今見ている箱が(0,0)に到達するまでの総移動距離」を持つことができる。

よって、移動距離*重みの和を求めておくことができ、次以降に見る箱が受ける荷重の和も持つことができます。スコア再計算は何度も呼び出されるので、かなり高速化できます。

グループのw[i][j]降順ソートの縛りを解除（+3,000）

• 降順ソートすると、重い箱から必ず拾うことになり、少ないループ数なら「動かした箱が適切な順番」になりやすく、遷移採用率が上がります
• しかし、多くのループを回す場合は「到達できない状態」が増えるデメリットの方が大きいので逆効果に。
  → ソート縛りを解除したら得点が向上しました

無駄な遷移をリジェクトしてやり直し（+5,500）

1点移動や2点スワップで「総移動距離が大きく増加してしまう」ことがあります。こういった場合は、たとえ遷移後の状態がvalidでもほぼ採用されないため、遷移操作やスコア再計算が無駄になります。

• 遷移する前に「移動距離の増減」を事前に計算し、悪化（移動距離+3以上）する場合は必ず遷移対象を選び直す
  → 無駄な遷移やスコア再計算が減り、効率化・得点向上に寄与

グループの末尾のランダムな長さをスワップ（+2,000）

• この近傍はかなり強力で、得点向上に大きく貢献しました

割り算や剰余計算をしない(+1,000)

• 実はコンピューターが割り算をしたり剰余を計算するのは遅いです。特に何千万回もループが回る時は、割り算や剰余を前計算などで代用できると高速化できることもあります。

2次元配列を1次元配列に変換して扱う場合などは特に、元座標での距離計算をするために/Nや%Nで元座標に再度変換してから距離を求める…という行為は避けたほうが無難です。前計算しましょう。