競技プログラミング練習記 No.24【ABC135練習】

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

[ABC135](https://atcoder.jp/contests/abc135)を解きました。
3完です。
D問題は解説を見て解きました。

|問題|時間|アルゴリズム|実行時間
|:-:|:-:|:-:|:-:|
| A |  2min |-|6ms|
| B |  4min |-|6ms|
| C |  8min |-|31ms|
| D | - |動的計画法|37ms|

## A - Harmony
```c++
	int a, b;
	cin >> a >> b;
	if ((a + b) & 1)
	{
		cout << "IMPOSSIBLE";
	}
	else
	{
		cout << (a + b) / 2;
	}
```
`|A-K|=|B-K|`を`K`について解きたいのですが、絶対値をそのまま外すと`K`が消えてしまいます。
そこで、右辺に-1をかけた状態で絶対値を外してみます。（絶対値の性質からこの操作ができます）
`A-K=-B+K`となるので、これを`K`について解くと`K = (A+B)/2`となります。
これは`A`と`B`の平均値ですね。

数学的には他にも場合分けがあるのですが、
絶対値がついている元の式に代入してみると、正しい答えだと分かります。
答えは整数なので、平均値が少数になるときは答えがないことに注意です。
`if ((a + b) & 1)`で偶奇判定をしています。

どちらでもいいのですが、回答を出力する部分は三項演算子で1行にまとめられましたね。
`if - else`項は考えやすくなるという利点があります。

## B - 0 or 1 Swap
``` c++
	int n, p, differ_num = 0;
	cin >> n;
	for(int i = 0; i < n; ++i)
	{
		cin >> p;
		if(p != i + 1) differ_num++;
	}
	cout << (differ_num <= 2 ? "YES" : "NO");
```
逆に考えて、昇順に並び替えられた数列からどこかをswapして、入力の数列と一致すればいいですね。
数列の要素は{1,2,...,N}と決まっているので、昇順に並び替えられた状態はすぐにわかります。

並び替えられた数列と入力数列とで違っている箇所を数え上げて、
違っている箇所が2か所以内なら、1回のswapで2つの数列を一致させられます。

ここまでわかれば実装です。書き方はいろいろありますが、私は上のように書きました。

## C - City Savers
``` c++
	ll n;
	cin >> n;
	vector<ll> a(n + 1);
	vector<ll> b(n);
	for(int i = 0; i < n + 1; ++i) { cin >> a[i]; }
	for(int i = 0; i < n; ++i) { cin >> b[i]; }

	ll ans = 0;
	for(int i = 0; i < n; ++i)
	{
		if (a[i] <= b[i])
		{
			ans += min(b[i], a[i] + a[i + 1]);
			a[i + 1] = max(0LL, a[i + 1] + a[i] - b[i]);
		}
		else
		{
			ans += b[i];
		}	
	}
	cout << ans;
```
`b[i]`の人は`a[i]`と`a[i+1]`のモンスターを倒せます。
`a[i]`のモンスターは`b[i-1]`と`b[i]`の人が倒せます。

`a[0]`を考えると、`a[0]`のモンスターを倒せるのは`b[0]`の人だけです。
そのため、`b[0]`の人はまず`a[0]`を倒し、余力で`a[1]`のモンスターを倒します。
もし`b[0]`の人が`a[0]`でなく`a[1]`を先に倒してしまうと、`a[0]`に割く力が減ってモンスターを倒しきれないかもしれません。
さらには`b[1]`の人が倒すモンスターの数が減ることも考えられます。
これでは倒せるモンスターの合計数が減ってしまいます。

そのため、`b[i]`の人は`a[i]`のモンスターを倒し、残った力で`a[i+1]`を手伝うという行動が最善手になります。

## D - Digits Parade


``` c++
	string s;
	cin >> s;
	
	ll dp[100005][13];
	for(int i = 0; i < 13; ++i) dp[0][i] = 0;
	dp[0][0] = 1;

	int len = s.length();
	for(int i = 0; i < len; ++i)
	{
		for(int j = 0; j < 13; ++j) dp[i + 1][j] = 0;

		int num = ((s[i] == '?') ? -1 : s[i] - '0');
		for(int j = 0; j < 10; ++j)
		{
			// num が数字の時はその数のみ、? のときは0~9について計算
			if (num != -1 && num != j) continue;
			for(int k = 0; k < 13; ++k)
			{
				dp[i + 1][(k * 10 + j) % 13] += dp[i][k];
			}
		}
		for (int j = 0; j < 13; ++j)
		{
			dp[i + 1][j] %= MOD;
		}
	}
	cout << dp[len][5];
```
DPです。
問題名からしてDPですね。というのも「Digits Parade」の頭文字をとると「DP」になります笑。
DP慣れたい。こういうのはわからないながらも解いていると、ある日ふと解けるようになっているものです。
ソースは私。焦らず、1つずつ理解していきます。

さて、このプログラムの肝は以下の部分です。
`dp[i + 1][(k * 10 + j) % 13] += dp[i][k];`

`dp[i][j] := 先頭 i 文字として考えられるもののうち，13 で割ったあまりが j であるものの数`
です。

上から見ます。(3桁の数字の場合、100の位を1桁目、1の位を3桁目としています。)
`i`桁までのmod13が`k`となる個数が分かっているとして、次の桁に`j`が来た場合の式です。
`i`桁までのmod13が`k`なので、次の桁を見ると`k * 10 + j`という2桁の数字ができますね。
これを13で割った余りが`dp[i + 1][(k * 10 + j) % 13]`に入ります。

例えば、`172`という数字について、1桁目までのmodは`1 % 13 = 1`ですね。
(`dp[1][1] = 1`になります。)
2桁目までのmod13は`17 % 13 = 4`ですね。
(`dp[2][4] = 1`になります。)
3桁目は`172 % 13`としてもいいのですが、この`4`を覚えておきます。
(最終的には10万桁にもなって計算しきれないからです。)
次の桁は`2`なので、調べるのは`4 * 10 + 2 = 42`という数字です。42のmod13は`42 % 13 = 3`となります。
(`dp[3][3] = 1`になります。)
これは`172 % 13 = 3`なので一致します。modというか割り算の性質からこれが言えます。
以上より、172を13で割って3になるものの個数が`dp[3][3]`にはいります。


例が長くなりましたが、これを一般化したものが上の式となります。
`?`にも対応したものが上のプログラムとなります。


※これは解説PDFのやり方です。
`dp[100005][13]`としていますが、`dp[13]`として解く方法もあります。その解法は解説動画にあります。


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