目次
ARC 097
C - K-th Substring
問題
- 英小文字からなる文字列 $s$ のsubstringを考える
- substring = 連続する1文字以上の部分文字列
- 抽出場所が違っても、文字列が同じであれば同一視する
- 辞書順でK番目のsubstringを求めよ
- $1 \le K \le 5$
例
'ikada' の4番目のsubstring
| 1 | 2 | 3 | 4 | 5 | 6 | … |
|---|---|---|---|---|---|---|
| a | ad | ada | d | da | i | … |
なので、答えは'd'となる。'a'は2箇所から抽出できるが、K番目を求める際は1つとして数える。
解法
答えの文字列は最長でも $K$ 文字となる。
例えば ABCDE という5文字の文字列があったとすると、辞書順では $A<AB<ABC<ABCD<ABCDE$ となる。$K$ 文字の文字列は、末尾を取ると自分より辞書順に小さい文字列が $K-1$ 個作れるので、$K$ 番目より小さくはならない。
よって、1～$K$ 文字のsubstringを全て抽出し、ソートすればよい。Pythonではset()を使うと、重複を除いた集合を作れる。
def solve(s, k):
can = set()
for l in range(k): # 抽出するsubstringの長さ
for i in range(len(s) - l): # 抽出するsubstringの開始位置
can.add(s[i:i + l + 1])
can = sorted(can)
return can[k-1]
s = input()
k = int(input())
print(solve(s, k))
D - Equals
問題
- 1から $N$ までの整数を並び替えた順列 $P=\{p_1, p_2, .., p_N\}$
- $P$ の2箇所の数字を入れ替える操作を繰り返す
- 入れ替えられるペアは $M$ 個あり、$x_m,y_m$ の組で与えられる
- 操作時点での $P$ の$x_m$ 番目と $y_m$ 番目を入れ替えることを示す
- $p_i=i$ となる項をなるべく増やしたい。最大いくつの項が達成できるか
例
5 1 4 3 2 p1とp2が入替可 p1とp5が入替可
↓
5 1 4 3 2 2 1 4 3 5 p1 <-> p5 1 2 4 3 5 p1 <-> p2
で、1,2,5について一致させられたので、答えは3となる。
解法
Union-Find問題。更新が無いのでDFSでもいいが。
p1とp2が入れ替え可能、p1とp5が入れ替え可能ならば、(1,2,5)は「同じ集合に所属している」と表現することにする。
同じ集合に属する数字は、たとえ直接は入れ替えできなくとも、その中で好きなように並べなおすことが可能となる。（全域木の葉から固定していく）
| i | 1 | 2 | 3 | 4 | 5 |
| pi | 5 | 1 | 4 | 3 | 2 |
例えば $i=1$ を考えると、1が属する集合と、$p_1=5$ が属する集合が同じであれば、5を $p_5$ の位置に持ってくることが出来る。逆に、存在しない（異なる集合に属する）場合はどうやっても無理。
よって、
- Union-Findで、集合関係を構築する
- $1 \le k \le N$ について、$k$ と $p_k$ が同じ集合に属するか調べる
- 同じ集合に属した $k$ の数が答え
class UnionFind:
def __init__(self, n):
self.table = [-1] * n
def _root(self, x):
if self.table[x] < 0:
return x
else:
self.table[x] = self._root(self.table[x])
return self.table[x]
def find(self, x, y):
return self._root(x) == self._root(y)
def union(self, x, y):
r1 = self._root(x)
r2 = self._root(y)
if r1 == r2:
return
d1 = self.table[r1]
d2 = self.table[r2]
if d1 <= d2:
self.table[r2] = r1
if d1 == d2:
self.table[r1] -= 1
else:
self.table[r1] = r2
n, m = map(int, input().split())
uft = UnionFind(n)
ppp = list(map(int, input().split()))
for _ in range(m):
x, y = map(int, input().split())
x -= 1
y -= 1
uft.union(x, y)
ans = 0
for i, x in enumerate(ppp):
if uft.find(i, x - 1):
ans += 1
print(ans)
E - Sorted and Sorted
問題
- $1$ から $N$ までの整数が1つずつ書かれた白いボールと黒いボールが $N$ 個ずつあり、あわせて $2N$ 個、一列に並ぶ
- 隣り合うボールを入れ替える操作を繰り返して、以下の条件を満たすようにする
- 白いボールだけを見ると、書かれた数字が左から昇順に並んでいる
- 黒いボールだけを見ても、書かれた数字が左から昇順に並んでいる
- 最小の操作回数を求めよ
- $1 \le N \le 2000$
例
❸②❶③①❷
↓ ③を1回右に
❸②❶①③❷
↓ ②を2回右に
❸❶①②③❷
↓ ❸を5回右に
❶①②③❷❸
これで条件を満たす。操作回数は8回
解法
ボールが1色だけなら、転倒数として解けることが知られている問題。バブルソートする時の交換回数と一致する。
この問題の場合は、その考えを使いつつ、動的計画法で解く。
dp[w][b] を、$1$～$w$ の白いボールと、$1$～$b$ の黒いボールだけを使っての、最小の操作回数とする。$0 \le w \le N, 0 \le b \le N$ とし、$w=0$ は白いボールを使わないことを示す。
オリジナル → ❸②❶③①❷
例: dp[2][2] → ②❶ ①❷ を並び替える最小回数 = 2
dp[1][3] → ❸ ❶ ①❷ を並び替える最小回数 = 3
dp[0][3] → ❸ ❶ ❷ を並び替える最小回数 = 2
すると、dp[w][b] は dp[w-1][b] と dp[w][b-1] から求めることが出来る。
どうするか。
まず dp[w][b] について、$1$～$w$ の白いボールと $1$～$b$ の黒いボールを使うと決めた時、初期状態は元の並び順から抜き出したままの並びとする。
条件を満たす最終状態は複数考えられるが、どれか1つに決めると、それに必要な操作回数は一意に決まる。
元の全体の並び
❸②❶③①❷ どんな最終状態がよい？
dp[2][2]での初期状態 ❶①②❷ = 2回 Best!
②❶ ①❷ → ①❶②❷ = 3回
①❶❷② = 4回
この操作回数を最小にする最終状態が一発でわかればいいが……
ここで転倒数の考え方、つまり「全体で必要な操作回数は、各ボールについて独立に『自分より右に、自分と交換しなければならないボールがいくつあるか』の和である」ということを用いる。
初期状態 最終状態 ②❶①❷ → ①❶②❷ ①について、初期状態で自分より右にあり、最終状態で左にあるものの個数＝0 ②について、(同上) ＝2 ❶について、(同上) ＝1 ❷について、(同上) ＝0 この最終状態にするには、0+2+1+0=3回の操作が必要
このことを念頭に置いて考える。
$1$～$w$ の白いボールと $1$～$b$ の黒いボールを条件に合うよう並べ替えた時、最終状態の一番右にあるボールは、必ず白の $w$ か 黒の $b$ である。
一番右を白の $w$ と仮定すると、“一番右以外の最終状態がどうであれ” 白の $w$ だけに必要な操作回数は、初期状態で自身の右にあるボールの個数と一致する。
dp[2][2] 最終状態 ②❶ ①❷ → ？？？？ dp[3][2] ②❶③①❷ → ？？？？③ （③が一番右に来ると仮定して）③の操作は2回
③以外の個々のボールの回数は、dp[2][2]の時と変わらない。だって追加された③は最終状態で絶対右にいるので、「最終状態で左にあるものの個数」に加えられるはずが無い。なので、dp[3][2]は、純粋にdp[2][2]に追加分の2回を足せばよいのである。
$$dp'[w][b] = dp[w-1][b] + (白のwより右にある,白はw-1,黒はb以下のボールの個数)$$
一番右に持ってくるのが黒の場合も同様に考えて、小さい方を採用することで、dpを更新できる。
\begin{align} dp[w][b] = \min( & dp[w-1][b] + (白のwより右にある,白はw-1,黒はb以下のボールの個数) \\ & dp[w][b-1] + (黒のbより右にある,白はw,黒はb-1以下のボールの個数)) \end{align}
実装においては、$cost_w[k][x]=$「白い $k$ 以下のボールの内、位置 $x$ よりも右にあるものの個数」を事前計算しておく（$cost_b$ も同様）と、
x = 初期状態で白のwのindex
y = 初期状態で黒のbのindex
dp[w][b] = min( dp[w-1][b] + cost_w[w-1][x] + cost_b[b][x],
dp[w][b-1] + cost_w[w][y] + cost_b[b-1][y] )
で遷移できる。
from itertools import accumulate
def solve(n, rev):
def existence_right(rev_c):
n2 = n * 2
acc = [[0] * n2]
row = [0] * n2
for x in rev_c:
row[n2 - x - 1] += 1
acc.append(list(reversed(list(accumulate(row)))))
return acc
# How many white/black ball lower than 'k' righter than index x? (0<=x<=2N-1)
# cost[k][x]
cost_w, cost_b = list(map(existence_right, rev))
dp = [0] + list(accumulate(c[y] for y, c in zip(rev[1], cost_b)))
for w, x in enumerate(rev[0]):
ndp = [0] * (n + 1)
cwx = cost_w[w][x]
ndp[0] = prev = dp[0] + cwx
for b, y in enumerate(rev[1]):
ndp[b + 1] = prev = min(dp[b + 1] + cwx + cost_b[b + 1][x],
prev + cost_w[w + 1][y] + cost_b[b][y])
dp = ndp
return dp[n]
n = int(input())
rev = [[0] * n, [0] * n] # White/Black 'k' ball is what-th in whole row?
for i in range(n * 2):
c, a = input().split()
a = int(a) - 1
rev[int(c == 'B')][a] = i
print(solve(n, rev))
F - Monochrome Cat
問題
- $N$ 頂点の木があり、各頂点は白か黒で塗られている
- 猫がこの木を移動する
- 猫は、以下の2種類の操作を行える
- 今いる頂点の色を反転させる
- 隣り合う頂点へ移動し、移動先の頂点の色を反転させる
- どの頂点から移動を開始し、どの頂点で終えてもよい
- 全ての頂点の色を黒にするのに最小の操作回数を求めよ
- $1 \le N \le 10^5$
例
○
／｜＼
○ ● ●
/\ ｜ /\
●○ ○ ○○
↑
ここから始める
○
／｜＼
○ ● ●
/\ ｜ /\
●❶ ○ ○○ 今いる頂点を反転（1回）
❶
／｜＼
● ● ●
/\ ｜ /\
●● ○ ○○ 頂点の色を変えながら上へ移動（2回）
●
／｜＼
● ○ ●
/\ ｜ /\
●● ❶ ○○ 中央下へ移動（2回）
①
／｜＼
● ● ●
/\ ｜ /\
●● ● ○○ 上へ移動（2回）
❶
／｜＼
● ● ●
/\ ｜ /\
●● ● ○○ 頂点の色を変える（1回）
●
／｜＼
● ● ○
/\ ｜ /\
●● ● ❶○ 下へ移動（2回）
●
／｜＼
● ● ●
/\ ｜ /\
●● ● ●❶ 1回上へ、1回下へ移動（2回）
これで全ての色が黒になる。操作回数は12回
解法
オイラーツアー+木の直径
まず、最初から黒の葉に訪れる必要は無いので、再帰的に切り詰める。
○
／｜＼
○ ● ●
/\ ｜ /\
●○ ● ○●
↑ ↑ ↑
最初から黒の葉
○
／ ＼
○ ●
\ /
○ ○ 切り詰めて考えてよい
白い葉には必ず訪れる。白い葉に行こうと思えば途中の頂点は白だろうが黒だろうが通るので、切り詰めた後の全ての頂点を最低1回は訪れることになる。
切り詰めた後の木を $T$、頂点数を $K$ とする。
ところで、木の全ての頂点をDFSの順に巡っていくのを、Euler_tour_technique(オイラーツアー)という。出発点と到着点は同じで、全ての辺を両方向1回ずつ通る。
猫は、Euler Tourの順に木を辿るのが最も無駄が無い。
○ ／｜＼ ○ ● ● \ ｜ /\ ○ ○ ○○
まず最終的な色は気にせず、Euler Tourの通りに移動を行う（全ての頂点を経由し出発点に戻ってくる）と、どの頂点から始めても移動回数は $2(K-1)$ となる。
全ての辺を両方向1回ずつ通るので、各頂点の色の反転回数は、その頂点の次数（頂点から伸びる辺数）と一致する。つまり、奇数なら初期状態で白、偶数なら初期状態で黒なら、Euler Tourの後で黒になっている。この事実も、どの頂点から始めても不変。
Euler Tour的な移動をした後の色の状態
●
／｜＼
○ ● ●
\ ｜ /\
● ● ●●
Euler Tourで辿るだけでは黒にならない頂点は、その頂点を訪れた時に1回だけ留まって色を反転させればよい。（初期状態が黒 XOR 次数が偶数）
操作の順番は関係ないので、Euler Tourの操作回数と、それだけでは黒にならない頂点の反転操作回数を単純に足し合わせればよい。
これでひとまず全ての頂点を黒にすることはできたが、明らかにこの移動は無駄がある。全ての頂点を一度だけ訪れればよいので、一番最後に訪れた頂点から出発点に戻る移動は不要だ。最後の頂点で終わった方が操作回数が少なくなる。
なので、どれだけ多くの操作を省略できるか考える。省略できる操作回数を最大化することが「操作回数の最小化」に結びつく。
一番最後に訪れる頂点から出発点へのパスを $P$ で示す。直感的には $P$ が出来るだけ長い方がよさそうだが……？
ただし、Euler Tourから $P$ の移動を省略するとなると、$P$ 上の頂点の最終的な色が変わってくる。つまり、$P$ は始点以外の頂点で1回ずつ訪れられる回数が減るので、終了後の色が逆になる。
Euler Tour後に白だった頂点は黒になるため最終的な反転も必要なくなり2倍お得。一方、黒だった頂点は白になり新たに色を反転させる必要性が生じるので、移動を省略したメリットが相殺される。
つまり減少させられる操作回数は、
$$ |P| + |EulerTour終了後に白になるP上の頂点| - |EulerTour終了後に黒になるP上の頂点| \\ = 2 |EulerTour終了後に白になるP上の頂点| $$
となる。なので、EulerTour終了後に白になる頂点の個数を最大化するように $P$ を決めればよい。これは、木の直径と同じように（ただしコストを辺数から条件を満たす頂点の個数に変えて）計算できる。
from collections import deque
def first_cut(links, colors):
tmp_links = links.copy()
for v, neighbors in tmp_links.items():
while len(neighbors) == 1 and colors[v]:
del links[v]
par = neighbors.pop()
links[par].remove(v)
v = par
neighbors = links[par]
return links
def diameter(links, flags):
def dfs(s):
fs = flags[s]
d, v = 0, 0
q = deque(sorted((fs + flags[v], v, s) for v in links[s]))
while q:
d, v, a = q.popleft()
for u in links[v]:
if u == a:
continue
fu = flags[u]
if fu:
q.append((d + 1, u, v))
else:
q.appendleft((d, u, v))
return d, v
s = next(iter(links))
_, t = dfs(s)
d, _ = dfs(t)
return d
def solve(links, colors):
if all(colors):
return 0
links = first_cut(links, colors)
k = len(links)
if k == 1:
return 1
flags = {v: colors[v] ^ (len(link) % 2 == 0) for v, link in links.items()}
euler_tour = 2 * (k - 1) + sum(flags.values())
return euler_tour - 2 * diameter(links, flags)
n = int(input())
links = {i: set() for i in range(n)}
for _ in range(n - 1):
x, y = map(int, input().split())
x -= 1
y -= 1
links[x].add(y)
links[y].add(x)
colors = [c == 'B' for c in input()]
print(solve(links, colors))
