競技プログラミング練習記 No.4【ABC152練習】

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

[ABC152](https://atcoder.jp/contests/abc152)を解きました。
4完です。
D問題を解いたところで時間がきました。

|問題|時間|アルゴリズム|
|:-:|:-:|:-:|
| A |  1min |-|
| B |  1min |-|
| C | 15min |-|
| D | 80min |組み合わせ|



## A
```c++
	int n, m;
	cin >> n >> m;

	cout << (n == m ? "Yes" : "No");

```
そのまんま

## B
``` c++
	int a, b;
	cin >> a >> b;

	if (a > b)
	{
		swap(a, b);
	}

	for(int i = 0; i < b; ++i)
	{
		cout << a;
	}

```
今回は入力が整数のみなので、辞書順で小さい = 数値が小さいということです。
`a < b` の状態にしてから、`a`を`b`回出力しました。

入力に文字列があったら`vector<string>`とか使ってたと思います。

## C
``` c++
	int n, p, min_p = 1e9, ans = 0;
	cin >> n;

	for(int i = 0; i < n; ++i)
	{
		cin >> p;
		if (p < min_p)
		{
			++ans;
			min_p = p;
		}
	}
	cout << ans;

```
最長部分数列か！？と思ったら違いました。
聞かれていることの理解に時間がかかってしまった。

## D
``` c++
	int low_digit = 0;
	int high_digit = 0;
	int log10 = 1;
	int mod = 10;

	int perm[6] = { 0, 2, 22, 222, 2222, 22222 };
	int ans[200003] = { 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, };

	for(int i = 10; i <= 200000; ++i)
	{
		if      (i >= 100000) { log10 = 5; mod = 100000; }
		else if (i >= 10000)  { log10 = 4; mod = 10000; }
		else if (i >= 1000)   { log10 = 3; mod = 1000; }
		else if (i >= 100)    { log10 = 2; mod = 100; }
		else                  { log10 = 1; mod = 10; }
		
		low_digit = i % 10;
		high_digit = i / mod;

		if (low_digit == 0)
		{
			ans[i] = 0;
			continue;
		}
		if (high_digit > low_digit)
		{
			ans[i] = perm[log10];
		}
		else if (high_digit < low_digit)
		{
			ans[i] = perm[log10 - 1];
		}
		else // low_digit == high_digit
		{
			ans[i] = perm[log10 - 1] + ( (i / 10) % (mod / 10) ) * 2 + 3;
		}
	}

	int n;
	cin >> n;

	for(int i = 0; i < n; ++i)
	{
		ans[i + 1] = ans[i] + ans[i + 1];
	}

	cout << ans[n];
```

最大桁と最小桁の数字を比べて、その結果で分岐しています。
`ans[i]` には、条件を満たす組`(A, B)`のうち、`max(A, B)`が`i`となる組み合わせの数が入っています。
最後は必要分までの累積和をとって出力です。

ちなみにこちらはリファクタ後のコードです。

リファクタで実行時間が2msから3msになったのですが、気にならないレベルでしょう。
コンテスト時に通したものに比べて大幅にまとめられました。
コンテスト時にもこんなコードを書きたい。

解説の解き方でも解きました。シンプルな組み合わせじゃん。次は気付きたい。↓

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

	int c[9][9];

	for(int i = 0; i < 9; ++i)
	for(int j = 0; j < 9; ++j)
	c[i][j] = 0;

	for(int i = 1; i <= n; ++i)
	{
		if (i % 10 == 0)
		{
			continue;
		}
		string s = to_string(i);
		c[s.front() - '0' - 1][s.back() - '0' - 1]++;
	}

	int ans = 0;
	for(int i = 0; i < 9; ++i)
	for(int j = 0; j < 9; ++j)
	ans += c[i][j] * c[j][i];

	cout << ans;
```

コンテスト時に通したのはこちら↓
桁数ごとに`for`で回しています。
バグりやすいけれど考えやすい書き方です。
バグらないように注意しながら書きました。

``` c++
	int low_digit = 0;
	int high_digit = 0;
	int ans[200003] = { 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, };

	for(int i = 10; i <= 99; ++i)
	{
		low_digit = i % 10;
		high_digit = i / 10;
		if (low_digit == 0)
		{
			ans[i] = 0;
		}
		else if (high_digit > low_digit)
		{
			ans[i] = 2;
		}
		else if (high_digit < low_digit)
		{
			ans[i] = 0;
		}
		else // low_digit == high_digit
		{
			ans[i] = 3;
		}
	}
	for(int i = 100; i <= 999; ++i)
	{
		low_digit = i % 10;
		high_digit = i / 100;
		if (low_digit == 0)
		{
			ans[i] = 0;
		}
		else if (high_digit > low_digit)
		{
			ans[i] = 22;
		}
		else if (high_digit < low_digit)
		{
			ans[i] = 2;
		}
		else // low_digit == high_digit
		{
			ans[i] = 5 + ((i / 10) % 10) * 2;
		}
	}
	for(int i = 1000; i <= 9999; ++i)
	{
		low_digit = i % 10;
		high_digit = i / 1000;
		if (low_digit == 0)
		{
			ans[i] = 0;
		}
		else if (high_digit > low_digit)
		{
			ans[i] = 222;
		}
		else if (high_digit < low_digit)
		{
			ans[i] = 22;
		}
		else // low_digit == high_digit
		{
			ans[i] = 25 + ((i / 10) % 100) * 2;
		}	
	}
	for(int i = 10000; i <= 99999; ++i)
	{
		low_digit = i % 10;
		high_digit = i / 10000;
		if (low_digit == 0)
		{
			ans[i] = 0;
		}
		else if (high_digit > low_digit)
		{
			ans[i] = 2222;
		}
		else if (high_digit < low_digit)
		{
			ans[i] = 222;
		}
		else // low_digit == high_digit
		{
			ans[i] = 225 + ((i / 10) % 1000) * 2;
		}	
	}
		for(int i = 100000; i <= 200000; ++i)
	{
		low_digit = i % 10;
		high_digit = i / 100000;
		if (low_digit == 0)
		{
			ans[i] = 0;
		}
		else if (high_digit > low_digit)
		{
			cout << "naihazu " << i << endl;
		}
		else if (high_digit < low_digit)
		{
			ans[i] = 2222;
		}
		else // low_digit == high_digit
		{
			ans[i] = 2225 + ((i / 10) % 10000) * 2;
		}	
	}

	int n;
	cin >> n;

	for(int i = 0; i < n; ++i)
	{
		ans[i + 1] = ans[i] + ans[i + 1];
		// cout << i + 1 << " " << ans[i + 1] << endl;
	}

	cout << ans[n];



```