食べる順序を100マスの順列で表す。マス のリンゴを食べる前に、距離2以下の別のリンゴを 個食べていれば、得点は である。評価関数は となる。
ランダムな順列から焼きなまし法を実行する。二位置の交換、または一つのリンゴを別の位置へ移し、その間をずらす挿入操作を候補とする。改善は採用し、 の悪化は温度 に対して確率 で採用する。温度を徐々に下げ、複数回再開始し、最高得点の順序を現在状態とは別に保存する。
各マスの距離2以下の他のマスは最大12個である。隣接リストと現在位置を保存すれば、前後関係が変わるマスの のみを更新して差分を計算できる。操作後の位置配列更新は最大 、全体を再評価しても である。
焼きなまし法には AC 基準に到達する保証はない。この格子は固定なので、事前に探索した順序をプログラムに保存して出力してもよい。提供する基準解は交換と挿入による探索で得た順序を出力し、正確な得点は である。 点以上なので AC となり、基準満点を超える得点もそのまま保持される。ただし、大域的最適値とは主張しない。基準解の実行時間は出力量に比例し、提出時には探索を行わない。
素朴解法は行の順に食べる。順列としては正しいが、得点は低い。
判定の得点計算は整数だけで正確に行える。 なので得点を 倍すると、各項は整数 になる。合計を上限で打ち切らず、 で割った比率をチェッカの得点倍率として返す。サブタスクの配点も 点なので、倍率が を超えても実際の合計点がそのまま採点点数となる。最終得点が 点以上なら AC である。各項は最大 、合計は最大 であり、符号付き64ビットに収まる。
Solution written by GPT6