目次
AtCoder Beginner Contest 209 D,E問題メモ
D - Collision
問題
- $N$ 頂点の木が与えられる
- 以下のクエリに $Q$ 個答えよ
- 頂点 $c_i$ と $d_i$ から等速度で2人が互いに近づいたとき、出会うのは頂点上が辺上か?
- $1 \le N,Q \le 10^5$
解法
2点間の距離(1辺の長さを1とする)が偶数なら頂点上、奇数なら辺上となる。
木の2点間距離と言えば、LCAを使ったアルゴリズムがある。
- 根を適当に決めて、各頂点の深さ(根からの距離)$dep[v]$ を求めておく
- $c,d$ のLCAを $l_{c,d}$ とすると、$c,d$ の距離は $dep[c]+dep[d]-2dep[l_{c,d}]$
とはいえ、LCAを求めるアルゴリズムは典型ではあるがそれなりにややこしい。
今回の場合、距離そのものではなく、その偶奇がわかれば十分である。
LCAの項は2倍して使われるので、距離の偶奇は $dep[c]+dep[d]$ の偶奇と一致する。
なので、LCAは求めなくても、$dep$ を求めておくだけで、クエリには高速に答えられる。
E - Shiritori
問題
- 英大小文字52種からなる単語が $N$ 個あり、この中の単語だけで2人で3文字しりとりをする
- ルール
- 前の人が言った言葉の末尾3文字で始まる単語を交互に言う
- 先に自分の手番で言う単語のなくなった方が負け
- 同じ単語は何度でも使ってよい
- 結果としては「先手の勝ち」「後手の勝ち」「永遠に続く」がある
- 2人は互いに、自分が負けないことを最優先し、次に相手を負かせることを優先する
- 各単語から開始したときの結果をそれぞれ求めよ
- $1 \le N \le 2 \times 10^5$
解法
しりとりは有向グラフに置き換えられるので、まずグラフを作る。
ただしその際、単語を頂点として繋げてしまうと、 「$10^5$ 個は“abc”で終わる」「$10^5$ 個は“abc”で始まる」ような入力で、辺が $10^{10}$ 本できてしまいTLE。
[aaaabc] → [abcxxx] × [bbbabc] → [abcyyy] × [cccabc] → [abczzz]
以下のように、頂点は先頭や末尾の「3文字」を表し、単語は辺にすると最大 $2 \times 10^5$ 本で済むようになる。
(aaa) (xxx) ↘ ↗ (bbb)→(abc)→(yyy) ↗ ↘ (ccc) (zzz)
その際、多重辺が生じうる点に注意する必要があるが、この問題では1本にまとめてしまってよい。
これに従ってグラフ化すると、ループしてる頂点グループや、行き止まりの頂点があったりする。
(図では3文字で無く1文字で表現する)
(a) → (b) → (c) → (d) ↑ ↓ ↓ (e) ← (f) (g) → (h) ↓ ↑ (i) → (j)
その3文字で終わる単語を言えば必ず勝てると判明した頂点を「必勝頂点」、 必ず負けると判明した単語を「必敗頂点」ということにする。
行き止まりはわかりやすく、必勝頂点である。
(a) → (b) → (c) → 勝(d) ↑ ↓ ↓ (e) ← (f) (g) → 勝(h) ↓ ↑ (i) → (j)
プレイヤーは、必勝頂点に遷移できる状態で相手にターンを渡すと、必ずそれを言われてしまう。
従って、必勝頂点に遷移できる直前の頂点は必敗頂点になる。
(a) → (b) → 負(c) → 勝(d) ↑ ↓ ↓ (e) ← (f) 負(g) → 勝(h) ↓ ↑ (i) ─→ (j)
次に、必敗頂点にしか遷移できない頂点は、 その状態で相手にターンを回せば必ず必敗頂点に遷移してくれるので、必勝頂点である。
(a) → (b) → 負(c) → 勝(d) ↑ ↓ ↓ (e) ← (f) 負(g) → 勝(h) ↓ ↑ (i) → 勝(j)
これを繰り返す。
(a) → (b) → 負(c) → 勝(d) ↑ ↓ ↓ (e) ← (f) 負(g) → 勝(h) ↓ ↑ 負(i) → 勝(j)
すると、どうしても決まらない頂点群が残る(注: ループならば残るわけでもない)。
必勝とも必敗とも確定しない頂点に移動し続けることができる、ということなので、 これらは「永遠に続く」頂点となる。
実装の上では、逆トポロジカルソートのようにすればよい。
- 準備
- $R_v=\{r_1,r_2,...\}$: $v$ に流入できる頂点リスト(逆辺)
- $o_v$: $v$ から出る辺の数
- $ans_v$: 確定した必勝・必敗情報。最初は未確定で初期化
最初は、$o_v=0$ の頂点が行き止まりなので、それを必勝頂点にしてスタックに積む。
その後スタックが空になるまで、
- スタックから取り出した頂点を $v$ とする
- $v$ への流入頂点 $R_v=\{r_1,r_2,...\}$ のそれぞれについて、
- $v$ が必勝の場合
- $r$ は必敗で確定
- $ans_r$ が未確定の場合、必敗として $r$ をスタックに積む
- $v$ が必敗の場合
- $o_r$ を1減らす
- $o_r$ が0になっても未確定なら、それは「必敗にしか遷移できない頂点」なので必勝で確定
- $ans_r$ を必勝とし、スタックに積む
ことを繰り返すとよい。最終的に未確定なら、それは永遠に続く頂点となる。
F - Deforestation
挿入DP、「はぁ、そんな風に情報を持たせりゃいいと気付くたぁ、世の中にゃえれぇ天才がいたもんだ」って毎回言ってる気がする。
問題
- $N$ 本の草が左右一列に並び、高さは $H_1,H_2,...,H_N$
- 好きな順で全ての草を伐採する
- 順番の決め方は $N!$ 通り
- 草 $i$ の伐採時は、
- その時点の $H_{i-1}+H_{i}+H_{i+1}$ のコストがかかる
- その後、$H_i$ を $0$ にする
- $N!$ 通りのうち、全草を伐採するコストを最小にできる順番は何通りあるか求めよ
- $1 \le N \le 4000$
解法
-
- このT問題がかなり近い