競技プログラミング練習記 No.8【ABC148練習】



AOJ



初回 -> [はじめに](https://qiita.com/easychoco/items/a9ae28aca97cfe47091f)

[ABC148](https://atcoder.jp/contests/abc148)を解きました。
5完です。
F問題は自力で解けず、解説等を見て解きました。
答えは見ましたが、F問題を解いたのは初めてです！

|問題|時間|アルゴリズム|実行時間
|:-:|:-:|:-:|:-:|
| A | 1min |-|1ms|
| B | 2min |-|1ms|
| C | 1min |最小公倍数|1ms|
| D | 6min |貪欲法|18ms|
| E | 8min |素因数|1ms|
| F | - |グラフ|45ms|



## A
```c++
	int a, b;
	cin >> a >> b;
	cout << 6 - a - b;
```
`a, b` は `1, 2, 3` のどれかなので、`6 - a - b` の計算で`a`でも`b`でもない数字がわかりますね。
3つ目の数字を`c`とすると `a + b + c = 6` という式が成り立つので、移項するとこの式が出てきます。

## B
``` c++
	int n;
	string s, t;
	cin >> n >> s >> t;
	for(int i = 0; i < n; ++i)
	{
		cout << s[i] << t[i];
	}
```
やるだけ

## C
``` c++
// 最大公約数 : 3,4 ->  1
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

// 最小公倍数 : 3,4 -> 12
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }

void solve()
{
	int a, b;
	cin >> a >> b;
	cout << lcm(a, b);
}
```
2つの入力値の最小公倍数が答えになるので計算するだけです。

## D


``` c++
	int n, a;
	cin >> n;

	int now_num = 1;
	int cnt = 0;

	for(int i = 0; i < n; ++i)
	{
		cin >> a;
		if (a == now_num)
		{
			cnt++;
			now_num++;
		}
	}

	if (now_num == 1)
	{
		cout << -1;
	}
	else
	{
		cout << n - cnt;
	}
```
`1,2,3,...`と求める数はわかるので、入力値が求める数でなかったらブロックを壊すことを続けていれば解けます。


## E

```c++
	ll n;
	cin >> n;
	if (n & 1)
	{
		cout << 0;
		return;
	}

	ll ans = 0;

	// 5 の個数を数える
	ll five_pow = 5;
	while(five_pow < n)
	{
		ans += n / five_pow / 2;
		five_pow *= 5;
	}
	cout << ans;
```
`O(log5 N)`です。
`10`の素因数分解は`5 * 2`です。
`f(n)`を素因数分解すると`p * 5^a * 2^b : (pは自然数. a, b は0以上の整数)` の形になります。
この`a`と`b`に注目すれば、後ろに`0`が何個続くかわかります。
`n`が奇数の時には `b = 0` のため答えは `0` です。
`n`が偶数の時には明らかに `a < b` といえるので、`a`の個数を調べればいいです。
つまり、`5`で何回割り切れるかを計算します。
例えば`n = 80`のとき、`f(n)`の中で`5`の倍数である数値は`80,70,60,50,40,30,20,10`です。
このなかに含まれる`5`は9個ですね。`50`は`5*5*2`なので`5`を2つ含んでいることに注意です。
この個数は`80 / 10` と `80 / 50` で計算できます。(端数切り捨て)
`80 / 10`で`5`を1つ以上含む数の個数、
`80 / 50`で`5`を2つ以上含む数の個数です。
ここまできたら、あとは一般化しましょう。
`n / (10 * 5^a)`によって`5`を`a`個以上含む数の個数が分かります。
その総和が答えになります。


## F

``` c++
	int n, u, v;
	cin >> n >> u >> v;
	u--; v--;

	vector< vector<int> > node(n, vector<int>() );
	vector<int> dist_u(n, -1);
	vector<int> dist_v(n, -1);

	int a, b;
	for(int i = 0; i < n - 1; ++i)
	{
		cin >> a >> b;
		a--; b--;
		node[a].emplace_back(b);
		node[b].emplace_back(a);
	}

	queue<int> que;
	que.push(u);

	dist_u[u] = 0;

	// ゲームは必ず終了することが証明できる
	// つまり閉路はない
	// BFSで経路長探索
	while(!que.empty())
	{
		int now = que.front();
		que.pop();
		for(const auto& next : node[now])
		{
			if (dist_u[next] == -1)
			{
				dist_u[next] = dist_u[now] + 1;
				que.push(next);
			}
		}
	}

	// queはemptyだから使いまわせる...けれどこれは関数化したい
	que.push(v);
	dist_v[v] = 0;

	while(!que.empty())
	{
		int now = que.front();
		que.pop();
		for(const auto& next : node[now])
		{
			if (dist_v[next] == -1)
			{
				dist_v[next] = dist_v[now] + 1;
				que.push(next);
			}
		}
	}

	int ans = -1;
	for(int i = 0; i < n; ++i)
	{
        if(dist_u[i] < dist_v[i])
		{
	        ans = max(ans, dist_v[i]);
		}
	}

	cout << ans - 1;
```
`O(N)`です。
BFSをしていますが、DFSでも計算量や結果は同じです。
`queue` を `stack` にすればDFSになりますね。
問題文よりこのグラフは木なので、閉路はないことが分かります。
すでに来たことがあるノードかどうかの判定が不要になるので、探索が楽になりますね。

その木の上で`u`が逃げて、`v`が追いかけます。
逃げる`u`は`v`から最も遠いノードへ移動するのが最善手です。移動中に`v`につかまらないように注意してください。
答えは`v`の移動量になります。
`u`が逃げ込むノードと`v`との距離が答えです。

つまり、
・`u`の初期位置から各ノードへの距離
・`v`の初期位置から各ノードへの距離
の2つが必要です。合計で2回の探索をして、走査すれば答えが出せます。


以上です。ありがとうございました。