ABC 427 F — Not Adjacent

考察

列を半分に分けると、各半分の内部で隣り合う要素を選ばないように列挙できる。左右の選択をつなぐときに確かめ直す必要があるのは、総和の剰余と、分割点を挟む二要素を両方選んでいないかだけである。この二つの情報で照合し、左右の全組を試すことを避ける。

非隣接の選択だけなら、半分ずつ列挙できる

部分列は、選ぶ位置の集合として考える。空部分列も答えに含む。何も選ばなければ隣接の違反はなく、総和0は必ず MM の倍数だからである。また、値の列が等しくても、選んだ位置が異なれば別の部分列として数える。

N≤60N\leq60 では全 2N2^N 通りの選択を試せない。剰余と直前の選択状態を持つDPも考えられるが、M≤109M\leq10^9 なので、剰余全体を配列にして O(NM)O(NM) 時間を使う方法は合わない。そこで、非隣接という条件を満たす選択そのものが何通りあるかを調べる。

長さ hh の列で、隣り合う位置を選ばない選択の個数を fhf_h とする。長さ0では空選択だけ、長さ1では空選択とその要素を選ぶ場合があるので、

f0=1,f1=2f_0=1,\qquad f_1=2

である。h≥2h\geq2 で先頭を選ばなければ、残りの h−1h-1 要素を自由に選べる。先頭を選べば2番目は選べず、残りの h−2h-2 要素を自由に選べる。この二つは重ならず全選択を尽くすから、

fh=fh−1+fh−2f_h=f_{h-1}+f_{h-2}

となる。全長60ではなお約4兆通りあるが、長さ30なら f30=2 178 309f_{30}=2\,178\,309 通りに収まる。全体の有効選択は多すぎても、半分の有効選択なら列挙できることが、半分全列挙を使う理由である。

半分の選択を、剰余と境界のフラグへまとめる

k=⌊N/2⌋k=\lfloor N/2\rfloor とし、左を A1,…,AkA_1,\ldots,A_k、右を Ak+1,…,ANA_{k+1},\ldots,A_N に分ける。各半分の内部で非隣接を守った選択について、選んだ値の総和を MM で割った剰余と、分割点に接する要素を選んだかを記録する。境界の要素は左では末尾、右では先頭である。

列挙には、左から順に位置を処理する深さ優先探索(DFS)を使う。処理する半分を長さ tt の列 B0,…,Bt−1B_0,\ldots,B_{t-1} と書き、次の状態を持つ。

  • jj: 次に処理する位置。範囲は 0≤j≤t0\leq j\leq t。
  • pp: 直前の位置を選んだかを表す0または1。
  • rr: ここまでに選んだ値の総和の剰余。
  • bb: この半分の境界要素を選んだかを表す0または1。

初期状態は (j,p,r,b)=(0,0,0,0)(j,p,r,b)=(0,0,0,0) とする。j<tj<t なら、現在位置を選ばない分岐では jj を1増やし、p=0p=0 として、r,br,b はそのまま引き継ぐ。選ぶ分岐は p=0p=0 のときだけ作り、jj を1増やし、p=1p=1、r=(r+Bj) mod Mr=(r+B_j)\bmod M とする。この位置が境界要素なら b=1b=1 にし、それ以外では bb を変えない。j=tj=t へ到達したら、その選択の (r,b)(r,b) を一度記録する。

すべての位置を選ばない経路も一度だけ終端へ到達する。従って、各半分の空選択は剰余0・境界フラグ0として一度ずつ入る。長さ0の半分では、要素へアクセスする前に初期状態がそのまま終端となり、同じ (0,0)(0,0) を一度記録する。境界要素が存在しないのでフラグは0のままでよい。

右の剰余の頻度から、境界の違反だけを引く

先に右半分を列挙し、全選択の剰余を入れるリストと、そのうち先頭を選んだ選択の剰余だけを入れるリストを作る。両リストを昇順にソートしておく。剰余 yy の出現回数を、それぞれ R(y),R1(y)R(y),R_1(y) と書く。これは長さ MM の配列ではなく、二分探索で求める頻度である。具体的には、yy より大きい値の最初の位置から、yy 以上の値の最初の位置を引けばよい。

次に左半分を列挙する。ある選択の剰余を xx、左末尾を選んだかを ℓ∈{0,1}\ell\in\{0,1\} とすると、総和を MM の倍数にする右側の剰余は

y=(−x) mod M=(M−x) mod My=(-x)\bmod M=(M-x)\bmod M

である。左末尾を選んでいなければ、この剰余を持つ右の選択はすべてつなげられる。左末尾を選んでいれば、右先頭も選ぶものだけが隣接条件に違反する。従って、左の各選択について

R(y)−ℓR1(y)R(y)-\ell R_1(y)

を答えへ加える。右側を準備し終えた後なら、左の終端へ着くたびにこの加算を行え、左のリスト全体を保存する必要はない。

例えば N=2,M=5,A=(0,0)N=2,M=5,A=(0,0) では、右の全剰余リストは空選択と先頭選択の [0,0][0,0]、先頭を選んだリストは [0][0] となる。左が空なら2通りを加え、左がその要素を選ぶなら 2−1=12-1=1 通りを加える。答えは3で、空部分列、1番目だけ、2番目だけを選ぶ場合である。両側を選ぶ1組だけを除いている。

この例の [0,0][0,0] を単に [0][0] にしてしまうと、異なる位置の選択をまとめて失う。剰余が等しくても重複を残すか、値を一意にまとめる際に必ず頻度を保存する。

典型の発動条件

制約付き半分全列挙

