AtCoder Beginner Contest 148 D~F問題メモ

AtCoder Beginner Contest 148

比較的優しい回という印象。つまり不注意によるWAが響く。

D - Brick Break

問題

  • 長さ $N$ の数列 $A=\{a_1,a_2,\ldots,a_N\}$
  • 好きな要素を消す操作を何回でもおこなうことができる(消された要素の後ろは前に詰める)
  • 消した結果、数列を $\{1,2,3,\ldots\}$ のように、$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 \ldots → \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))

programming_algorithm/contest_history/atcoder/2019/1222_abc148.txt · 最終更新: 2019/12/23 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0