競技プログラミング練習記 No.27【ABC133練習】

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

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

|問題|時間|アルゴリズム|実行時間
|:-:|:-:|:-:|:-:|
| A |  1min |-| 8ms|
| B | 10min |-| 9ms|
| C | 27min |mod|14ms|
| D | 60min |しゃくとり法|28ms|



## A - T or T
```c++
	int n, a, b;
	cin >> n >> a >> b;
	int ans = min(n * a, b);
	cout << ans;
```
`N`人いて、「ひとりあたり`A`円」と「`N`人で`B`円」のどちらが安いか求める問題ですね。
どちらも計算して、`min`関数で小さいほうを求めます。

## B - Good Distance
``` c++
	int n, d;
	cin >> n >> d;
	vector< vector<int> > x(n, vector<int>(d));

	for(int i = 0; i < n; ++i)
	{
		for(int j = 0; j < d; ++j)
		{
			cin >> x[i][j];
		}
	}

	int ans = 0;
	for(int i = 0; i < n - 1; ++i)
	{
		for(int j = i + 1; j < n; ++j)
		{
			int sq_sum = 0;
			for(int k = 0; k < d; ++k)
			{
				int dif = x[i][k] - x[j][k];
				sq_sum += dif * dif;
			}
			if (fmod(abs(sqrt(sq_sum)), 1.0) <= 0.001)
			{
				ans++;
			}
		}
	}
	cout << ans;
```
`O(N^2 * D)`です。
計算量が多いですが、この制約なら全通り試しても大丈夫です。
`X_i`と`X_j`の組み合わせを全列挙して、問題文にある式に沿って距離を求めています。

さて、距離が整数になるかの判定は2通りあります。
精度が高い方法と精度が低い方法です。

精度が低い方法は、実際に距離を計算して、「1.0で割った余りが0」かどうかを調べる方法です。
PCで扱う実数は浮動小数点なのですが、その性質上、「ちょうど0」という判定はできません。
そのため、「1.0で割った余りが0.001以下」のように不等号で判定します。
私はこちらでやりました。一行でかけるので手間を省くためです。
以下の部分です。
`if (fmod(abs(sqrt(sq_sum)), 1.0) <= 0.001)`

精度が高い方法は、距離の2乗が整数の2乗かを調べる方法です。
この方法は実数が出てこない（整数のみで判定できる）ので判定の間違いがありません。



## C - Remainder Minimization 2019
``` c++
	ll l, r;
	cin >> l >> r;
	if (r - l >= 2019)
	{
		cout << 0;
		return;
	}
	l %= 2019LL;
	r %= 2019LL;
	if (l >= r) r += 2019LL;

	int ans = (l * r) % 2019;
	for(int i = l; i <= r - 1; ++i)
	{
		for(int j = i + 1; j <= r; ++j)
		{
			ans = min(ans, (i * j) % 2019);
		}
	}
	cout << ans;
```
WA量産してしまいました。悔しいぃ。
`O((R-L)^2)`で、`L,R = [0, 2*10^9]`なので、普通にやるとTLEですね。

これは合同式modの性質を使った問題です。
`(i * j) mod 2019`
は
`(i mod 2019) * (j mod 2019) mod 2019`
と一致します。
つまり、`i`と`j`をかける前にmodの計算をすることができます。
こうすると、`i,j`の範囲を`[0,2*10^9]`から`[0,2018]`に縮められます。
ここまでわかれば、`L`と`R`の大小に注意しながら全探索をして答えです。

`if (r - l >= 2019)`について
これが成り立つ場合は`[l,r]`に2019の倍数があります。つまり答えが0になります。
これを書いていなくてWAしました。。。

## D - Rain Flows into Dams

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

	ll diff_eve = 0;
	ll diff_odd = 0;
	for(int i = 0; i < n / 2; ++i)
	{
		diff_eve += a[(i * 2 + 1) % n];
		diff_odd += a[(i * 2 + 2) % n];
	}
	for(int i = 0; i < n / 2; ++i)
	{
		cout << sum - 2 * diff_eve << " " << sum - 2 * diff_odd << " ";
		diff_eve += a[(i * 2 + 1 + n / 2 * 2) % n] - a[(i * 2 + 1) % n];
		diff_odd += a[(i * 2 + 2 + n / 2 * 2) % n] - a[(i * 2 + 2) % n];
	}
	if (n & 1)
	{
		// 奇数の時、端数を表示
		cout << sum - 2 * diff_eve;
	}
```
もらった条件から式を作ります。
ダムを`d`、山を`y`として
入力で`d`を受け取り、`y`を求める問題なので、`d`で`y`を表す式を目指します。

`d[0] = (y[0] + y[1]) / 2`
のような式ができます。
これを一般化すると、
`d[i] = (y[i] + y[i+1]) / 2`・・・(1)
ですね。

また、`d[0] + d[1] + d[3] + ... = y[0] + y[1] + y[2] + ...` ・・・(2)
の式もみつかります。

(1)(2)式をくみあわせると、`y`を`d`で表す式が出せます。
`d[0] + d[1] + d[2] + ...`を`sum`として、
`y[0] = sum - 2 * (d[1] + d[3] + d[5] + ...)`
`y[1] = sum - 2 * (d[2] + d[4] + d[6] + ...)`
...
となります。

一般化して、
`y[i] = sum - 2 * (d[i+1] + d[i+3] + d[i+5] + ...)`
ですね。インデックスが`n`以上になった場合は`%n`を使うことに注意です。

これで答えが出せるのですが、そのままやると`O(N^2)`のため制約よりTLEとなってしまいます。
そのため、ここからさらに高速化を考えます。

`(d[i+1] + d[i+3] + d[i+5] + ...)`
は毎回計算しているのですが、共通部分が多いので高速化できそうですね。
実際にこの部分はしゃくとり法で高速化できます。

その実装が上のプログラムです。
インデックスが偶数と奇数の場合とで共通部分が違うので偶奇に分けました。
複雑になりました。バグりやすい書き方です。。。反省。


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