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

C - Keep Graph Connected

問題

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

解法

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

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

頂点     もう片方
 ○---(3)---3        →  3以外の番号にする
 ○---(3)---4        →  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]+\ldots+DP[x-1][x]+DP[x][x]+DP[x][x+1]+\ldots+DP[x][y]$
    • $x \gt y$ なら $DP[1][x]+DP[2][x]+\ldots+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

問題

解法

本WebサイトはcookieをPHPのセッション識別および左欄目次の開閉状況記憶のために使用しています。同意できる方のみご覧ください。More information about cookies
programming_algorithm/contest_history/atcoder/2020/1121_arc108.txt · 最終更新: 2020/11/27 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0