AtCoder Regular Contest 171 B,C,D問題メモ

AtCoder Regular Contest 171

B - Chmax

• $(1,2,...,N)$ の順列 $P$ に対して、以下を $F(P)$ と定義する
  • 数列 $B=(1,2,...,N)$ で初期化する
  • $B_i$ のうち、$B_i \lt P_{Bi}$ を満たす $i$ のうち最小のものを $j$ とし、$B_j←P_{Bj}$ に置き換える
  • 置換ができなくなるまで繰り返した時の $B$ を $F(P)$ とする
• 長さ $N$ の数列 $A=(A_1,...,A_N)$ が与えられるので、$F(P)=A$ となるような $P$ の個数を求めよ
• $1 \le N \le 2 \times 10^5$
• $1 \le A_i \le N$

文章としては複雑だけど、要は $B$ の各要素に対して $b→\max(b,P_b)$ という置換を繰り返していけばよい。

i  1 2 3 4
P  2 4 3 1  に対するF(P)の求める手順

B  1 2 3 4
            ... B[1]=1  <  P[B[1]]=2  なので、B[1]←2に置換
B  2 2 3 4
            ... B[1]=2  <  P[B[1]]=4  なので、B[1]←4に置換
B  4 2 3 4
            ... B[2]=2  <  P[B[2]]=4  なので、B[2]←4に置換
B  4 4 3 4
            ... もう置き換えられるものはないので、終了

まず、B は必ず大きい値に置き換えられるので、 初期状態 $B=(1,2,...,N)$ のうち、$A_i \lt B_i$ となるものがあったら無理。（0通り）

そうでない場合、$A$ にはいくつかの同じ値が含まれている。それ毎にグループ化する。

i  1 2 3 4 5 6 7 8
A  6 6 8 4 5 6 8 8

   6 6       6
       8       8 8
         4
           5

置換配列 $P$ は順列なので、異なる $i$ から同じ数字 $P_i$ に置換できない。
例えば上記では、1→6 と 2→6 という“直接の”置換を両立するような $P$ は存在しない。

置換の法則から、値の位置 $i$ によらず、ある時点の $B_i$ と $B_j$ が同じ値ならその後同じ変化をし、最終的に同じ値に行き着く、という点は重要。 また、置換は値が大きくなる方向にのみ行われる。

よって、必ず 1→2→6 というように、小さい方から同じ値になるindexを辿って置換されていく必要がある。
すると、$P$ に求められる条件が決まってくる。

グループ6に着目して、あり得るPとして決まった箇所

i  1 2 3 4 5 6 7 8
P  2 6       ^        
             6以下の値

グループの中で最大の位置は、置き換えられてはいけない。
例えば、上記で $P_6=7$ だったりすると、$P_1,P_2$ も7まで置換が進んでいないとおかしいことになる。
よって、$i \ge P_i$ という制約がかかる。

同じ理由から、各グループの最大の位置 $i$ について $i=A_i$ でない場合、答えは0通りとなる。

以下、$A$ はそれを満たすとする。

グループ6と同様に、他のグループについての制約を全て適用すると、以下のようになる。

i  1 2 3 4 5 6 7 8
P  2 6 7 ^ ^ ^ 8 ^
         4 5 6   8  ←○以下の値しか入れられない、という制約

まだPに使われていない値: 1,3,4,5

まだPに使われていない値は、各グループで一番左の $i$ となる。

各グループの中で最大の位置 $I=\{4,5,6,8\}$ に、使われていない値 $R=\{1,3,4,5\}$ を、 $i \ge P_i$ となるように埋める方法の個数が、答えとなる。

$R$ の大きい方から埋められる箇所の個数を求めていけばよい。

r=5  置けるIの箇所は3箇所  →  3
r=4  置けるIの箇所は4箇所だが、1箇所は既に埋まっている  →  3
r=3  置けるIの箇所は4箇所だが、2箇所は既に埋まっている  →  2
r=1  置けるIの箇所は4箇所だが、3箇所は既に埋まっている  →  1

3*3*2*1 = 18 通り

$O(N)$ や $O(N \log{N})$ で解ける。

Python3

C - Swap on Tree

• $N$ 頂点の木があり、最初、頂点 $i$ にコマ $i$ が置かれている
• 以下の操作を0回以上、好きな回数おこなえる
  • 辺を1つ選び、両端に置かれているコマを入れ替える
  • その後、選んだ辺を削除する
• 操作後の頂点 $1,2,...,N$ に置かれたコマを $A=(a_1,...,a_N)$ としたとき、$A$ としてあり得るものの個数を $\mod{998244353}$ で求めよ
• $1 \le N \le 2 \times 10^5$

操作によって木は分断され、その後2つの連結成分内のコマは入れ替わることはない。

よって、ある辺を使う場合と使わない場合では、別の $A$ となる。

①--②--③--④--⑤--⑥

③-④の辺を選ぶ場合
  ①②③頂点にあるコマの集合は、「①②③から2個と、④⑤⑥から1個」
  ④⑤⑥頂点にあるコマの集合は、「④⑤⑥から2個と、①②③から1個」

③-④の辺を選ばない場合
  ①②③頂点にあるコマの集合は、「①②③」
  ④⑤⑥頂点にあるコマの集合は、「④⑤⑥」

また、ある頂点 $v$ から出る辺について、異なる順で選んだ操作列で $A$ が同じになることはない。

雑な証明

①--②--③--④--⑤  操作列（選んだ辺の列）が決まっていて、
        ｜          その中で ③-②, ③-④, ③-⑥ がともに出てくるとする
        ⑥--⑦      （各辺を  (2)    (4)    (6)  と呼ぶことにする）

(2)→(4)→(6) の順に操作  ①--③--⑥--②--⑤
                                  └--④--⑦

(6)→(4)→(2) の順に操作  ①--④--②--⑥--⑤
                                  └--③--⑦

頂点を  ③、①②、④⑤、⑥⑦グループに分ける。
それぞれG3   G2    G4    G6   とする。

最初 G3,G2,G4,G6 の頂点集合にあったコマの集合は
たとえば (2)→(4)→(6) の順に操作した場合、以下のように移動する
  G3から1頂点→G2に移る
  G2から1頂点→G4に移る
  G4から1頂点→G6に移る
  G6から1頂点→G3に移る

（省略するが本来は、以上で $A$ が異なる条件は全てであるという証明も必要。公式Editorial参照。帰納法でできるみたい）

頂点 $v$ について、「$v$ から出る辺のうち、どの辺がどの順で選ばれるか」のパターンを $P(v)$ とする。
矛盾しないように定めることができる全頂点のパターンの組 $(P(1),P(2),...,P(N))$ の個数が、求めるものとなる。
（※矛盾しない＝全ての辺 $(u,v)$ について、$P(u)$ と $P(v)$ で辺 $(u,v)$ を選ぶ/選ばないが一致している）

根を適当に決めて、以下のDPをする。

• $DP[v,k]=$ 頂点 $v$ 以下の部分木に含まれる全頂点についての矛盾しないパターンの組 $(P(v),P(w),P(x),P(y),...)$ の個数
  • ただし $v$ の親への辺については未考慮でよい
  • 親で $v-親$ 間の辺を考慮する時に必要なため、$v$ の子頂点への辺を何個選ぶか（$k$）で場合分け

     (v)
   ／ | ＼
 (w) (x) (y)
  :   :   :

$DP[v]$ を計算するため、以下のDPをする。

• $DP2[i,k]=v$ の $i$ 番目の子まで考慮して、そのうち $k$ 個を選んだ状態の暫定の $DP[v,k]$

        k:0  1  2  3
DP2[0] = [1, 0, 0, 0] と初期化する。kはvの子の数まで用意する。

子頂点を1つずつ採用/不採用を決めていく。

1つめの子の DP[w] = [5, 9, 3] だとして、

辺 v-w を選ぶ場合の係数:
  DP[w,k] で子を k 個選んでいる中の、どこに v-w 辺を挿入するか、という場合分けが増える。
  k に対して (k+1) 通りなので、
  
  t = Σ_k( DP[w,k] * (k+1) ) = 5*1 + 9*2 + 3*3 = 32
  
辺 v-w を選ばない場合の係数:
  v-w 辺を選ばない場合には、k での場合分けは不要。単純に w 以下の決め方となる。
  
  s = sum(DP[w]) = 17


DP2[0] から DP[1] の遷移は、↓選ばない場合 s 倍、↘選ぶ場合 t 倍となる。

DP2[0] = [1,  0,  0, 0]
  ↓
DP2[1] = [17, 32, 0, 0]

他の子についても同様に遷移していき、最終的に $DP2[vの子の数]$ が得られる。

ここに、各 $k$ につき子の選び順 $k!$ をかけたものが、$DP[v]$ となる。

全体を $O(N^2)$ で計算できる。

二乗の木DPは、各頂点に付き「部分木の頂点数」分の配列を持ってマージしていっても $O(N^2)$ で収まるという理論だが、 この問題では、各頂点に付き「子の頂点数」分の配列しか不要だし、マージも子ごとに独立に計算できるので、 ランダムなケースでの平均計算量はより少なく済む。

1つの根が $N-1$ 個の子を持つようなヒトデグラフなど、特殊な場合の最悪計算量として $O(N^2)$ かかる感じ。

Python3

D - Rolling Hash

• 非負整数列 $X=(x_1,...,x_n)$ に対して、以下を $hash(X)$ とする
  • $hash(X) = (x_1 B^{n-1} + x_2 B^{n-2} + ... + x_n B^0) \mod{P}$
  • つまり、$B$ を基数、割ってあまりを取る数を $P$ としたローリングハッシュ
• $M$ 個の区間 $(L_i,R_i)$ が与えられる
• 次の条件を満たす、長さ $N$ の非負整数列 $A=(A_1,...,A_N)$ があるか判定せよ
  • 全ての区間について、$hash((A_L,A_{L+1},...,A_R)) \neq 0$ である
• $1 \le N ale 16$
• $1 \le B \lt P \le 10^9$
• $P$ は素数

以下、添字が合わないのが気持ち悪いので、$A$ の添字を0始まりとし、 ローリングハッシュも逆に（先頭が下の位になるように）計算することにする。

• $hash(A) = (A_0B^0 + A_1B^1 + ... + A_{n-1}B^{n-1}) \mod{P}$

クエリ $L,R$ も、元の位置から、逆転させたこの並びの位置に対応させれば、元の問題と変わらない。

先頭からこれの累積和を取ったものを $C$ とすると、

C[-1] = 0                     （便宜的にC[-1]を0とする）
C0    = A0B^0
C1    = A0B^0 + A1B^1
C2    = A0B^0 + A1B^1 + A2B^2
 :    :
C[N-1]= A0B^0 + A1B^1 + A2B^2 + ... + A[N-1]B^(N-1)

区間 $(L,R)$ を抜き出した文字列のハッシュは、$C$ を使って表せる。

• $hash(A_L～A_R) = \dfrac{C_R - C_{L-1}}{B^{L}}$

$P$ が素数で $\dfrac{1}{B^{L}} = B^{-L} \not\equiv 0 \mod{P}$ なので、modで考えても上の式がゼロ除算で計算できなくなることはない。

よって、これが0になる時というのは、$C_R \equiv C_{L-1} \mod{P}$ のときに限られる。

つまり、$C[-1]$ も合わせて全部で $N+1$ 個の頂点があって、 「こことここは同じになってはいけない」という条件が $M$ 個与えられる、と考えられる。

これは、グラフの頂点彩色の問題に言い換えられる。

• グラフ彩色#頂点彩色

$A$ にはどんな数でも置けるので、上手く調整すれば $C$ の各項は $0 \le C_i \le P-1$ の $P$ 個の値を好きに設定できる。
（言い換えると、各要素が $0 \le C_i \le P-1$ である任意の $C$ に対して、対応する $A$ が存在する）

ここで、もしグラフを塗り分けるのに $P+1$ 以上の色が必要となった場合、どうしてもどれかは被ってしまい、アウトとなる。
逆に $P$ 色以下なら、可能となる。

頂点彩色数は、bitDPで $O(N2^N)$ や $O(3^N)$ で計算できる。

• 彩色数を求めるアルゴリズム - Learning Algorithms

$P$ の制約はやたらでかいくせにほとんどの場合Yesで、求めるのが難しいのは $P \le 13$ の時のみという、なかなか癖のある問題。

Python3