公式
E - Two Increasing Sequences 解説
by
E - Two Increasing Sequences 解説
by
sounansya
\(A\) の中で変化がある bit の中で最も上の bit を考えると、\(A\) の狭義単調増加性より \(000\ldots111\) と並んでいることが分かります。この \(0\) と \(1\) のブロックにより \(A_i \oplus X\) の大小関係が二分されます。このことを元に考えると、以下の条件が満たされない時答えは必ず No となります:
- \(P\) の Permutation Tree を考えた時に、そのノード全てが linear Node である。
以降はこの条件が満たされている場合について考えます。
Permutation Tree 上で木 DP を行います。\(d[x]\) を「頂点 \(x\) が表す \(P\) の区間のみを考えた時に、その大小関係を表現するために必要な \(x\) の下位 bit 数は最小で何 bit か」と定義します。各部分木のマージでは以下の部分問題が解ければ良いです:
- 長さ \(n\) の整数列 \(c=(c_1,c_2,\ldots,c_n)\) が与えられる。隣接 \(2\) 項 \(c_i,c_{i+1}\) を選び、それらを \(\max(c_i,c_{i+1})+1\) に置き換える操作を \(n-1\) 回行う。最終的な \(c_1\) の値の最小値を求めよ。
この問題は \(\max(c_i,c_{i+1})\) が最小な \(i\) (複数ある場合は \(i\) が最小のもの)を取りそれらをマージすれば良いです。
以上の木 DP を実装し、与えられた \(X\) で \(P\) を完全に表現できる場合は Yes、できない場合は No を出力すれば良いです。
\(X\) の先頭にある \(0\) も使えることに注意してください。
投稿日時:
最終更新:
