AtCoder Beginner Contest 209 D,E問題メモ

AtCoder Beginner Contest 209

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

n, qn = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)

depth = [-1] * n
depth[0] = 0
q = [0]
while q:
    v = q.pop()
    for u in links[v]:
        if depth[u] != -1:
            continue
        depth[u] = depth[v] + 1
        q.append(u)

for _ in range(qn):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if (depth[c] + depth[d]) % 2 == 0:
        print('Town')
    else:
        print('Road')

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

なんか、単語を頂点のまま残し、3文字を表す頂点と混在させる変な実装をしてしまっている。

n = int(input())
letters3_dict = {}
links = [set() for _ in range(3 * n)]
rev_links = [set() for _ in range(3 * n)]
out_degrees = [0] * (3 * n)
for i in range(n):
    s = input()

    prefix = s[:3]
    if prefix in letters3_dict:
        pi = letters3_dict[prefix]
    else:
        letters3_dict[prefix] = pi = len(letters3_dict) + n
    links[pi].add(i)
    rev_links[i].add(pi)
    out_degrees[pi] += 1

    suffix = s[-3:]
    if suffix in letters3_dict:
        si = letters3_dict[suffix]
    else:
        letters3_dict[suffix] = si = len(letters3_dict) + n
    links[i].add(si)
    rev_links[si].add(i)
    out_degrees[i] += 1

m = len(letters3_dict)
links = links[:n + m]
rev_links = rev_links[:n + m]
out_degrees = out_degrees[:n + m]

ans = [-1] * (n + m)
q = []
for i, c in enumerate(out_degrees):
    if c == 0:
        q.append(i)
        ans[i] = 1

while q:
    v = q.pop()
    # print(v, q, ans)
    if v < n:
        for u in rev_links[v]:
            if ans[u] != -1:
                continue
            if ans[v] == 1:
                ans[u] = 0
                q.append(u)
            else:
                out_degrees[u] -= 1
                if out_degrees[u] == 0:
                    ans[u] = 1
                    q.append(u)
        continue

    win = ans[v]

    for u in rev_links[v]:
        out_degrees[u] -= 1
        ans[u] = win
        q.append(u)

for a in ans[:n]:
    print(['Aoki', 'Takahashi', 'Draw'][a])

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$

解法

Educational DP Contest S,T,U,Vメモ
- このT問題がかなり近い

Python3

import numpy as np

n = int(input())
hhh = list(map(int, input().split()))
dp = np.ones(n, np.int64)
MOD = 10 ** 9 + 7
for i in range(n - 1):
    if hhh[i] > hhh[i + 1]:
        dp = dp[:0:-1].cumsum()[::-1]
    elif hhh[i] == hhh[i + 1]:
        dp[:] = dp.sum()
        dp = dp[:-1]
    else:
        dp = dp[:-1].cumsum()
    dp %= MOD
print(dp[0])

目次

AtCoder Beginner Contest 209 D,E問題メモ

D - Collision

問題

解法

E - Shiritori

問題

解法

F - Deforestation

問題

解法