全体の選択数が多すぎるときは、半分の長さに対する「有効な選択数」を見積もる。全maskを生成してから違反を落とすのではなく、制約を守る分岐だけを生成できれば、通常の 2N/22^{N/2} 通りよりも列挙数を減らせる。左右の全組を試さず、補数の頻度で照合できることも確認する。

境界状態による結合

列の局所制約を分割するときは、各半分の内部で保証できる条件と、分割点をまたぐ条件を分ける。本問のように隣り合う二要素だけの制約なら、左右それぞれの境界要素の選択有無で足りる。より遠い位置まで関係する制約へ、同じ1フラグだけで一般化しない。

問題固有の要素

「隣接して選べない」という条件は、結合時の注意点であると同時に、列挙数を減らす性質でもある。先頭を選んだら次の位置を選べないことから有効選択数の漸化式を立てると、N=60N=60 でも半分ずつなら扱えると分かる。

また、総和の条件は剰余へまとめられる一方、隣接条件のためには境界フラグを残す必要がある。「相手側との照合に必要な情報は何か」を、条件ごとに調べることが状態設計につながる。

正当性

DFSは、直前を選んだ場合にだけ現在位置を選ぶ分岐を禁止する。従って生成される選択はすべて半分の内部で非隣接を満たす。逆に、内部で非隣接な任意の位置集合について、その集合に属する位置だけを選ぶ分岐列が一意に存在する。このため、空選択を含む全選択を漏れも重複もなく列挙し、剰余と境界フラグを正しく記録できる。

元の列の位置集合は、左右への制限によって左右の選択の組へ一意に分かれる。各半分の内部が有効なら、新たに隣接違反を起こし得るのは分割点を挟む二要素だけである。左末尾を選ばなければ右側に追加の禁止はなく、選べば右先頭を選ぶものだけを除けばよい。左半分が空なら末尾フラグは0であり、存在しない境界による除外は起こらない。

左の剰余が xx のとき、右の剰余が (M−x) mod M(M-x)\bmod M であることは、総和が MM の倍数となる必要十分条件である。従って各左選択に対する加算 R(y)−ℓR1(y)R(y)-\ell R_1(y) は、総和と境界の両条件を満たす右選択の個数に等しい。頻度は位置集合ごとに保存されるので、等しい剰余を持つ異なる選択も別々に数えられる。全左選択について加えることで、条件を満たす部分列をちょうど一度ずつ数える。両側が空の組も一度加算され、境界フラグはともに0なので引かれない。

実装上の注意

  • N=1N=1 では左の長さが0となる。左は (x,ℓ)=(0,0)(x,\ell)=(0,0) を一度生成するので、答えは右の R(0)R(0) になる。A1=0A_1=0 なら空部分列と1要素の計2通り、A1≠0A_1\ne0 なら空部分列だけの1通りである。空列で末尾の添字を参照しない。
  • 補数は (M−x) mod M(M-x)\bmod M とし、x=0x=0 のときは0を検索する。M=1M=1 でも同じ式でよく、すべての剰余が0となって、答えは非隣接な全選択の個数 fNf_N になる。答え自体を MM で割る操作はしない。
  • 頻度の取得に使うソート済みリストでは、同じ剰余を消さない。圧縮する場合は出現回数を持つ。MM に比例する頻度配列は確保しない。
  • 答えは32 bit整数には収まらない。最終的な答えは f60=4 052 739 537 881f_{60}=4\,052\,739\,537\,881 以下で、照合途中でも左右の全組数 f302<5×1012f_{30}^2<5\times10^{12} 以下なので、加算には64 bit整数を使えば足りる。

復習の核

  • 制約付きの列挙では、有効選択数の漸化式を立ててから半分の長さで評価する。
  • 各側の内部を保証し、結合で壊れる条件に必要な境界情報だけを残す。
  • 数え上げの照合では、等しい剰余の多重度を失わない。空選択も剰余0の1通りとして生成する。

計算量と制約

時間

h=⌈N/2⌉h=\lceil N/2\rceil とし、fhf_h は考察で定義した長さ hh の非隣接選択数とする。長さ tt のDFSの状態数は、処理済み長さごとの有効選択数の総和 ∑j=0tfj=O(ft)\sum_{j=0}^{t}f_j=O(f_t) である。各遷移で剰余とフラグだけを更新するので、左右の列挙は合計 O(fh)O(f_h) 時間となる。右の2リストのソートと、左の各選択に対する二分探索を含め、全体は O(fhlog⁡fh)O(f_h\log f_h) 時間。

空間

右の全剰余リストと先頭選択リストに O(fh)O(f_h)、入力とDFSの再帰スタックに O(N)O(N) を使う。左の選択は生成のたびに照合するので保存不要であり、全体は O(fh+N)=O(fh)O(f_h+N)=O(f_h) 空間。

制約との対応

公式制約は 1≤N≤601\leq N\leq60、1≤M≤1091\leq M\leq10^9、0≤Ai<M0\leq A_i<M。実行時間制限は4秒、メモリ制限は1024 MiBである。h≤30h\leq30 より、各半分の有効選択は最大 2 178 3092\,178\,309 通りとなる。右の剰余リストだけを保存し、ソートと二分探索で照合する。剰余の範囲全体を走査・確保する処理を含まないため、MM が大きくても計算量は増えない。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Not Adjacent の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: meet-in-the-middle・半分全列挙

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

      主タグ: meet-in-the-middle・半分全列挙

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

      学習の位置

      体系上の位置: meet-in-the-middle・半分全列挙

      • 探索空間を独立に列挙できる二集合へ分け、両側の結果を照合・合成できる。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題