−目次

AtCoder Beginner Contest 148 D～F問題メモ

AtCoder Beginner Contest 148 D～F問題メモ

AtCoder Beginner Contest 148

解説放送: AtCoder Beginner Contest 148 - YouTube

比較的優しい回という印象。つまり不注意による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頂点は必ず異なる）
以下の手順の繰り返しで行う
1. 2人が同じ頂点にいたら終了。そうで無ければ高橋君は隣接する頂点を1つ選んで移動
2. 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))

            

        
      