競技プログラミング練習記 No.25【ABC134練習】

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

[ABC134](https://atcoder.jp/contests/abc134)を解きました。
4完です！
E問題は解説を見て解きました。

|問題|時間|アルゴリズム|実行時間
|:-:|:-:|:-:|:-:|
| A |  1min |-|8ms|
| B |  3min |-|8ms|
| C | 15min |-|41ms|
| D | 35min |xor|30ms|
| E | - |最長増加部分列|34ms|



## A - Dodecagon
```c++
	int r;
	cin >> r;
	cout << 3 * r * r;
```
問題文に数式が載っているので、当てはめると答えが出ます。

問題名が面白いですね。ドデカゴン。ちなみに12角形の正式名称です笑。

## B - Golden Apple
``` c++
	int n, d;
	cin >> n >> d;
	cout << (n - 1) / (2 * d + 1) + 1;
```

ひとりの見れる範囲が`[i−D, i+D]`なので、ひとりあたり`2D + 1`の範囲を見れますね。
そのため、範囲`N`を監視するのに必要な人は、`N`を`2D+1`で割って切り上げたものだとわかります。

double型にキャストして`ceil(N / (2D+1))`で計算できます。
int型のままで`N / D`の切り上げをすることもできて、今回はそれを使いました。
`( (N - 1) / D ) + 1` の式です。

## C - Exception Handling
``` c++
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; ++i)
	{
		cin >> a[i];
	}
	int max1 = 0;
	int max2 = 1;
	for(int i = 1; i < n; ++i)
	{
		if (a[max1] < a[i])
		{
			max2 = max1;
			max1 = i;
		}
		else if (a[max2] < a[i])
		{
			max2 = i;
		}
	}
	for(int i = 0; i < n; ++i)
	{
		cout << (i == max1 ? a[max2] : a[max1]) << endl;
	}
```
そのまますると`O(N^2)`となってTLEします。

解き方としては、数列の中で一番大きいものと二番目に大きいものを覚えておきます。
・一番大きい要素の時は二番目に大きいものを出力
・それ以外は一番大きいものを出力
とすると答えになります。
同じ要素が二つ以上あるときにうまくいかない恐れがあったので、インデックスで管理しています。
と書きましたが、今思い返すとインデックス管理は不要だったかもしれません。（複雑にしただけかもです）

## D - 	Preparing Boxes


``` c++
	int n;
	cin >> n;
	vector<int> a(n + 1, 0);
	for(int i = 1; i <= n; ++i)
	{
		cin >> a[i];
	}

	// 1は考えなくていい
	// 半分以降は決まり：倍数が1つだけ
	// 前半の半分について考える
	bitset<200000 + 1> ball;
	for(int i = n / 2 + 1; i <= n; ++i)
	{
		ball[i] = a[i];
	}

	for(int i = n / 2; i >= 1; --i)
	{
		int next_b = a[i];
		for(int j = i * 2; j <= n; j += i)
		{
			next_b ^= ball[j];
		}
		ball[i] = next_b;
	}

	cout << ball.count() << endl;
	for(int i = 1; i <= n; ++i)
	{
		if (ball[i]) cout << i << " ";
	}
```

各要素に対して2で割った余りを求めるとあるので、2進数が思い浮かびます。
bitmaskやxorを使います。
「いいボールの入れ方」のうち、`i`番目の箱に関係するのは`i, 2*i, 3*i, ...`です。
この時、入力サイズ`N`に対して、`N/2 ~ N`番目の箱に関係するのは`i`番目の入力値だけですね。
というのも、`2*i`が`N`より大きくなってしまうためです。
つまり、`N/2 ~ N`番目については入力値がそのまま「いいボールの入れ方」になります。

また、どの箱にも`i`番目の箱は自由に設定できます。
`2*i + 3*i + 4*i + ...` の値がどうなっていようと、`i`番目の箱にボールを入れるか入れないかで結果を操作できます。
このようにどの箱も結果を自由に操作できるので、必ず「いいボールの入れ方」は存在します。
つまり出力結果に`-1`はありません。

また、試してみると、入力値を`a`、箱を`b`として
`b[i] = a[i] ^ b[2*i] ^ b[3*i] ^ ...`
であることが分かります。
この形になっているため、`b`は上から更新する必要があります。

ここまでわかれば実装です。
実装時は境界値に注意です。

## E - Sequence Decomposing

```c++
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; ++i)
	{
		cin >> a[i];
	}
	reverse(a.begin(), a.end());

	vector<int> dp(n, INF);
	for(int i = 0; i < n; ++i)
	{
		*upper_bound(dp.begin(), dp.end(), a[i]) = a[i];
	}
	cout << lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
```
最長増加部分列（LIS）です。
今回の問題は最長現象部分列の長さが答えになる問題でした。
数列を`reverse`させればLISに帰着できます。

LISの発想はあったのに解けなくて悔しいです。次は解きたい。
プログラムは[蟻本](https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%82%B3%E3%83%B3%E3%83%86%E3%82%B9%E3%83%88%E3%83%81%E3%83%A3%E3%83%AC%E3%83%B3%E3%82%B8%E3%83%96%E3%83%83%E3%82%AF-%E7%AC%AC2%E7%89%88-%EF%BD%9E%E5%95%8F%E9%A1%8C%E8%A7%A3%E6%B1%BA%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E6%B4%BB%E7%94%A8%E5%8A%9B%E3%81%A8%E3%82%B3%E3%83%BC%E3%83%87%E3%82%A3%E3%83%B3%E3%82%B0%E3%83%86%E3%82%AF%E3%83%8B%E3%83%83%E3%82%AF%E3%82%92%E9%8D%9B%E3%81%88%E3%82%8B%EF%BD%9E-%E7%A7%8B%E8%91%89%E6%8B%93%E5%93%89/dp/4839941068/)にあったものを`vector`になおして使いました。

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