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$ を求めておくだけで、クエリには高速に答えられる。

Python3

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$ を必勝とし、スタックに積む

ことを繰り返すとよい。最終的に未確定なら、それは永遠に続く頂点となる。

Python3

F - Deforestation

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$

解法

Python3

programming_algorithm/contest_history/atcoder/2021/0710_abc209.txt · 最終更新: 2021/07/13 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0