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

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

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

012

問題に戻る

解説

勝敗の境界 攻撃者が常に勝つために必要な比較回数の最小値は次の通りである。

Q(N)=⌈3N2⌉−2.Q(N)=\left\lceil\frac{3N}{2}\right\rceil-2.Q(N)=⌈23N​⌉−2.

M≥Q(N)M\geq Q(N)M≥Q(N) なら攻撃者、それ以外なら防御者を選ぶ。

攻撃の上界 等しい位置をまとめながら、異なる二値の代表 L<HL<HL<H を探す。三つの異なる値の順序が判明すると、中央の代表の値は必ず 111 である。それ以降は各位置を中央の代表と一度比較すれば値が分かる。

三値がそろう前は、処理済みの位置は二つのグループ L<HL<HL<H に属する。新しい二位置 a,ba,ba,b を組にして、まず比較する。

  • a=ba=ba=b なら一つのグループとして LLL、必要なら HHH と比較する。合計三回以下である。
  • 異なる場合は a<ba<ba<b となるよう名前を付け、aaa と を比較する。 なら から中央が分かり、 と をもう一度比較すればよい。

各組は三回以下、最後の余った一位置は二回以下で処理できる。三値すべてが現れるため、最後まで第三の値が見つからないことはない。

最初の異なる代表が見つかる前の等号の回数を eee とすると、最初の e+2e+2e+2 位置には e+1e+1e+1 回を使う。R=N−e−2R=N-e-2R=N− とすると、合計は である。中央が早く分かれば残りは一位置一回なので、回数は増えない。

防御の下界 等しいと答えた位置を DSU でまとめ、各グループを未分類、低、高のいずれかに分類する。厳密な比較は常に低から高へ向くようにする。

  • 未分類同士なら異なると答え、一方を低、他方を高にする。
  • 未分類と低なら未分類の方が大きいと答えて高にする。高との比較は対称的に処理する。
  • 異なる低グループ同士、または高グループ同士なら等しいと答えて併合する。
  • 低は高より小さく、既に同じグループの位置は等しいと答える。

未分類をなくして二グループだけにするには、全 NNN 位置の分類に少なくとも ⌈N/2⌉\lceil N/2\rceil⌈N/2⌉ 回、さらに N−2N-2N−2 回の併合が必要である。両者は別の比較なので合計は Q(N)Q(N)Q(N) 回以上となる。

それ未満なら常に異なる二つの有効な数列が残る。未分類と低・高が存在するなら、(低、高、未分類) の値を (0,2,1)(0,2,1)(0,2,1) または (1,2,0)(1,2,0)(1,2,0) とすればよい。まだ比較していなければ任意の異なる二つの有効な数列を選ぶ。未分類がなければ低か高の少なくとも一方に二グループ以上がある。反対側を端の値に固定し、その側で値 111 にするグループを二通りに選ぶ。他のグループはその側の端の値にする。どちらもすべての等号と厳密な比較を保つ。

従って M<Q(N)M<Q(N)M<Q(N) ならこの戦略で答え、二つの証拠数列を提出できる。

判定と計算量 ジャッジの防御者はこの戦略を使い、三グループのうち同じ分類の二つを併合できなくなった時点で、その二つに厳密な順序を与える。この時点で三グループの値は一意になる。それ以前は必ず二つの証拠があるため、単なる推測を正確に拒否できる。提出された防御者については、最後の二数列をすべての回答記録と照合する。有効な証拠があれば、途中の各時点の整合性も保証される。

攻撃は O(N)O(N)O(N) 時間・空間、防御は O((N+M)α(N))O((N+M)\alpha(N))O((N+M)α(N)) 時間と O(N)O(N)O(N) 空間である。インタラクタの記録は 空間を使う。すべての数値計算は符号付き ビット整数に収まる。

サブタスク 1 は 3N3^N3N 個の数列から有効なものを列挙し、残っている数列集合を状態とするメモ化ミニマックス全探索で解ける。状態数は指数的だが N≤6N\leq6N≤6 なら十分小さい。サブタスク 2 は上記の戦略を使う。

Solution written by GPT6

LL
L
a<La<La<L
a<L<Ha<L<Ha<L<H
bbb
LLL
  • a>La>La>L なら L<a<bL<a<bL<a<b から中央が分かり、以前の HHH と aaa をもう一度比較する。
  • a=La=La=L なら bbb と HHH を比較する。等しければ既存の二グループに加え、異なれば三値が判明する。
  • e−
    2
    e+1+3⌊R/2⌋+2(R mod 2)≤Q(N)e+1+3\lfloor R/2\rfloor+2(R\bmod2)\leq Q(N)e+1+3⌊R/2⌋+2(Rmod2)≤Q(N)
    O(N+M)O(N+M)
    O(N+M)
    646464