Official

E - Gaps of 1 or 2 Editorial by maspy

ヒント → https://atcoder.jp/contests/arc190/editorial/11715

[1] 方針

まずは区間クエリを無視して，\(Q=1\), \(L=1\), \(R=N\) の場合を考えます．

この問題は次のようにして，グラフの最大マッチング問題として定式化できます．

座標 \(i\) に \(A_i\) 個の頂点がある．\(1\leq j-i\leq 2\) のときに，座標 \(i\) にある頂点と座標 \(j\) にある頂点を辺で結ぶ．このようなグラフの最大マッチングの大きさを求めよ．

これを Tutte-Berge formula により求めることを考えます．頂点集合 \(U\) を適切に選んで \(\mathrm{odd}(G-U)-|U|\) を最大化する問題を解けばよいです．

この際，最適解で次の性質を満たすものが存在することを証明することができます：同じ座標の頂点は「すべて \(U\) に含まれる」か「すべて \(U\) に含まれない」のどちらかである．

このことは，座標 \(i\) 以外の頂点を \(U\) に含めるか否かを固定して，座標 \(i\) にある頂点を \(U\) に含める個数を \(0\) 個から \(A_i-1\) 個まで増加させていくことを考えると証明できます．

結局，各座標について「\(U\) に含める」「\(U\) に含めない」のどちらかを選ぶという \(2^N\) 通りのうちで最適なものを求める問題を解けばよいことになります．

[2] 計算の詳細

座標 \(i\) にある頂点を \(U\) に含めるとき \(u_i=1\), \(U\) に含めないとき \(u_i=0\) と定めることで，\(0,1\) からなる列 \((u_1,\ldots,u_N)\) を定めましょう．

簡単のため \(u_0=u_{N+1}=1\) などとしておきます．

考えるべき列 \((u_i)\) およびそれに対する \(\mathrm{odd}(G-U)-|U|\) の計算は次のようにできます：

  • \((u_i)\) は連続部分列 \((0,1,0)\) を含まないとしてよい．
    • この \(1\) を \(0\) に置き換えても損にならないため．
  • \(u_i=1\) のときに \(-A_i\) 点を得る．
    • \(-|U|\) に対応する．
  • \(u_{i-1}=1, u_i=0, u_{i+1}=1\) のときに \(+A_i\) 点を得る．
    • 孤立点（奇成分）が \(A_i\) 個できるため．
  • \(u_{L-1}=1\), \(u_L=\cdots=u_R=0\), \(u_{R+1}=1\), \(R>L\) のときに，\(A_L+\cdots+A_R\) が奇数ならば \(1\) 点を得る．

\(A_i=0\) であるような \(i\) がある場合には，上の式では厳密に \(\mathrm{odd}(G-U)-|U|\) という計算式に従っていない場合があります．しかしこの場合にも \(A_i=0, u_i=0\) であるときに前後の連結成分を連結させてしまって考えても得することがないことなどから，上のように計算して問題ないことが確かめられます．

列 \((u_i)\) を手前から順に定めることを考えます．\(u_i\) の値の他に，末尾に連続して並ぶ \(0\) や \(1\) の個数が \(2\) 個以上であるか否か，\(0\) が並ぶ部分の \(A\) の総和の偶奇などを状態として持つことで，本問題の答が状態数が \(O(1)\) 個の dp により \(O(N)\) 時間で計算できることが分かります．

[3] クエリへの対応

上で述べた dp による答の計算は，\(i=1,2,\ldots,N\) の順にベクトルに適当な行列をかけていく形で記述できます（max-plus semiring 上でのベクトル・行列です）．よって区間クエリに答えるにはセグメント木を使えばよいです．

dp が \(K\times K\) 行列により表される場合，セグメント木で \(K\times K\) 行列の行列積を扱うことで，\(O((N+Q\log N)K^3)\) 時間で本問題を解くことができます．writer の実装では \(K=5\) にとっており，この計算量は十分高速です．

なお本問題では列 \(A\) が変化しないことから，セグメント木に更新は行われません．求値クエリは行ベクトル \(X\) と行列 \(M_1, \ldots, M_n\) に対する \(XM_1\cdots M_n\) の計算という形で記述できますが，これは左から順に計算することで，（「行列行列積」ではなく）「ベクトル行列積」の反復で計算できます．これを行った場合の計算量は \(O(NK^3+QK^2\log N)\) で，\(K\) を writer 解よりもすこし大きくとってしまった場合でも正答を得ることができると思います．他にもセグメント木の代わりに遷移表列が疎であることと分割統治を利用する高速化もあります．

[4] コメント

Tutte-Berge formula は，一般グラフ最大マッチングという題材について学べば必ず見るであろう有名な定理ですし，ご存知の方も多いと思います．この定理と dp を組み合わせることで最大マッチングを計算するというアイデアもきわめて自然なものに感じます．

しかしこれまで私は，競技プログラミングでそのような解法を見たことがありませんでした．類似手法を用いることが想定された問題をご存知でしたら，教えてくれるとうれしいです．

posted:
last update: