勝敗の境界 攻撃者が常に勝つために必要な比較回数の最小値は次の通りである。
なら攻撃者、それ以外なら防御者を選ぶ。
攻撃の上界 等しい位置をまとめながら、異なる二値の代表 を探す。三つの異なる値の順序が判明すると、中央の代表の値は必ず である。それ以降は各位置を中央の代表と一度比較すれば値が分かる。
三値がそろう前は、処理済みの位置は二つのグループ に属する。新しい二位置 を組にして、まず比較する。
各組は三回以下、最後の余った一位置は二回以下で処理できる。三値すべてが現れるため、最後まで第三の値が見つからないことはない。
最初の異なる代表が見つかる前の等号の回数を とすると、最初の 位置には 回を使う。 とすると、合計は である。中央が早く分かれば残りは一位置一回なので、回数は増えない。
防御の下界 等しいと答えた位置を DSU でまとめ、各グループを未分類、低、高のいずれかに分類する。厳密な比較は常に低から高へ向くようにする。
未分類をなくして二グループだけにするには、全 位置の分類に少なくとも 回、さらに 回の併合が必要である。両者は別の比較なので合計は 回以上となる。
それ未満なら常に異なる二つの有効な数列が残る。未分類と低・高が存在するなら、(低、高、未分類) の値を または とすればよい。まだ比較していなければ任意の異なる二つの有効な数列を選ぶ。未分類がなければ低か高の少なくとも一方に二グループ以上がある。反対側を端の値に固定し、その側で値 にするグループを二通りに選ぶ。他のグループはその側の端の値にする。どちらもすべての等号と厳密な比較を保つ。
従って ならこの戦略で答え、二つの証拠数列を提出できる。
判定と計算量 ジャッジの防御者はこの戦略を使い、三グループのうち同じ分類の二つを併合できなくなった時点で、その二つに厳密な順序を与える。この時点で三グループの値は一意になる。それ以前は必ず二つの証拠があるため、単なる推測を正確に拒否できる。提出された防御者については、最後の二数列をすべての回答記録と照合する。有効な証拠があれば、途中の各時点の整合性も保証される。
攻撃は 時間・空間、防御は 時間と 空間である。インタラクタの記録は 空間を使う。すべての数値計算は符号付き ビット整数に収まる。
サブタスク 1 は 個の数列から有効なものを列挙し、残っている数列集合を状態とするメモ化ミニマックス全探索で解ける。状態数は指数的だが なら十分小さい。サブタスク 2 は上記の戦略を使う。
Solution written by GPT6