ABC 308 E — MEX

考察

真ん中の E の位置を決めると、左の M と右の X はそれぞれ自由に選べる。同じ値を持つ位置は mex への寄与が等しいので、左右にある値ごとの個数を掛け合わせれば、多数の三つ組をまとめて数えられる。

求めるのは、添字が i<j<ki<j<k の順に並び、対応する文字が M、E、X となる三つ組の寄与の総和である。全三つ組を調べると時間は O(N3)O(N^3) となり、間に合わない。そこで、順序条件を左右に分けられる中央の添字 jj に注目する。SjS_j が E なら、ii は左側の M、kk は右側の X から選ぶ。どの左候補とどの右候補を組み合わせても順序条件を満たすため、左右の選択に依存関係がなくなる。

残る寄与は mex⁡(Ai,Aj,Ak)\operatorname{mex}(A_i,A_j,A_k)、つまり三つの値に含まれない最小の非負整数である。jj を固定したとき、左右の候補について必要なのは添字そのものではなく、その位置の値だけになる。しかも値は 0,1,20,1,2 の3種類しかない。値 aa を持つ左の M の個数を L[a]L[a]、値 bb を持つ右の X の個数を R[b]R[b] とすると、左右の値が (a,b)(a,b) になる三つ組は L[a]R[b]L[a]R[b] 個であり、すべて同じ mex を持つ。この jj の寄与は次の9組の和になる。

∑a=02∑b=02L[a]R[b]mex⁡(a,Aj,b)\sum_{a=0}^{2}\sum_{b=0}^{2} L[a]R[b]\operatorname{mex}(a,A_j,b)

例えば、独自の小例として文字列が MMEXXX、数列が (0,0,1,2,2,0)(0,0,1,2,2,0) の場合を考える。中央の E の値は1で、左には値0の M が2個、右には値2の X が2個と値0の X が1個ある。左右の値が (0,2)(0,2) となる選び方は 2×2=42\times2=4 個で、それぞれの mex は3。(0,0)(0,0) となる選び方は 2×1=22\times1=2 個で、それぞれの mex は2である。従って寄与は 4×3+2×2=164\times3+2\times2=16。値が同じ位置も別々の選択肢なので、頻度の積が必要になる。

すべての jj について頻度を調べ直す必要はない。最初に全体の X を値別に数えて RR へ入れ、LL はすべて0にする。添字 jj を左から右へ進め、各位置で次の順に処理する。

  1. SjS_j が X なら、R[Aj]R[A_j] を1減らし、現在位置を右側から外す。
  2. SjS_j が E なら、LL と RR を使って上の9組の寄与を答えに加える。
  3. SjS_j が M なら、L[Aj]L[A_j] を1増やし、次の位置から左側の候補にする。

この順序なら、寄与を計算するときの LL は現在位置より左、RR は現在位置より右の候補を表す。mex は0から3までを順に調べ、三つの値に含まれない最初の数を返せば定数時間で求まる。9組の集計を各 E で行い、加えた総和が答えとなる。

典型の発動条件

中央要素固定のtriplet counting

順序付き三つ組の集計では、中央を固定したときに左右を独立に選べるかを調べる。寄与が両端の少数の属性だけで決まるなら、左右の属性別頻度の積へ集約できる。両端の距離など、左右を結び付ける条件が残る場合は、そのまま積に分けられない。

小さい値域の全組表

候補の個数が多くても、答えに影響する値の種類が少なければ、値の組を列挙して頻度を掛ける。本問では中央の値を固定した後の組は9通りである。mex を繰り返し計算する代わりに、三つの値の全27通りを前計算してもよい。

問題固有の要素

文字は「左の M・中央の E・右の X」という役割を決め、数列の値は寄与を決める。この二つを分けて考えると、位置の順序は走査で、値への依存は長さ3の頻度配列で扱える。MEX という文字条件と mex という関数の定義を混同しない。

正当性

各位置で X を右側から外し、寄与を集計した後に M を左側へ加えるため、E の位置を処理するとき、L[a]L[a] はその左にある値 aa の M の個数、R[b]R[b] はその右にある値 bb の X の個数である。従って各値の組に対する L[a]R[b]L[a]R[b] 個の選択はすべて順序条件を満たす。

有効な三つ組には中央の E と左右の値の組が一意に定まるため、対応する集計でちょうど一度数えられる。同じ集計に含まれる三つ組は mex が等しいので、頻度の積にその mex を掛ければ寄与の総和になる。候補のない値の組は頻度が0となり、全体を足せば漏れや重複なく答えを得られる。

実装上の注意

  • X を右側から除く→E の寄与を計算する→M を左側へ足す、の順序にすると、厳密な不等号 i<j<ki<j<k と配列の意味を対応させやすい。
  • mex⁡(0,1,2)=3\operatorname{mex}(0,1,2)=3 もありえる。候補は0から3まで調べる。
  • 三つ組の数は最大で (N3)\binom{N}{3}、各寄与は高々3である。積を計算する前に64 bit整数へ変換し、答えも64 bit整数で保持する。

復習の核

  • 三つ組の総和では、中央を固定して左右の選択を切り離せるかを考える。
  • 添字の区別を頻度へまとめても、選択肢の個数は失わない。同じ値の位置も頻度の積で別々に数える。

計算量と制約

時間

O(N)O(N)。全 X の集計と左からの走査に線形時間を使い、各 E では固定9組を定数時間ずつ評価する。

空間

入力の数列と文字列の保持に O(N)O(N)、頻度配列などの補助領域に O(1)O(1)。

制約との対応

3≤N≤2×1053\leq N\leq2\times10^5、Ai∈{0,1,2}A_i\in\{0,1,2\}。値域が3種類であることが、各位置を定数時間で処理できる理由である。MEX となる三つ組がなければ加算されず、答えは0になる。実行時間制限は2秒、メモリ制限は1024 MiB。

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 局所寄与へ分解して集計順を交換する

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

      主タグ: 寄与の数え上げと順序交換

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

      学習の位置

      体系上の位置: 局所寄与へ分解して集計順を交換する

      • 数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。

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

      • active集合を時刻・座標順に更新するevent sweep、更新列を逆から読むだけの処理、および成分ごとの解を単に掛け合わせる構造判定。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題