競技プログラミング練習記 No.20【ABC138練習】

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

[ABC138](https://atcoder.jp/contests/abc138)を解きました。
4完です。
D問題につまって、他の人のコードをみました。

|問題|時間|アルゴリズム|実行時間
|:-:|:-:|:-:|:-:|
| A |   1min |-|6ms|
| B |   3min |-|6ms|
| C |   2min |-|8ms|
| D | 110min |木|129ms|
| E |  55min |文字列マッチング|1415ms|


## A - Red or Not
```c++
	int a;
	string s;
	cin >> a >> s;
	cout << (3200 <= a ? s : "red");
```
そのままやるだけですね。
問題文もプログラムにしやすい書き方だと思います。

## B - Resistors in Parallel
``` c++
	int n;
	double a;
	double sum = 0.0;
	cin >> n;
	for(int i = 0; i < n; ++i)
	{
		cin >> a;
		sum += 1.0 / a;
	}
	printf("%.7f", 1.0 / sum);
```
数学的にシンプルな式が思いつかなかったのでそのままやりました。
丸め精度が不安でしたが、`10^-5`程度の誤差は許容とあったので助かりました。

## C - Alchemist
``` c++
	int n;
	cin >> n;
	vector<double> v(n);
	for(int i = 0; i < n; ++i)
	{
		cin >> v[i];
	}
	sort(v.begin(), v.end());

	double value = v[0];
	for(int i = 1; i < n; ++i)
	{
		value = (value + v[i]) / 2.0;
	}
	printf("%.7f", value);
```
ぶちゃけると数学的な考察はしていません。

暴論ととらえられるかもしれませんが、私なりの競技プログラミングのコツです。
`こういう時`はほとんどの場合で昇順か降順でソートして計算すると答えになります。
今回は最大値を求める問題だったので、昇順と降順で値が大きくなった方を選びました。
もしダメだったらその時に考えていたと思います。

`※こういう時`
・数列の要素ごとに処理する
・処理した順番によって値が変わる
・求まる値を最大化・最小化する
・四則演算を使う (mod とか xor とか約数とかは使わない)

## D - Ki

``` c++
vector< vector<int> > edge(200004, vector<int>());
ll counter[200004];
bool seen[200004];

void dfs(int node) // search child
{
	if (seen[node]) { return; }
	seen[node] = true;

	for(const auto& e : edge[node]) {
		if (seen[e]) { // 親
			counter[node] += counter[e];
			break;
		}
	}

	for(const auto& e : edge[node]) {
		if (!seen[e]) { // 子
			dfs(e);
		}
	}
}

void solve()
{
	fill(counter, counter + 200004, 0);
	fill(seen, seen + 200004, false);

	ll n, q, a, b, p, x;
	cin >> n >> q;

	for(ll i = 0; i < n - 1; ++i) {
		cin >> a >> b;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}
	for(ll i = 0; i < q; ++i) {
		cin >> p >> x;
		counter[p] += x;
	}

	dfs(1);
	for(int i = 1; i <= n; ++i)
	{
		cout << counter[i] << " ";
	}
}
```
愚直にやると`O(N^3)`くらいでしょうか。
`N = [2, 200000]`なので余裕をもってTLEしますね。

問題文には
> 点 p_j を根とする部分木に含まれるすべての頂点のカウンターの値に x_j を足す。 

とありますが、部分木のすべての頂点ではなく根のカウンターのみ更新します。
入力をすべてそのように処理したあと、各頂点から根に向かって移動します。
移動時に通った頂点のカウンターをすべて足した値が頂点のカウンターになりますね。
いわゆる葉から根へ向かう処理です。
このやり方だと`O(N logN)`となります。

さて、解き方自体はわかったのですが、データの持ち方をミスりました。
この問題は入力時点での親子関係は不明ですね。(普通の問題は、特に言及されていなければ不明です。)
それとは気づかずに葉から根へ向かう処理を書いていました。
そのために木構造がうまく設定されず、WAを量産しました。反省。

他の人の解法を見て、根から葉へ向かう処理にしました。
葉から根へ向かっても、根から葉へ向かっても、計算量は同じ`O(N logN)`です。

## E - Strings of Impurity

```c++
	string s, t;
	cin >> s >> t;
	ll s_size = s.length();
	ll t_size = t.length();

	vector<int> bin[26] = {};
	for(int i = 0; i < s_size; ++i)
	{
		bin[ s[i] - 'a' ].emplace_back(i);
	}
	for(int i = 0; i < t_size; ++i)
	{
		if (bin[ t[i] - 'a' ].empty())
		{
			cout << "-1";
			return;
		}
	}

	vector<int> t_num(t_size, -1);
	t_num[0] = bin[ t[0] - 'a' ][0];
	for(int i = 1; i < t_size; ++i)
	{
		t_num[i] = bin[ t[i] - 'a' ][0];
		for(int j = 0; j < bin[ t[i] - 'a' ].size(); ++j)
		{
			if (bin[ t[i] - 'a' ][j] > t_num[i - 1])
			{
				t_num[i] = bin[ t[i] - 'a' ][j];
				break;
			}
		}
	}

	ll ans = 0;
	for(int i = 1; i < t_size; ++i)
	{
		if (t_num[i - 1] >= t_num[i])
		{
			ans += s_size;
		}
	}
	cout << ans + t_num.back() + 1;
```
ACしましたが実行時間かかりすぎです。反省。
`O(|t|^2)` です。制約は`|t| = [1, 10000]` なので普通はTLEです。
実際の計算量は `|t|*|t| / 26`程度のため、なんとかACになりました。

実行時間がかかっているのであまりスマートではないですが、解法です。

↓
↓
↓

`t`の各文字が`s`の何番目の文字かを配列に保存します。
その配列はできる昇順の長さが大きくなるようにします。

例えば`s = "constest", t = "tston"` のとき
`s_num : { 1,2,3,4,5,6,7 }` として
`t_num : { 4,6,4,2,3 }`
となります。
`s`の中に"t"という文字は`4,7`の2つです。つまり、"t"は`4`と`7`のどちらでもいいです。
この時、`t_num`の2つめの`4`を`7`にすると昇順の長さが増えますね。
つまり、
`t_num : { 4,6,4,2,3 }`
よりも
`t_num : { 4,6,7,2,3 }` 
のほうが昇順になっている長さが大きいです。

このように`t_num`を設定すると、`t_num`の値を順にみていったとき、
・前の値よりも小さくなった時に`|s|`を加算
・`t_num`の最後まで来たらその時の値を加算
の結果が答えになります。



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