競技プログラミング練習記 No.29【ABC131練習】

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

[ABC131](https://atcoder.jp/contests/abc131)を解きました。
4完です！
Eは解説を見て解きました。

|問題|時間|アルゴリズム|実行時間
|:-:|:-:|:-:|:-:|
| A |  2min |-| 6ms|
| B |  8min |数列の和| 6ms|
| C | 25min |包除原理|11ms|
| D |  7min |-|55ms|
| E | - |二部グラフ|8ms|



## A - Security
```c++
	string s;
	cin >> s;
	if (s[0] == s[1] || s[1] == s[2] || s[2] == s[3])
	{
		cout << "Bad";
	}
	else
	{
		cout << "Good";
	}
```
4桁の数字にゾロ目があるかを判定する問題です。
1文字目と2文字目が同じ
2文字目と3文字目が同じ
3文字目と4文字目が同じ
このどれかが成り立つとき、ゾロ目だといえますね。
各桁を抜き出しやすいので、`string`型で受け取るといいと思います。

## B - Bite Eating
``` c++
	int n, l;
	cin >> n >> l;
	int sum = n * (l - 1) + n * (n + 1) / 2;
	if (0 < l) sum -= l;
	if (l + n - 1 < 0) sum -= l + n - 1;
	cout << sum;
```
まず総和を出して、そのあと、数列の中で0に一番近い数字を引いています。
数列の中に0があるときは0を引いて総和が変わらないので、何もしていません。

## C - Anti-Division
``` c++
// 最大公約数 : 3,4 ->  1
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

// 最小公倍数 : 3,4 -> 12
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }

// a 以上 b 以下の数のうち c で割り切れるものの個数
ll ranged_div_num(ll a, ll b, ll c)
{
	return (b / c - (a-1) / c);
}

void solve()
{
	ll a, b, c, d;
	cin >> a >> b >> c >> d;

	ll all = b - a + 1;
	cout << all - ( ranged_div_num(a, b, c) + ranged_div_num(a, b, d) - ranged_div_num( a, b, lcm(c, d) ) );
}
```
包除原理というやつですね。この前あったABC172-Eで出ました。
使うのは初めてですが、E問題に比べて優しいC問題で実践できたのでうれしいです。
難しそうな名前を見ると難しく感じますが、内容は単純です。

問題文より
> A 以上 B 以下の整数のうち、C でも D でも割り切れないものの個数を求めてください。

とあるのですが、少し考えにくいですね。（愚直にやるとできるのですが、制約があるので解けません。）
そういう時は余事象を考えてみましょう。
つまり、`A以上B以下の整数のうち、CまたはDで割り切れるものの個数`を考えます。

この個数は
`Cで割り切れるものの個数` + `Dで割り切れるものの個数`
でわかりますね。
ですが、これだけだと`CとDで割り切れるものの個数`が2回カウントされてしまいます。
そのため、`CとDで割り切れるものの個数`を1回引きます。

つまり、
`Cで割り切れるものの個数` + `Dで割り切れるものの個数` - `CとDで割り切れるものの個数`
が求めたい個数です。

それぞれ
`Cで割り切れるものの個数` : `ranged_div_num(a, b, c)`
`Dで割り切れるものの個数` : `ranged_div_num(a, b, d)`
`CとDで割り切れるものの個数` : `ranged_div_num(a, b, lcm(c, d))`
ですね。

あとは、`A以上B以下の整数`の個数から求めた個数を引けば答えです。

## D - Megalomania


``` c++
using P = pair<ll, ll>;
{
	ll n, a, b;
	cin >> n;
	vector<P> task(n);
	for(int i = 0; i < n; ++i)
	{
		cin >> a >> b;
		task[i] = P(b, a);
	}
	sort(task.begin(), task.end());

	ll sum_a = 0, now_b = 0;
	for(int i = 0; i < n; ++i)
	{
		now_b = task[i].first;
		sum_a += task[i].second;
		if (now_b < sum_a)
		{
			cout << "No";
			return;
		}
	}
	cout << "Yes";
}
```
締め切りが近いものから仕事をこなして、今の時間が締め切りを超えなければ大丈夫ですね。
「かかる時間」と「締め切り」をセットにしながら「締め切り」の順にソートしたいので、`pair`型を使っています。
ソートした後は、かかった時間の総和を計算しながら、締め切りを超えているかチェックすれば答えがわかります。


## E - Friendships

```c++
	int n, k;
	cin >> n >> k;

	// 二部グラフの考えを使うけど二部グラフじゃない！
	if ( (n - 1) * (n - 2) / 2 >= k )
	{
		int m = (n - 1) * (n - 2) / 2;
		cout << n-1 + m-k << endl;
		for(int i = 2; i <= n; ++i)
		{
			cout << 1 << " " << i << endl;
		}

		for(int i = 2; i <= n - 1; ++i)
		{
			for(int j = i + 1; j <= n; ++j)
			{
				m--;
				if (m >= k) cout << i << " " << j << endl;
				else break;
			}
		}
		return;
	}
	cout << -1;
```
二部グラフまではわかっていて、`(n - 1) * (n - 2) / 2 == k`となる場合の答えは出せていました。。。
惜しかった。

この問題は二部グラフの特殊な状態である[グラフ理論のスター](https://ja.wikipedia.org/wiki/%E3%82%B9%E3%82%BF%E3%83%BC_(%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96))について知っていれば解けたと思います。勉強します。

頂点数を固定したとき、「最短距離が2である頂点対」が最も多いグラフはスターになります。

`N`個の頂点を `1`個と`N-1`個の2つの頂点集合に分けます。
「`1`個の頂点集合」から「`N-1`個の頂点集合」へ辺をつなげればスターとなります。
その場合、「`N-1`個の頂点集合」同士の最短距離が2になります。
そのような頂点対は`N-1`個の頂点から`2`個の頂点を選ぶ組み合わせになるので、`(n-1) C 2 = (n-1)*(n-2)/2`個ですね。

また、「`N-1`個の頂点集合」同士で辺を1つつなぐごとに「最短距離が2である頂点対」は1つ減ります。
そのため、`0`以上`(n-1) C 2`の頂点対を実現可能となります。

ここまでわかれば問題文通りに実装です。
辺の数と境界値に注意してください。

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