DOJ logoDOJ
問題
最近追加された問題保存した問題Workbooks
カテゴリDLCコンテストグループチーム掲示板
ランキング
正解数ランキングストリークランキングDOJ Powerランキング
提出状況
問題募集ログイン新規登録
DOJ logoDOJ

OI形式のサブタスク採点、Eloレーティング、Discord連携を備えたオンラインジャッジです。

問題
問題一覧カテゴリ
コミュニティ
コンテストランキング掲示板お知らせ外部のコンテストを開催するガイド
アカウント
ログイン新規登録ジャッジ状態
ポリシー
利用規約DLCの利用規則プライバシーAPI 文書言語ランタイムコンテストの順位報酬レーティングとパフォーマンス
© 2026 DOJ
All rights reserved
解説

リンゴを食べよう

問題に戻る

解説

食べる順序を100マスの順列で表す。マス vvv のリンゴを食べる前に、距離2以下の別のリンゴを kvk_vkv​ 個食べていれば、得点は 100⋅0.9kv100\cdot0.9^{k_v}100⋅0.9kv​ である。評価関数は ∑v100⋅0.9kv\sum_v100\cdot0.9^{k_v}∑v​100⋅0.9kv​ となる。

ランダムな順列から焼きなまし法を実行する。二位置の交換、または一つのリンゴを別の位置へ移し、その間をずらす挿入操作を候補とする。改善は採用し、ddd の悪化は温度 TTT に対して確率 exp⁡(−d/T)\exp(-d/T)exp(−d/T) で採用する。温度を徐々に下げ、複数回再開始し、最高得点の順序を現在状態とは別に保存する。

各マスの距離2以下の他のマスは最大12個である。隣接リストと現在位置を保存すれば、前後関係が変わるマスの kvk_vkv​ のみを更新して差分を計算できる。操作後の位置配列更新は最大 O(100)O(100)O(100)、全体を再評価しても O(100⋅12)O(100\cdot12)O(100⋅12) である。

焼きなまし法には AC 基準に到達する保証はない。この格子は固定なので、事前に探索した順序をプログラムに保存して出力してもよい。提供する基準解は交換と挿入による探索で得た順序を出力し、正確な得点は 6391.44590319386391.44590319386391.4459031938 である。6391.46391.46391.4 点以上なので AC となり、基準満点を超える得点もそのまま保持される。ただし、大域的最適値とは主張しない。基準解の実行時間は出力量に比例し、提出時には探索を行わない。

素朴解法は行の順に食べる。順列としては正しいが、得点は低い。

判定の得点計算は整数だけで正確に行える。0≤kv≤120\le k_v\le120≤kv​≤12 なので得点を 101210^{12}1012 倍すると、各項は整数 100⋅9k になる。合計を上限で打ち切らず、 で割った比率をチェッカの得点倍率として返す。サブタスクの配点も 点なので、倍率が を超えても実際の合計点がそのまま採点点数となる。最終得点が 点以上なら AC である。各項は最大 、合計は最大 であり、符号付き64ビットに収まる。

Solution written by GPT6

v⋅1012−kv100\cdot9^{k_v}\cdot10^{12-k_v}
100⋅9kv​⋅1012−kv​
6391.46391.46391.4
6391.46391.46391.4
111
6391.46391.46391.4
101410^{14}1014
101610^{16}1016