あれこれ考えるより、実際に愚直に求めるプログラムを実装して簡単な例から法則を見つけ出す方が速い。
N の偶奇で分かれる。
偶数(たとえば6)の時、先頭の1文字が 1~3 と 4~6 のgoodな整数列の個数は等しい。
よって、先頭の1文字が 3 のgoodな整数列の辞書順最後のものが答えとなる。
N=6 K=3 ↓ 3 6 6 6 5 5 5 4 4 4 3 3 2 2 2 1 1 1
奇数(たとえば5)の時、先頭の1文字が 1~2 と 4~5 のgoodな整数列の個数は等しい。
というわけで先頭1文字目は真ん中の 3 である。
その中で、2文字目が 1~2 と 4~5 のgoodな整数列の個数は等しい。
2文字目も 3 となる。
連鎖的に考えていくと、先頭 K 文字は 3(つまり、N+12)となる。
その後は、3 を除いた 1,2,4,5 で偶数の時と同じことが言えて、「先頭が 2 の辞書順最後」を後に繋げればよい。
N=5 K=3 ↓ 3 3 3 2 5 5 5 4 4 4 2 2 1 1 1
公式解説を読んでの自分用のメモ。
行える操作の候補数が多すぎて、簡単なケースでも「このケースは不可能っぽく見えるが、本当に不可能か?」を確認するのが 手作業でも、愚直なプログラムを実装するのでも難しい。
操作を逆から考えると上手くいく。
「どうしたらこれで上手くいくと着想できるか?」といわれると難しい。(一応、よくある解法としてセオリーの1つではあるが)
はじめから A=B の場合はもちろんOK。
操作で A にない値を作り出すことはできないので、B に A に無い値が含まれる場合はNG。
また、K=1 の場合は、数字を飛び越えることができないので別に扱う。
この場合、並び順を変えない限り、各要素の連続する個数を自由に変えられる。(0個にすることも含め)
よって、ランレングス圧縮して、B が A の部分列であればよい。
上記以外の場合、「最後の操作」を考える。
操作では Ai を Aj に上書きするため、当然、操作直後は Ai=Aj となっている。
これが B と一致するので、B では K 以下離れた2つの要素が同じである箇所が、少なくとも1つなければならない。
K = 2 A 1 2 3 4 5 B 5 5 1 2 1 ← ○: 1か5を最後に操作したと解釈できる A 1 2 3 4 5 B 5 1 3 2 1 ← ×: 最後に操作したと解釈できる要素がない。NG
最後の操作の直前では、Ai の値は何であったと仮定してもよい。これをワイルドカード * とする。
K = 2 A 1 2 3 4 5 B 5 5 1 2 1 5 5 * 2 1 最後の操作の直前の一例
操作を逆順に考え、B を A に合致させることを目指す。
たとえば * が 2 であったとすると、最後の操作と同様に K 以下離れた同じ値の一方を * にできる。
5 5 * 2 1 最後の操作の直前の一例。 5 5 2 2 1 ...であったと仮定し、 5 5 2 * 1 とできる
これは、結果的に「* を K 以下離れた値とスワップした」と解釈できる。
よって、K≥2 であれば、スワップを繰り返して好きな値を好きな位置に持っていくことができる。
A 1 2 3 4 5 5 5 2 * 1 K=2で1を左端に持っていく例 5 5 2 1 * 5 5 * 1 2 5 5 1 * 2 5 * 1 5 2 5 1 * 5 2 * 1 5 5 2 1 * 5 5 2
B に無い値(または個数が足りない値)は、* を1個消費してその値に変えなければならない。
ただ、B に無い値があるということは、B ではその分だけ、別の値が重複しているということになる。
同じ値を端に固めれば、* を作り出すことができる。
A 1 2 3 4 5 6 7 8 9 B 1 9 1 8 1 7 1 6 1 ↓ 1 1 1 1 * 9 8 7 6 ↓ 1 * * * * 9 8 7 6
これで、K≥2 の場合は、最初の取っかかりさえあれば可能だということが分かった。
距離 K 以内に同じ値がある箇所が1箇所でもあればOK、なければNGとなる。
区間DP。
本番中にも区間DPの可能性は考えていたが、 「DP[l,r] を求めるのに、DP[l,m] と DP[m,r] を統合した結果と、 DP[l,m+1] と DP[m+1,r] を統合した結果を足したら重複しちゃうな」 など謎の勘違いで行き詰まっていた。
M 個の「条件」は、一般名詞と混同しないよう「禁止条件」と表現する。
また、禁止条件で指定された [Li,Ri] の区間は「禁止区間」と表現し、区間DPで考慮中の「区間」と区別する。
DP[l,r] を求めるにあたり、
区切る場所 m を様々に変えた結果の重複を防ぐためには、何かしら、排反事象で場合分けする必要がある。
今回の場合、分ける位置 m を「区間内の最大値を置く場所」と考えると上手くいく。
以下、禁止条件は、[l,r) に内包されるもののみを考慮の対象とする。
まず、禁止条件のうち、Xi=m であるようなものがある場合、 m に最大値を置いたら、当然、内包される禁止区間 [Li,Ri] の中でも最大値になる。 したがって、m には区間最大値は置けない。
以下、Xi=m となる禁止条件が無いとする。無いなら、m に最大値を置ける。
その時の [l,r) の他の値の決め方を求めたい。
禁止区間中に m を含む禁止条件は、もう満たされている。
なぜなら、m が最大値となったため、Xi (≠m) は最大値であり得なくなったから。
残りの禁止条件は、区間 [l,m) または [m+1,r) に内包され、それぞれのDPで既に考慮されている。
この2区間は、左右独立に決められる。
ただし、「相対的な大きさ」を左右で統合するにあたり、r−l−1Cm−l を掛け合わせる必要がある。
これで求められる。DP[l,r]=r−1∑m=lf(l,r,m) となる。
上記の区間DPでネックとなるのが、「考慮中の区間 [l,r) に内包された禁止条件で、Xi=m であるものがあるか?」を、 各 (l,r,m) につき高速に判定しなければならない点である。
区間DPの時点で、l,r,m の探索に O(N3) かかり (16 ほどの定数倍がかかるが、N=500 として約 2×107)、 ほぼ O(1) で判定できなければ間に合わない。
ここで、区間 (l,r) や禁止区間 (Li,Ri) を2次元座標に落とすと、 (l,r) に内包される禁止条件というのは、右下の範囲になる。
R ^ | | r |----+---- | |ここ -+----|----> L l
N×N の2次元配列に bitset を使って
としておくと、全ての (l,r) につき、そこに内包される禁止条件で指定されている Xi の集合がわかる。
500bitを表現するのに64bit整数を9個ほど使うので定数倍は重くなるが、 l,r が小さい間はbitsetの最大桁もそんなに大きくならないことなどから、なんとか間に合う。
木から頂点を2つずつ取って距離の総和を最大化、という問題は最近のABCでも類題がある。
木の重心を必ず通るような2点を選んでいけばよい。
言い換えると、重心 c を根として、c の相異なる2つの子の部分木から、葉を1個ずつ取ってきてペアにすればよい。
(同じ部分木内の2つをペアにする、ということをしなければよい)
今回は「完全マッチングを保つ」という制約もあるため、どれでも好きな頂点を選ぶわけにはいかない。
1つの方法として、2点を結ぶパスが「マッチングに使われる辺と使われない辺が交互になる」ようなペアを取ると、
ペアを削除しても完全マッチングが保たれる。
この時、他の枝のマッチングはこのパス上の頂点のマッチングには影響しない。
◎==○--○==○--○==○--○==◎ ○==○--' `--○==○ ↓ ○==○--○==○--○==○ ○==○--' `--○==○
ペア (u,v) を「根の相異なる2つの子の部分木から、その間のパスがマッチング使用/不使用辺を交互に使うように選ぶ」という観点で考えると、 ペアの1つ u はその時点で根とマッチングしている子頂点(下記例①を根として②)の部分木から選ぶ必要がある。
① ⇙↓↘ ⇒:マッチングに使われている辺 ② ③ ⑦ →:それ以外の辺 : ⇙↘ : ④ ⑤ : :
もう1つ v は、他のどの子の部分木でもよい。
ただし、u,v いずれも、根からその頂点まで辿る時に
①→③→⑤のようにマッチングに使われない辺を2回連続で辿ることはダメ。
「子とマッチングしている頂点」からは必ずマッチングしている頂点(③に対する④)を優先して辿る必要がある。
これが保たれるようにするには、根の各子頂点(②③⑦)の部分木に対し、以下のように使用順を決めるとよい。
この帰りがけ順が、その部分木内で「マッチングに使われない辺を2回連続で通らない」ように頂点を選ぶ順番の1つの例となる。
木の重心を根と見なし、根とマッチングしている子の部分木を m、それ以外の子の部分木を C=(c1,c2,...) とする。
m,c1,c2,... のそれぞれからオイラーツアーの帰りがけ順で、その中の使用順を決めておく。
以下を N2−1 回繰り返せばよい。
この時、最後まで部分木が2つ以上残るように、部分木サイズが大きい子から使用していく。
C から1つ選ぶ際、頂点数が大きい方から取り出せる優先度付きキューを使うとよい。
最後に、m に1つだけ残った頂点と根をペアとしたものを追加して、答えとなる。