競技プログラミング練習記 No.31【ABC129練習】

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

[ABC129](https://atcoder.jp/contests/abc129)を解きました。
4完です！

|問題|時間|アルゴリズム|実行時間
|:-:|:-:|:-:|:-:|
| A |  1min |-| 6ms|
| B |  9min |しゃくとり法| 8ms|
| C |  7min |動的計画法|15ms|
| D | 48min |ランレングス圧縮|145ms|

E問題は解けていないです。桁DPの問題なのですが、気付くこともできませんでした。
悔しい。復習しておきます。



## A - 	Airplane
```c++
	int p, q, r;
	cin >> p >> q >> r;
	cout << min ( {p+q, q+r, r+p} );
```
問題文が複雑ですが、`P+Q, Q+R, R+P`の最小値を求める問題ですね。
`min`関数は引き数にタプルを指定することで3要素の比較をできます。

## B - 	Balance
``` c++
	int n;
	cin >> n;
	vector<int> w(n);
	int g1 = 0;
	int g2 = 0;
	for(int i = 0; i < n; ++i)
	{
		cin >> w[i];
		g2 += w[i];
	}
	int ans = 10000;
	for(int i = 0; i < n; ++i)
	{
		g1 += w[i];
		g2 -= w[i];
		ans = min(ans, abs(g2 - g1));
	}
	cout << ans;
```
問題文より
> 番号が T 以下の重り と 番号が T より大きい重りの 2 グループに分けることを考え、それぞれのグループの重さの和を S1,S2 とします。

とありますね。
区間を区切った両側の総和を比べる問題で、区切る位置が１つずつずれます。
つまり、しゃくとり法だと高速に解けますね。
（今回の制約ではしゃくとりり法を使わなくても解くことができます。）

区間をずらしながら差の絶対値を比較して答えです。

## C - 	Typical Stairs
こちらのライブラリを使いました。
https://github.com/atcoder-live/library/blob/master/mint.cpp

``` c++
	int n, m, input;
	cin >> n >> m;
	vector<bool> a(n, true);
	for(int i = 0; i < m; ++i)
	{
		cin >> input;
		a[input] = false;
	}

	vector<mint> dp(n + 1, 0);
	dp[0] = 1;
	dp[1] = a[1] ? 1 : 0;
	for(int i = 2; i <= n; ++i)
	{
		if(a[i]) dp[i] = dp[i-2] + dp[i-1];
	}
	cout << dp[n];
```
動的計画法ですね。
`dp[i] = i段目にたどり着く移動方法` です。

また、1歩で 1 段か 2 段上ることができるので、
`dp[i] = dp[i-1] + dp[i-2]`が成り立ちますね。
→`i`段目には、1段前か2段前からくることができるという式です。

PAST3にも似たハードルの問題が出ていましたね。

漸化式がわかったら実装です。
壊れている床に注意です。

## D - Lamp


``` c++
	int h, w;
	cin >> h >> w;
	vector<string> s(h);
	for(int i = 0; i < h; ++i)
	{
		cin >> s[i];
	}

	vector< vector<int> > runlength_h(h, vector<int>(1, 1));
	for(int y = 0; y < h; ++y)
	{
		for(int x = 1; x < w; ++x)
		{
			if (s[y][x-1] == s[y][x]) runlength_h[y].back() += 1;
			else runlength_h[y].emplace_back(1);
		}
	}
	vector< vector<int> > runlength_w(w, vector<int>(1, 1));
	for(int x = 0; x < w; ++x)
	{
		for(int y = 1; y < h; ++y)
		{
			if (s[y][x] == s[y-1][x]) runlength_w[x].back() += 1;
			else runlength_w[x].emplace_back(1);
		}
	}

	int ans = 0;
	vector< vector<int> > score(h, vector<int>(w, 0));
	for(int y = 0; y < h; ++y)
	{
		int index = 0;
		for(const int& r : runlength_h[y])
		{
			for(int i = index; i < index + r; ++i) score[y][i] += r;
			index += r;
		}
	}
	for(int x = 0; x < w; ++x)
	{
		int index = 0;
		for(const int& r : runlength_w[x])
		{
			for(int i = index; i < index + r; ++i) score[i][x] += r;
			index += r;
		}
	}

	for(int y = 0; y < h; ++y)
	{
		for(int x = 0; x < w; ++x)
		{
			if (s[y][x] == '.') 
			{
				score[y][x]--;
				ans = max(ans, score[y][x]);
			}
		}
	}
	cout << ans;
```
そのままやるとO((W*H)^2)なのでTLEですね。
高速に解くために[ランレングス圧縮](https://www.google.com/search?q=%E3%83%A9%E3%83%B3%E3%83%AC%E3%83%B3%E3%82%B0%E3%82%B9%E5%9C%A7%E7%B8%AE&oq=%E3%83%A9%E3%83%B3%E3%83%AC%E3%83%B3%E3%82%B0%E3%82%B9%E5%9C%A7%E7%B8%AE)をしました。

実行速度は速いのですが、バグりやすい書き方です。。。

この問題は`'.'`の文字が横と縦に連続している回数がスコアになりますね。
ランレングス圧縮は文字が連続する回数を数字で表すので相性がいいです。

スコアは横と縦の2方向に関係しているので、横方向と縦方向の2方向にランレングス圧縮をします。
これは`O(W*H)`が2回です。

圧縮した後は、`O(W*H)`で各マスのスコアを計算できますね。
スコアを配列に記録して、横と縦の2方向分のスコアを計算します。

最後に、計算したスコアの中の最大値を答えにします。

このやり方だとO(W*H)となるので、時間内に解ききれます。

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