競技プログラミング練習記 No.21【ABC137練習】

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

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

|問題|時間|アルゴリズム|実行時間
|:-:|:-:|:-:|:-:|
| A |  1min |-|7ms|
| B |  3min |-|6ms|
| C | 12min |ヒストグラム|53ms|
| D | 27min |動的計画法|41ms|
| E | - |ベルマンフォード法|88ms|

## A - 	+-x
```c++
	int a, b;
	cin >> a >> b;
	cout << max( { a + b, a - b, a * b } );
```
そのままですね。
3つの計算結果の`max`をとると答えになります。
`max`関数の引数にタプルをもってこれるのは初めて知りましたw

## B - One Clue
``` c++
	int k, x;
	cin >> k >> x;
	for(int i = x - k + 1; i < x + k; ++i)
	{
		cout << i << " ";
	}
```
座標Xに黒い石が置かれていて、その左右隣が白い石になる場合を考えるといいですね。
つまり境界値を考えます。
`[ x - k + 1, x + k - 1 ]` の範囲が答えになります。


## C - Green Bin
``` c++
	int n;
	cin >> n;
	unordered_map< string, ll > ana_list;

	string s;
	for(int i = 0; i < n; ++i)
	{
		cin >> s;
		sort(s.begin(), s.end());
		ana_list[s]++;
	}

	ll ans = 0;
	for(const auto& ana : ana_list)
	{
		ans += ana.second * (ana.second - 1LL) / 2LL;
	}
	cout << ans;
```
ヒストグラムが使えますね。
ヒストグラムはbin sortで使う考え方ですが、問題名の「Green Bin」より想起されました。

受け取った文字列をソートすると、アナグラムの関係にある文字列は同じ一意の結果になります。
つまり、ソート後の文字列が何回現れたかを記憶しておけば答えは出せます。

ハッシュマップより、ソート後の文字列をkeyとして発生回数を記憶しています。
最後に組み合わせ `nC2`の計算式をつかって答えを出しました。


## D - 	Summer Vacation

``` c++
	int n, m;
	cin >> n >> m;
	vector<P> job(n);

	for(int i = 0; i < n; ++i)
	{
		int a, b;
		cin >> a >> b;
		job[i] = P(a, b);
	}

	sort(job.begin(), job.end());
	priority_queue<int> job_score;

	ll ans = 0;
	int job_index = 0;
	for(int i = 1; i <= m; ++i)
	{
		while(job_index < n && job[job_index].first <= i)
		{
			job_score.push(job[job_index].second);
			job_index++;
		}
		if (!job_score.empty())
		{
			ans += job_score.top();
			job_score.pop();
		}
	}
	cout << ans;
```
残り`i`日の時にできる最も報酬の多い仕事をするのが基本方針です。
ですが、それだけでは入力例 2のような場合に解くのが難しくなります。

問題文をそのまま受け取ると、残り日数を`M`日から`1`日まで減らしていくように読み取れます。
残り日数を減らしていくと選べる仕事が減っていき、考えるべき変数が`残り日数, 仕事の期間, 報酬`の3つになります。

逆に、残り日数を`1`日から`M`日まで増やしてみます。
すると、残り日数を増やしていくと選べる仕事が増えていき、`残り日数`と`仕事の期間`は考える必要がなくなります。
つまり、`報酬`のみを考えればいいです。

逆に考えると変数が1つになって考えやすくなりましたね。この方針なら解けそうです。
そしてこれが正しい考え方です。

今回は報酬の合計を最大化するので、選べる仕事のうち最も報酬が大きいものを選べば答えになります。
最大値だけわかればいいので`priority_queue(heap)`の出番ですね。
選べる仕事を抽出し、その報酬を`priority_queue`に入れて計算すれば答えになります。


## E - 	Coins Respawn

```c++
vector<int> to[2505];
vector<int> reverse_to[2505];
bool ok[2505];
bool reachableFrom1[2505];
bool reachableFromN[2505];

void dfs(int v) {
	if (reachableFrom1[v]) return;
	reachableFrom1[v] = true;
	for(const auto& u : to[v]) dfs(u);
}

void dfs_reverse(int v) {
	if (reachableFromN[v]) return;
	reachableFromN[v] = true;
	for(const auto& u : reverse_to[v]) dfs_reverse(u);
}

void solve() {
	fill(ok, ok + 2505, false);
	fill(reachableFrom1, reachableFrom1 + 2505, false);
	fill(reachableFromN, reachableFromN + 2505, false);

	int n, m, p;
	cin >> n >> m >> p;

	vector<Edge> edges;
	vector<int> dist(n, INF);
	dist[0] = 0;

	for(int i = 0; i < m; ++i) {
		Edge edge;
		cin >> edge.from >> edge.to >> edge.cost;
		edge.from--;
		edge.to--;
		edge.cost -= p;
		edge.cost *= -1; // コストを反転させて最短経路問題を解けば、最長経路になる

		edges.emplace_back(edge);
		to[edge.from].emplace_back(edge.to);
		reverse_to[edge.to].emplace_back(edge.from);
	}

	dfs(0);
	dfs_reverse(n - 1);
	for(int i = 0; i < n; ++i) ok[i] = reachableFrom1[i] & reachableFromN[i];

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			Edge e = edges[j];
			if(!ok[e.to]) continue;
			if(!ok[e.from]) continue;

			if (dist[e.to] > dist[e.from] + e.cost) {
				dist[e.to] = dist[e.from] + e.cost;
				if (i == n - 1) {
					cout << -1;
					return;
				}
			}
		}
	}
	cout << max(dist[n - 1] * -1, 0);
}
```
長いです。。。行数をおさえるためにすこし整形しました。
青difficultyの問題です。
あまり多く解いたことはありませんが、青difficultyの問題は長いものが多い印象です。慣れなきゃ。

この問題について･･･
・始点が決まっています。

・グラフ上を移動するたびに報酬がもらえて、最後に移動した回数だけ`p`が引かれます。
　ただ、最後に`p`を引く処理は移動中にしても結果は同じです。
　つまり、各枝の報酬から先に`p`を引いても大丈夫です。この時に負の値が出てきます。

・閉路が存在して報酬が無限に大きくなります。

・報酬を最大化する問題ですが、報酬の正負を反転すれば報酬を最小化する問題になります。
　つまり最短経路問題です。


長くなりましたが、この問題は「負閉路あり負数重み付き有向グラフの単一始点最短経路問題」に帰着できます。
つまりベルマンフォード法ですね。使ったのは今回が初めてです。

ただ、ここで終わらないのが青difficultyというか、それだけでは解けません。
始点と終点の間に負閉路があった場合には`-1`を出力するのですが、その検出はベルマンフォード法ではできません。
（始点と終点に関係なく負閉路があるかは検出できます。）

その検出を先にDFSでやります。
`dfs(0);`
`dfs_reverse(n - 1);`
の部分ですね。
始点と終点の両方から到達できない点について、ベルマンフォード法の処理をさせないようにします。

ここまでやってACです。長かった。

できるひとは「おっ、ベルマンフォードか」「でも閉路がちょっと良くないな」「始点と終点からdfsするか」
と一瞬でなるのでしょうか。その高みにいきたいです。これはその高みに続く一歩ですね。

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