競技プログラミング練習記 No.5【ABC151練習】

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

[ABC151](https://atcoder.jp/contests/abc151)を解きました。
3完です。
D問題は自力で解けたのですが時間切れでした。

|問題|時間|アルゴリズム|
|:-:|:-:|:-:|
| A |  1min |char型|
| B | 10min |平均値|
| C |  8min |-|
| D |110min |幅優先探索|



## A
```c++
	char c;
	cin >> c;
	c++;
	cout << c;
```
char型は内部的には文字コードを数値として持っていて、`+1`すると次の文字になります。
`+2`すると2つ先の文字になります。
大文字⇔小文字の変換を手動でするときにも使えます。
``int five = `5` - `0`; `` とすると、`five`に数値の`5`が入るのもこれを利用しているからですね。

## B
``` c++
	int n, k, m, a, sum = 0;
	cin >> n >> k >> m;
	for(int i = 0; i < n - 1; ++i)
	{
		cin >> a;
		sum += a;
	}
	int next_score = n * m - sum;
	cout << (next_score <= k ? max(0, next_score) : -1);
```
平均値の計算式を考えれば、平均値を出さなくても解けますね。
境界値で少しはまりました。反省。

## C
``` c++
	int n, m, p;
	string s;
	cin >> n >> m;

	vector<int> problems(n, -1);
	for(int i = 0; i < m; ++i)
	{
		cin >> p >> s;
		p--;
		if (problems[p] <= 0)
		{
			if (s == "WA")
			{
				problems[p]--;
			}
			else if(s == "AC")
			{
				problems[p] *= -1;
			}
		}
	}

	int ans_ac = 0;
	int ans_wa = 0;
	for(const auto& v : problems)
	{
		if (v > 0)
		{
			++ans_ac;
			ans_wa += v - 1;
		}
	}
	cout << ans_ac << " " << ans_wa;
```
通常はサイズ`n`のbool配列を用意して解くことが多いかもしれません。
変数を増やしたくなかったので`vector<int> problems`だけでやっています。
値が負の時はWAをしていて、ACしたら符号を反転させています。
`0`は正でも負でもないので除外されるようにしました。


## D


``` c++
#define X first
#define Y second

using Pair = pair<int, int>;
const int BLOCK = 100000;

void solve()
{
	int h, w;
	cin >> h >> w;

	int ans = 0;

	vector< vector<int> > initial_maze( h, vector<int>(w, -1) );

	string s;
	for(int i = 0; i < h; ++i) {
		cin >> s;
		for(int j = 0; j < w; ++j) {
			initial_maze[i][j] = ((s[j] == '.') ? -1 : BLOCK);
		}
	}

	for(int i = 0; i < w; ++i) {
		for(int j = 0; j < h; ++j) {
			if (initial_maze[j][i] == BLOCK) { continue; }
			vector< vector<int> > maze( initial_maze );

			queue<Pair> que;
			Pair p(make_pair(i, j));
			maze[j][i] = max(0, maze[j][i]);
			que.push(p);

			int dx[4] = { 0, 1, 0, -1 };
			int dy[4] = { 1, 0, -1, 0 };

			while(!que.empty()){
				Pair now = que.front();
				que.pop();

				for(int k = 0; k < 4; ++k) {
					int next_x = now.X + dx[k];
					int next_y = now.Y + dy[k];
					if (next_x < 0 || w <= next_x || next_y < 0 || h <= next_y) { continue; }

					if (maze[next_y][next_x] == -1) {
						Pair next(make_pair(next_x, next_y));
						maze[next.Y][next.X] = maze[now.Y][now.X] + 1;
						que.push(next);
					}
				}
			}

			for(int y = 0; y < h; ++y) {
				for(int x = 0; x < w; ++x) {
					if (maze[y][x] != BLOCK) { ans = max(ans, maze[y][x]); }
				}
			}
		}
	}
	cout << ans;
}
```

迷路といえば幅優先探索です。略してBFS。
PAST3でも出たのでタイムリーですね。
コストの更新と `queue` に詰める処理を別のところでやっていたらTLEになり、気付くまで時間がかかりました。

コードがながめです。短くしたい。（ながいので整形しています）

コンテスト時は座標とコストを持った`struct`を使って解いたのですが、Pairと経路コストの配列があれば解けました。
シンプルな方がバグりにくい。気をつけねば。

BFS本体はこの部分。`dx[4]` と `dy[4]` のテクニックはよく使います。

``` c++
			queue<Pair> que;
			Pair p(make_pair(i, j));
			maze[j][i] = max(0, maze[j][i]);
			que.push(p);

			int dx[4] = { 0, 1, 0, -1 };
			int dy[4] = { 1, 0, -1, 0 };

			while(!que.empty()){
				Pair now = que.front();
				que.pop();

				for(int k = 0; k < 4; ++k) {
					int next_x = now.X + dx[k];
					int next_y = now.Y + dy[k];
					if (next_x < 0 || w <= next_x || next_y < 0 || h <= next_y) { continue; }

					if (maze[next_y][next_x] == -1) {
						Pair next(make_pair(next_x, next_y));
						maze[next.Y][next.X] = maze[now.Y][now.X] + 1;
						que.push(next);
					}
				}
			}
```

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