ABC 272 G — Yet Another mod M

考察

valid Mで同じremainder Xを持つmajority index set Sを考えると、任意のi,j∈SについてM divides |A_i−A_j|となる。

|S|>N/2なのでrandomに二indexを選んだとき両方がSに入る確率は1/4より大きく、正しいdifferenceをconstant probabilityで得られる。

棄却する候補: M=3,…,10^9を列挙してremainder frequenciesを調べる。

modulus候補範囲が大きすぎる。

採用する候補: random pairsのdifferenceをfactorizeし、その3以上のdivisorsを候補Mとして全Aのremainder majorityを検証する。

majority pairを引けば真のMがdifferenceのdivisorに現れ、反復でfailure probabilityが幾何的に減る。

candidateは推測だけで返さず、A_i mod Mのfrequencyが実際にN/2を超えるかO(N)で検証するためfalse positiveはない。

divisor closureより全divisorsの代わりにdifferenceのodd prime factorsと4だけを試しても、valid divisorがある場合のより小さいvalid candidateを拾える。

典型の発動条件

majority集合からの乱択sampling

発動条件: 未知のgood subsetが全体の半数超を占め、その中の少数sampleから答え候補を生成できるとき。

random pairを複数回選び、両方がmajority residue classに入るeventを利用する。

差の約数による合同類候補

発動条件: 複数整数が同じmodulo remainderを持つ未知modulusを探すとき。

sample differenceをfactorizeし、3以上のdivisorsまたは必要十分なprime-factor candidatesを列挙する。

問題固有の要素

入力値はdistinctなのでsampleした異なるindicesのdifferenceは正で、factorization対象0の例外を避けられる。

別の問題へ持ち帰る視点: majority構造はrandom pairが同じhidden classへ入る定数確率を与え、candidate generationのrandomizationに使える。

正当性

過半数の同余類から二要素を引けば、その差は真の法の倍数である。奇素因数または4への候補削減は同余類をさらにまとめるため、過半数条件を保つ。各候補を全要素で確かめるので誤った法を返すことはなく、失敗は有効な対を一度も引けない場合に限られる。

実装上の注意

  • 同一pair・同一factorから出るcandidateをdeduplicateし、M≥3かつM≤10^9を満たすものだけ検証する。
  • 試行回数を要求failure probabilityから決め、random generatorのindex選択で同じindexを避ける。

復習の核

  • 同じmodulo classの二値差はmodulusの倍数になるので、未知modulus候補をdifference factorizationへ移す。
  • majorityが保証するconstant hit probabilityと、候補の完全検証を組み合わせてone-sided errorにする。

計算量と制約

時間

T回sample、差の試し割りO(T√D)、候補C個の検査O(CN)、D=maxA−minA。固定Tで失敗確率を制御する。

空間

O(N+√D)、候補とfrequency。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 3 \le N \le 5000; 1 \le A_i \le 10^9; The elements of A are distinct.; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Yet Another mod M の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 乱択の成功条件と誤り確率を設計する

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: 乱択・Monte Carloアルゴリズム

    補助タグ: 素因数・約数分解

    執筆: abc-explanation-author1.1.1 / revision 3

    学習の位置

    体系上の位置: 乱択の成功条件と誤り確率を設計する

    • 乱数で選ぶ対象と成功条件を定め、誤り確率を上から評価して必要な反復回数または決定的な事後検証を設計できる。

    先に読む単元:

    • 素因数分解と約数構造 — 初歩的な素因数分解を、指数vectorと約数格子へ条件を分解する道具として発展させる。

    この解説で扱わないこと:

    • 誤り確率の評価を伴わない固定hash、および入力全体を確定的に列挙できる探索。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題