目次
AtCoder Beginner Contest 148 D～F問題メモ
比較的優しい回という印象。つまり不注意によるWAが響く。
D - Brick Break
問題
- 長さ $N$ の数列 $A=\{a_1,a_2,...,a_N\}$
- 好きな要素を消す操作を何回でもおこなうことができる（消された要素の後ろは前に詰める）
- 消した結果、数列を $\{1,2,3,...\}$ のように、$i$ 番目の要素が $i$ であるようにしたい
- 消す必要のある最小数を求めよ
- 不可能な場合は
-1を出力せよ - $1 \le N \le 2 \times 10^5$
解法
消す要素数を最小化するには、残す要素数を最大化すればいい。
元の $A$ において左から順に 1→2→3→4→… と拾える数列を残すことができる。しかし順番は変えられないので、'1'の前に'2'が出てきても、その'2'は使えない。
'1'がどこにも無ければ不可能なので'-1'を出力して終了。
その他は、先頭から貪欲に残せる要素を拾っていって、残る要素数を $N$ から引いた値が答え。
N = 10 A 3 1 4 1 5 9 2 6 5 3 残す 1 2 3 ↓ 消す 10 - 3 = 7
貪欲に残してよい証明を与える方法の1つとして、貪欲に残さなかった場合によくならないことを示せばよい。
たとえば'3'について、(A)残すことが可能な最初の'3'でなく、(B)その次に出てくる'3'を残すとする。 すると次以降の「'4'→'5'→'6'→…」は'3'の後に出てくる中から選んで残すことになるが、(B)の場合に残すことが可能な要素は全て、(A)の場合でも残すことができる。 残す要素数を最大化するにあたり、貪欲にしないことによって改善することはない。
(A) (B)
... 3 1 4 3 4 2 ...
|-------------- ... (A)を残すことで次に残す'4'を採用可能な範囲
|----- ... (B)を残すことで次に残す'4'を採用可能な範囲
実装では、多くのプログラミング言語では、配列内の検索で開始indexを指定できるのでそれを使えばよい。 検索する要素が存在しないかも知れない点に注意。Pythonでは例外処理により対応するのがメジャー?
n = int(input())
aaa = list(map(int, input().split()))
if 1 not in aaa:
print(-1)
exit()
i = 0
a = 1
while True:
try:
j = aaa.index(a, i)
except ValueError:
break
i = j + 1
a += 1
print(n - a + 1)
E - Double Factorial
問題
- 0以上の整数 $n$ に対し $f(n)$ を次のように定義する
- $f(n)=1 \ \ \ \ (n = 0, 1)$
- $f(n)=nf(n-2) \ \ \ \ (n \ge 2)$
- 整数 $N$ が与えられる
- $f(N)$ の末尾に何個の0が続くかを求めよ
- $0 \le N \le 10^{18}$
解法
ちょっと書いてみると、$f$ はつまり二重階乗である。
- $f(n=偶数)=n$ までの全ての偶数の積 $=n!!$
- $f(n=奇数)=n$ までの全ての奇数の積 $=n!!$
$N$ が奇数の時は、そもそも $f(N)$ が偶数になり得ないので、10の倍数にもなり得ない。'0'が答え。
偶数の時は、掛け合わせる要素の素因数として2が出てくる数と5が出てくる数の少ない方が答えとなる。今回の場合、明らかに5の方が少ない。
- $2^a \times 5^b \times X^c \times ... → \min(a,b)$ 個の'0'が並ぶ
よって、「$N$ までの偶数の中に、5の素因数は何個ありますか」という問題である。
偶数という制限が無ければ、このような問題は、$N$ を5で繰り返し割って、その都度、商を足した結果が答えとなる。
N = 600
5を 1個 素因数に持つ数は 600/5 = 120 個
その中で 5をもう 1個 素因数に持つ数は 120/5 = 24 個
その中で 5をさらに1個 素因数に持つ数は 24/5 = 4 個
→ 148 個
今回は偶数なので、最初だけ10で割り、後は5で割っていけばよい。
偶数かつ5の倍数 10 20 30 40 50 ... 100 ... 600 10で割った結果 1 2 3 4 5 ... 10 ... 60 → この数列から、さらに5の素因数が残っている数を探す ＝ 制限のない N=60 の問題と見なせる
def solve(n):
if n % 2 == 1:
return 0
d = n // 10
ans = d
while d:
d //= 5
ans += d
return ans
n = int(input())
print(solve(n))
F - Playing Tag on Tree
問題
- $N$ 頂点の木があり、$i$ 番目の辺は頂点 $a_i$ と $b_i$ を双方向に結ぶ
- 高橋君と青木君が木の上で鬼ごっこをする
- はじめ、高橋君は頂点 $u$、青木君は頂点 $v$ にいる（この2頂点は必ず異なる）
- 以下の手順の繰り返しで行う
- 2人が同じ頂点にいたら終了。そうで無ければ高橋君は隣接する頂点を1つ選んで移動
- 2人が同じ頂点にいたら終了。そうで無ければ青木君は隣接する頂点を1つ選んで移動
- 高橋君はできるだけ長くゲームを続け、青木君ははやく終了させたい
- 2人が最適に動いた時、終了するまでに青木君が移動する回数を求めよ
- $2 \le N \le 10^5$
解法
判定は毎ターン行われるので、すれ違いはできない。
青木君の移動を考えると、常に高橋君のいる方角の頂点を選んで移動した方がよい。 別の道に逸れてしまうと、高橋君から近づかない限り結局引き返さないと捕まえられないが、高橋君はそのような移動をわざわざする意味はない。
高橋君は、奥に逃げられるなら奥に逃げた方がよいので、捕まるのは行き止まりで追い詰められたときである。 その際、なるべく長く逃げられるよう、行き止まりが遠い枝を選んで逃げるのがよい。
まず①が思いつく。 また、少し考えると、②でも可能である。（実質①は②に包含される）
- ①最初から、行き止まりが遠い方へ逃げ続ける
- ②一旦青木君に近づき、ある頂点から行き止まりが遠い方へ逃げ続ける
,-○
青 ------○----- 高 ----------→ ①
| `-○
`-------------------→ ②
どちらを取っても、青木君の移動回数は開始地点から① or ②への距離に近い値になるので、より青木君から遠い頂点で捕まりたい。
①より遠い②があればそちらに逃げ込みたいが、近づいたところで捕まってしまっては元も子もないので、近づけるのは青木君に捕まらない範囲までとなる。
最終的に捕まる頂点
最終的に捕まる状況はどうなるかというと、2通りのパターンがある。
- 青木君が、高橋君のいる頂点に移動する
- 高橋君が、行き止まりで仕方なく青木君のいる頂点に移動する
実際に試してみると、どちらにしても捕まる頂点は「行き止まりの1つ手前の頂点」となる。
これ、「高橋君の移動回数」なら場合分けする必要があったが、「青木君の移動回数」なので、純粋に青木君の初期位置からの距離を答えてよい。
実装
まず、青木君を根として「各頂点の深さ」と「その頂点から最も深い葉までの距離」を計算しておく。
高橋君が、青木君に捕まらない範囲で近づけるぎりぎりの頂点まで近づき、折り返す。 （実際には①の戦略でよかったとしても、この移動の仕方で、捕まる位置は変わらない）
「折り返す頂点の深さ」+「その頂点から最深の葉までの距離」が答えとなる。
折り返せず捕まる最大の頂点の深さは、高橋君の開始位置の深さの $\frac{1}{2}$（切り捨て）となる。
（または、高橋君と青木君の両方を始点としてDFSを2回行い、高橋君の方が速いターンでたどり着ける葉、としてもよい）
import sys
sys.setrecursionlimit(10 ** 5)
def dfs(v, parent, depth):
parents[v] = parent
self_depths[v] = depth
sd = 0
for u in links[v]:
if u == parent:
continue
res = dfs(u, v, depth + 1)
sd = max(sd, res + 1)
subtree_depths[v] = sd
return sd
def solve(u):
catch = self_depths[u] // 2
while self_depths[parents[u]] > catch:
u = parents[u]
return self_depths[u] + subtree_depths[u] - 1
n, u, v = map(int, input().split())
u -= 1
v -= 1
links = [set() for _ in range(n)]
for line in sys.stdin:
a, b = map(int, line.split())
a -= 1
b -= 1
links[a].add(b)
links[b].add(a)
parents = [-1] * n
self_depths = [0] * n
subtree_depths = [0] * n
dfs(v, -1, 0)
print(solve(u))
