ABC098 B-Cut and Count で全探索を堪能してみた

# はじめに
個人的に面白い問題だったので、
いくつかアプローチを試してみました。

# [**問題**](https://atcoder.jp/contests/abc098/tasks/abc098_b) 
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/cd3a5882-5a6a-a976-739f-2a60ddf1ccfa.png)
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/4da88480-032d-b799-db7d-e9d9eac7c006.png)

# アプローチ 1: for + set
step 1:文字を分割する境界線を for 文で動かしていきます。
step 2:区切った文字列を set に放り込み、重複なしの文字列に分解します。
step 3:両者で同じ文字がないか for 文で確認します。
step 4:境界線の位置別にカウントの最大値を更新

```abc098b.cpp
#include <iostream>
#include <set>
using namespace std;

int main() {

	int N; string S; cin >> N >> S;
	set<char> A;//分割した文字列を格納する箱
	set<char> B;//分割した文字列を格納する箱
	int ans = 0;
    
	for (int i = 0; i < N-1; i++) {  //step 1 :文字を分割する境界を i で回す

		for (int n = 0; n <= i; n++) //step 2:区切った文字列を set にブチ込み
			A.insert(S[n]);
		for (int m = i+1; m < N; m++)//step 2:区切った文字列を set にブチ込み
			B.insert(S[m]);

		int cnt = 0; 
		for (auto x : A) {           //step 3:両者で同じ文字数をカウント
			bool flag = false;
			for (auto y : B) {
				if (y == x) {
					flag = true;
					break;
				}
			}
			if (flag)
				cnt++;
		}
		ans = max(ans, cnt);        //step 4:境界線の位置別にカウントの最大値を更新
		A = {}; B = {};//各箱を都度空にする
	}
	cout << ans;
	return 0;

}
//AC 36ms;
```

## step 3 の簡略化を目指す 
[_contain_](https://cpprefjp.github.io/reference/set/set/contains.html) :対応バージョン C++20~
有識者の解説に感謝です。
但し、2020/8/26 現在 c++20 は atcoder では未対応。
残念。

https://qiita.com/Chippppp/items/620d2e5229f5c7e93f0c

[_find_](https://cpprefjp.github.io/reference/set/set/find.html):C++17 対応
探索した結果、そのポインタが返るらしい。
但し、以下によると該当値が無い場合は end() を返すとある、少し使いにくい。。

http://vivi.dyndns.org/tech/cpp/set.html

# アプローチ 2: for only
調査不足も否定できないですが、set は悪手かもしれません。
有識者の回答を眺めていたら秀逸なアイディアを発見しました。

step 1:文字を分割する境界線を for 文で動かしていきます
step 2:'a' ~ 'z' の何れが文字列に適合するか for で check
step 3:両方の文字列に含まれていればカウント
step 4:境界線の位置別にカウントの最大値を更新

```abc098.cpp
#include <iostream>
#include <set>
using namespace std;

int main() {

	int N; string S; cin >> N >> S;
	int ans = 0;

	for (int i = 0; i < N; i++) {        //step 1 :文字を分割する境界を i で回す

		int cnt = 0;
		for (char c='a'; c <= 'z'; c++) {//step 2:'a' ~ 'z' の何れが適合するか確認

			bool left = false, right = false;
			for (int n = 0; n <= i; n++) {
				if (S[n] == c)
					left = true;
			}

			for (int m = i+1; m < N; m++) {
				if (S[m] == c)
					right = true;
			}
            //step 3:両方の文字列に含まれていればカウント
			cnt += (left == true && right == true);

		}
		ans = max(ans, cnt);//step 4:境界線の位置別にカウントの最大値を更新
	
	}

	cout << ans;
	return 0;

}
//AC 7ms;
```

素晴らしい!! good idea の出会いに感謝。

# アプローチ3 :for only ver2
アプローチ2 と step の踏み方は同じだが
書き方が変わり、for 文を削減している。

```abc098.c
#include <iostream>
#include <string>
#include <set>
using namespace std;

int main() {

	int N; string S; cin >> N >> S;
	int ans = 0;

	for (int i = 0; i < N-1; i++) {
		string A = S.substr(0, i + 1);
		string B = S.substr(i + 1, N - i - 1);

		int cnt = 0;
		for (char c = 'a'; c <= 'z'; c++) {
			if (A.find(c) != string::npos && B.find(c) != string::npos)
				cnt++;
		}
		ans = max(ans, cnt);

	}

	cout << ans;
	return 0;

}

//AC 5ms;
```

時短の為に for を減らしている。

また _find_ の使い方が素晴らしい。
これは検索したい element が含まれていない場合 error となる。
しかし _string::npos_ (該当なしの意図)を
使うことで上手く error を回避している、素晴らしい!