AtCoder Regular Contest 108 C,D,E,F問題メモ

AtCoder Regular Contest 108

C - Keep Graph Connected

• $N$ 頂点の連結な無向グラフが与えられる
• 辺にはコスト $c_i$ が付いている
• 以下の条件を満たすように頂点に番号を付けたい
  • 辺のうち、「それが結ぶ2頂点のちょうど片方だけに辺と同じ番号が付いている」ものだけを残す
  • 残した結果でも、グラフは連結を保っている
• 可能か判定し、可能なら頂点への番号の付け方の一例を構築せよ
• $2 \le N \le 10^5$

必ず可能である。騙されるな。

頂点とそれを結ぶ辺があって、辺のもう片方の頂点番号が決まっていたとしても、頂点の番号を自由にいじることで辺は残せるので、グラフは連結が保たれる。

頂点     もう片方
 ○---(3)---３        →  3以外の番号にする
 ○---(3)---４        →  3にする

なので、適当に1頂点を決めて、辺を伝って貪欲にまだ決まっていない頂点番号を決めていくことで、必ず連結にできる。

Python3

D - AB

• 文字列 $S$ は、はじめ'AB'である
• 4つの文字 $a,b,c,d$ が与えられる。それぞれ'A'か'B'のいずれかである
• $S$ に対して以下の操作を好きな順で繰り返し行う
• 操作
  • 好きな'AA'を'AaA'に置換する
  • 好きな'AB'を'AbB'に置換する
  • 好きな'BA'を'BcA'に置換する
  • 好きな'BB'を'BdB'に置換する
• 長さが $N$ になった時にあり得る $S$ の個数を $\mod{10^9+7}$ で求めよ
• $2 \le N \le 1000$

なんか $a,b,c,d$ が決まってると楽だなーと思いつつ、でも実は組み合わせは16通りしか無いことに気付く。

じゃあ場合分けできそう。

最初はbの操作しかできないのでそこから考える。 場合分けは、なんかこう決めたら都合よく場合が限定されそう、という部分から決めていくのがセオリー（多分）。 RPGのマップで宝箱を取り逃さないために、行き止まりっぽい方から調べるのと同じ。

たとえば b='A' なら 'AAB' になる。

もし、ここで a='A' ならa,bどちらを使っても'AAA…AB' にしかできない。cやdは使う機会さえ無く、1通り。

a='B'なら'ABAB'にでき、cが使えるようになる。

ここで、c='A'なら、'BB'という連続した'B'を作ることができない。 逆にその制約さえ守っていれば、最初に好きなだけ'AAA…AB'と並べておいて、'B'を好きな位置に挿入することで作れる。

最初は'A'、最後が'B'、'B'が連続しない、という制約での並べ方は簡単なDPを用いて求められる。

• $DP[i][j:0/1]=i$ 文字目まで、末尾が $j=0$:'A'、$j=1$:'B'の場合の並べ方

さて、最後にc='B'の時、'BB'を作れる。

この場合はほぼ任意の文字列を作れる。最初に必要なだけ'A'を並べておいて、'B'を好きな位置に挿入して好きなだけ拡張できる。
ただし、最後から2文字目は'A'から変えることができない。最初、最後も除いて $N-3$ 文字を自由に決められるので、$2^{N-3}$ となる。

b='B'の時も、前後と'A','B'を反転させれば同様に考えられる。

これで、場合分けが済んだ。

if b='A':
  if a='A': 1通り
  if a='B':
    if c='A': Bが連続しないパターン数
    if c='B': 2^(N-3)
if b='B':
  if d='B': 1通り
  if d='A':
    if c='B': Aが連続しないパターン数
    if c='A': 2^(N-3)

Python3

E - Random IS

• $1～N$ の順列 $A_1～A_N$ がある
• 「採用しても増加部分列が崩れない要素の中から等確率で1つ採用する」操作を繰り返して、増加部分列を作る
• 採用できるものがなくなったら操作を終了する
• 増加部分列の長さの期待値を、$\mod{10^9+7}$ で求めよ
• $1 \le N \le 2000$

A:  2 5 3 1 4
    2            確率 1/5 で 2 を採用
    2     x      1 は増加部分列にならなくなるためもう選べない
    2     x 4    確率 1/3 で 4 を採用
    2 x   x 4    5 は増加部分列にならなくなるためもう選べない
    2 x 3 x 4    確率 1/1 で 3 を採用
                 このような操作をした場合の最終的な長さは3となった

他の操作も含めると、この場合の答えは 266666671 (= 37/15) となる

こんな短いくせして意外と複雑な値になるじゃねえかおめえ……

最終的に出来上がる増加部分列が同じであっても、その選ぶ順番によって生成確率が異なる。

たとえば上記の例では、最初に2、次に $\dfrac{2}{3}$ で3か4を採用することで「2 3 4」が確定するが、もし最初に3を選ぶとそれだけで1,5が除外されて「2 3 4」が確定する。
どうにも完成形で分類しての計算は難しそう。

また、主客転倒でよくあるような「各 $A_i$ について、増加部分列に採用されて答えに寄与する確率」を求める方法もありそうだが、 確率を求めるには結局「それがいくつの候補の中から採用されたのか」というのが必要となる。

このためにまとめての計算、たとえば自身の左側/右側を独立に処理するなどができない。
直近の左/右で採用済みの数字を $A_l,A_r$ とすると、 あり得る $l,r$ のペアそれぞれについて試さないと無理そう（上手い方法があるのかも知れないが）。

• $DP[l][r]=A_l$ と $A_r$ を採用することが決まっている場合の、その間で採用する個数の期待値
  • 番兵として、最初に $A_0=0$、最後に $A_{N+1}=N+1$ を置くと、$DP[0][N+1]$ が答え

以下のように更新できる。

• $(l,r)$ 間で採用可能な（$l \lt j \lt r$ かつ $A_l \lt A_j \lt A_r$ であるような）$j$ の集合を $M$ とする
• もしある $j$ を採用すると、次なる状態は区間 $(l,j)$ と $(j,r)$ に分割される
  • つまり、$DP[l][j]+DP[j][r]+1$ を求め、この全 $j$ についての和を $|M|$ で割った値で更新できる
  • $\displaystyle DP[l][r]=\frac{1}{|M|}\sum_{j \in M}(DP[l][j]+DP[j][r])+1$

        l                      r
i: ...  3  4  5   6  7  8  9  10  ...
A: ...  5  2  7  11  9  1  8  10  ...

j=5     3 --- 5  ------------ 10    DP[3][5] + DP[5][10] + 1
j=7     3 ---------- 7 ------ 10    DP[3][7] + DP[7][10] + 1
j=9     3 ---------------- 9  10    DP[3][9] + DP[9][10] + 1

            DP[3][5] + DP[5][10] + DP[3][7] + DP[7][10] + DP[3][9] + DP[9][10]
DP[3][10] = ------------------------------------------------------------------ + 1
                                            3

これを、効率的に計算したい。

• 大前提として、$DP[3][10]$ を計算するときには、それの元となる上記の値が既に求まっている必要がある
• 求まっていても、1個1個個別に足していては $O(N^3)$ となるので、集約した形で管理・取得したい

$DP[l][r]$ の計算に必要となる値は、$DP[l][○]$ か $DP[○][r]$ のようにいずれかが $l$ または $r$ であるのを利用する。

累積和として、以下を定義する。$N+2$ 本のFenwick Treeを作る。

• $SUB[x][y]=$ 片方が $x$、もう片方が $z$ の $DP$ の値の、$z=1～y$ の累積和
  • $x \lt y$ なら $DP[1][x]+DP[2][x]+...+DP[x-1][x]+DP[x][x]+DP[x][x+1]+...+DP[x][y]$
  • $x \gt y$ なら $DP[1][x]+DP[2][x]+...+DP[y][x]$
• ただし $A_l \gt A_r$ であるような、本来同時に採用されないような $DP[l][r]$ は $0$ とする

なお、$x$ が $DP[l][r]$ の $l$ になる場合も $r$ になる場合もまとめて1つの累積和に押し込んでいるのは単にメモリ節約のためで、 「$x$ が $l$ に来る時用」「$r$ に来る時用」の2つに分けてもよい。

累積和をいい感じに用意しておいて、$DP[3][10]$ を求める際に次のようなものが用意できていれば嬉しい。

• $SUB[3][10]-SUB[3][3]$ の計算で、$DP[3][5]+DP[3][7]+DP[3][9]$ が得られる
• $SUB[10][10]-SUB[10][3]$ の計算で、$DP[5][10]+DP[7][10]+DP[9][10]$ が得られる

しかし、元の定義通りでは、$DP[3][6]$（$A_6=11 \gt A_{10}=10$ なので対象外）や $DP[8][10]$（$A_3=5 \gt A_8=1$ なので対象外）など、 $DP[3][10]$ を求める上では除きたい $DP$ の値も混じってしまう。

処理順序を工夫することで、「必要な値は埋まりつつ、不要な値は未処理でまだ埋まっていない状態」にする。

$A_i$ の小さい方から、それを $r$ とした $DP$ を埋めていくことにする。

$r$ を固定したら $l$ を全探索する。
この際、$l$ については $A_l$ が大きいものから順に埋めていくと上手くいく。

                               r         rを固定
i: ...  3  4  5   6  7  8  9  10  ...      この時点で、10より小さい値をrとしたDPは埋まっていて、
A: ...  5  2  7  11  9  1  8  10  ...      10より大きい値をrとしたDPは未処理

                     l         r         lを「l<r かつ Al<Ar」のものの中からAlが大きい順に固定
i: ...  3  4  5   6  7  8  9  10  ...    [l, r) 間に採用可能な値はないので、DP[7][10]=0
A: ...  5  2  7  11  9  1  8  10  ...

                    済     l   r         lを次に固定
i: ...  3  4  5   6  7  8  9  10  ...    [l, r) 間に採用可能な値はないので、DP[9][10]=0
A: ...  5  2  7  11  9  1  8  10  ...

              l     済    済   r         lを次に固定
i: ...  3  4  5   6  7  8  9  10  ...    [l, r) 間には2つ採用可能な値が存在
A: ...  5  2  7  11  9  1  8  10  ...    

上例で、$DP[7][10]$ や $DP[9][10]$ は先ほど求めたし、$DP[5][7]$ や $DP[5][9]$ は $A_r=10$ まで進んできた時点で埋まっている。

逆に $DP[5][6]$ は、$A_6=11$ なので $DP[○][6]$ をまだ埋めていないので未処理、 $DP[8][10]$ は $A_8=1$ なので、$r=10$ に対する $l=8$ としたDPをまだ埋めていないので未処理となり、 きちんと必要な部分だけ埋まっていることがわかる。

よって、以下で更新できる。

• $DP[5][10] = (SUB[5][9] - SUB[5][5] + SUB[10][9]-SUB[10][5]) \times \dfrac{1}{2} + 1$
• $SUB[10][5] \xleftarrow{add} DP[5][10]$
• $SUB[5][10] \xleftarrow{add} DP[5][10]$

Python3

F - Paint Tree

• $N$ 頂点の木が与えられる
• 全頂点を白か黒で塗り分ける
• ある塗り方を決めたとき、白い頂点同士の最大距離を $X$、黒い頂点同士の最大距離を $Y$ とする
• $2^N$ 個の全ての塗り方について、$\max(X,Y)$ の総和を $\mod{10^9+7}$ で求めよ
• $2 \le N \le 2 \times 10^5$

$X$ や $Y$ が取り得る最大値は直径 $D$ になる。
まず直径をとる2頂点を見つける。

この2頂点が同色なら、他の頂点がどうあろうと $D$ になる。
まずこの場合は、$2^{N-1}D$ だけ答えに寄与する。

違う色の場合を考える。とりあえず左の頂点を白と固定して考えて、最終的な答えは2倍することにする。

○--？--？--？--？--？--？--●
    ｜      ｜      ｜
    ？      ？--？  ？--？

直径の性質として、どの頂点からも「その頂点から一番遠い点（の1つ）は直径の2点のいずれか」となる。

なので、直径の2頂点からの距離さえ考慮すればよい。それをまず全頂点について求めておく。

○--１--２--３--４--５--６--●
    ｜      ｜      ｜
    ２      ４--５  ６--７

○--６--５--４--３--２--１--●
    ｜      ｜      ｜
    ７      ５--６  ３--４

この中で、距離の大きい方から、$\max(X,Y)$ をその値にできるかを考えていく。

7になり得るのは、「右下の頂点が白の時」か「左下の1頂点が黒の時」。
(A)このどちらかさえ満たしていればよく、またその時に(B)他の頂点はどうなっていてもよい。

(A)の場合の数は $2^{7になり得る頂点の個数}-1$、(B)は $2^{直径からの距離が両方7未満の頂点の個数}$。

よって、答えには $7 \times (2^2-1)2^9$ だけ寄与する。

6になり得る頂点は4つある。7の場合と同様に考えて、$6 \times (2^4-1)2^5$ だけ寄与する。

実はもう5が取り得る最小値であることが判明していて、4以下は考える必要は無い。

なぜなら、真ん中付近から伸びる枝先にある頂点は、白からの距離が5、黒からが6である。

○--○--２--３--４--５--●--●
    ｜      ｜      ｜
    ○      ４--○  ●--●
                ↑これ

最大値が $x$ （以下）となるには、上図のように $x$ より大きい距離となりうる頂点については全て小さい方（大きくない方）の色を選んでいるということだが、 それでも距離が5となる頂点があるため、4以下にはなり得ない。

よってこの場合は、この時点で残っている頂点は全てどちらになろうとも、$\max(X,Y)$ は5となる。

答えには $5 \times 2^5$ だけ寄与する。

このように、大きい方から処理しながら「小さい方を取ったときの最大値」を更新しておいて、それが現在処理中の値以下になったら、そこで打ち切るようにする。
ただし、一直線のグラフに関しては残る頂点がなくなるまでその条件に当てはまらないため、最後に打ち切ったかのように計算する。

Python3