[日記] AtCoder ABC148 に参加した

C, D からバリバリ難しかった前回と打って変わって E まではそこそこ解きやすい問題で、 F が急に難しいような配分だった。

# ABC148
## ABC148 A Round One

`1`, `2`, `3` の中から二つが与えられるので、残りの一個を表示する。

### 印象

やるだけ

### 解法

`if` 文でゴリゴリ分岐する。

### 別解

`1 + 2 + 3` が `6` になるので、 `6` から与えられた二つを引くことでも求まった（この方がコード量が圧倒的に少ない）。言われてみればショートコーディングをやっていたときにやった気もするけど、思いつけなかった。

## ABC148 B Strings with the Same Length

二つの同じ文字数の文字列 `S`, `T` が与えられるので、 `S[0]`, `T[0]`, `S[1]`, `T[1]`, ... の順に表示する

### 印象

やるだけ

### 解法

問題文通りに実装するだけ

## ABC148 C Snack [LCM]

`A`, `B` のどちらでも割り切れるなるべく小さい整数を求める

### 印象

最小公倍数

### 解法

ユークリッドの互除法か何かで最小公倍数を求めれば ok。面倒だったので `lcm` がライブラリに入っている Nim で解いてしまった。

## ABC148 D Brick Break

`N` 個の整数が与えられる。ここからいくつかを取り除いて、 `i` 番目の数字が `i` になっているようにしたい。最小でいくつの整数を取り除く必要があるか。不可能な場合は `-1` を表示

### 印象

まずは `1` がくるまで整数を取り除き続け、 `1` がきたら次は `2` がくるまで整数を取り除き続け、…を繰り返せば ok

### 解法

印象通り。

すべての整数が取り除かれてしまったら `-1` と表示することに注意。

## ABC148 E Double Factorial [素因数分解]

`N <= 10^18` が与えられるので、「一個飛ばしの階乗」

    N * (N - 2) * (N - 4) * ...

の末尾に `0` がいくつ並ぶかを求める

### 印象

かなり近い問題を研究室のプロコンで出題したことがあった。 `N` が巨大なので真面目に計算したらもちろんダメ。

末尾に `0` をひとつ増やすためには素因数に `2` と `5` が一つづつあればよい。

`N` が奇数の場合は登場人物が全員奇数になってしまうので `2` は一つもとれない。したがって答えは `0`。

偶数の場合、全てが `2` の倍数になるので `2` はいくらでも取れる。なので `5` がいくつ取れるかを求めればよさそう。

普通の階乗だったら繰り返し `5` で割っていれば「`5` の倍数の数」「`25` の倍数の数」... が求まるので、たんにそれらを合計すればいくつ `5` が取れるかがわかる。しかし今回は偶数しか登場しないので、 `15` や `25` は出てこない。したがって、初回だけは `10` で割って 10 の倍数までフィルターする必要がある (同じことだが、最初に `2` で割って偶数にフィルターしてから、以降 `5` で割り続けるでも ok)。

### 解法

印象通り。

`N / 10`, `N / 10 / 5`, `N / 10 / 5 / 5`, ... の合計をループで求めれば ok

## ABC148 F Playing Tag on Tree [BFS]

`N <= 10^5` 個の頂点と `N - 1` 本の辺があって、これらは木になる (ループがない) ことが保証されている。

`u` 番目の頂点に逃げ役が、 `v` 番目の頂点に鬼役がいて、これから鬼ごっこをする：

1. もし逃げ役と鬼役が同じ頂点にいたら終了

2. 逃げ役が隣接する頂点のどれかに必ず移動する

3. もし逃げ役と鬼役が同じ頂点にいたら終了

4. 鬼役が隣接する頂点のどれかに必ず移動する

5. 1 に戻る

逃げ役はなるべくゲームが長引くように行動し、鬼役はなるべくゲームが早く終わるように行動する。二人が互いに相手の居場所と戦略を把握して最適に行動するとき、ゲームが終了するまでに鬼役が何回移動するか

### 印象

相手の戦略を把握して最適に行動って minimax とかゲームのシミュレーション系…？

やったことないけどやってみるか…。

### 解法

全然違った。落ち着いて。

もしループがあるマップだったら相手を巻いたり撹乱することができそうだが、今回はループがないので、どう逃げても必ずいつかは袋小路に入って鬼に捕まる。したがって逃げ役にできる最大の悪あがきは「一番長い袋小路に逃げ込んでなるべくゲームを長引かせる」こと。一方の鬼役も、寄り道せずひたすら逃げ役を追い詰めるのが最適。シンプル。

「鬼役が何回移動するか」を求めることは、鬼役のスタート地点から、逃げ役を捕まえる地点までの距離を求めることと同じなので、結局、逃げ役がどこで捕まるか (逃げ役がどこまで逃げられるか) がわかればよい。

逃げ役はどこに逃げ込むのが最適か考える。木なので、 `u, v` をつまんで持ち上げるとこんな感じになる。

<img width="1054" alt="スクリーンショット 2019-12-23 11.59.47.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/54240/546a277e-5760-3042-40de-4643c753212a.png">

鬼役を巻くことはできないので、せめて相手をなるべく長く走らせることを考えると、鬼から一番距離が遠い頂点に直行し、その最奥で捕まるのを待つのがよいとわかる。

ただし、以下の赤で塗ったエリアは逃げこむ前に鬼に鉢合わせてしまうので、ここを目指してしまうとむしろ鬼を迎えに行くことになってしまう。

<img width="1049" alt="スクリーンショット 2019-12-23 12.04.12.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/54240/701c49a7-6578-7f8b-c8e5-c05e44cf4539.png">

赤のエリアは「鬼の方が早く辿り着ける、または同着」のエリアなので、言い換えれば逃げ役の目指すべき頂点 `x` は「逃げ役の方が早く辿り着ける」エリア

```
distance(u, x) < distance(v, x) [distance は頂点間の最短距離]
```

であって、 `distance(v, x)` が一番大きい頂点。

念のため逃げ込める部分木がないケースも考えておく。

<img width="981" alt="スクリーンショット 2019-12-23 12.08.38.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/54240/853f82ea-1002-e7bb-789a-ef012c0537af.png">

この場合はあえて鬼を迎えに行かずに、スタート地点でじっとしているのが最適になるが、これも上の条件を満たす。したがって別個に求める必要はない。

あとは各 `1 <= i <= N` について `distance(v, i), distance(u, i)` を求めればよいが、これは木なのでたんに `u, v` からそれぞれ DFS / BFS をすれば十分。

最後にひとつトラップがあって、逃げ役の捕まる場所は必ず、行き止まりの「一つ前」の頂点になる。なぜなら、行き止まりのぴったり先端で捕まるためには、逃げ役が先端・鬼役がそのひとつ手前の頂点にいる状態で鬼役にターンが回ってくる必要があるが、そのためにはその直前の逃げ役のターンで逃げ役が一つ手前の頂点にいなければならない。そこにはすでに鬼がいるので、矛盾する。

したがって、答えは上の条件から見つかる「最適の引きこもり先」を `x` として、 `distance(v, x) - 1`。