比較的優しい回という印象。つまり不注意によるWAが響く。
-1
を出力せよ消す要素数を最小化するには、残す要素数を最大化すればいい。
元の $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)
ちょっと書いてみると、$f$ はつまり二重階乗である。
$N$ が奇数の時は、そもそも $f(N)$ が偶数になり得ないので、10の倍数にもなり得ない。'0'が答え。
偶数の時は、掛け合わせる要素の素因数として2が出てくる数と5が出てくる数の少ない方が答えとなる。今回の場合、明らかに5の方が少ない。
よって、「$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))
判定は毎ターン行われるので、すれ違いはできない。
青木君の移動を考えると、常に高橋君のいる方角の頂点を選んで移動した方がよい。 別の道に逸れてしまうと、高橋君から近づかない限り結局引き返さないと捕まえられないが、高橋君はそのような移動をわざわざする意味はない。
高橋君は、奥に逃げられるなら奥に逃げた方がよいので、捕まるのは行き止まりで追い詰められたときである。 その際、なるべく長く逃げられるよう、行き止まりが遠い枝を選んで逃げるのがよい。
まず①が思いつく。 また、少し考えると、②でも可能である。(実質①は②に包含される)
,-○ 青 ------○----- 高 ----------→ ① | `-○ `-------------------→ ②
どちらを取っても、青木君の移動回数は開始地点から① 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))