ABC053 D-Card Eater で脳汁の枯渇体験

# はじめに
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/16caf4a5-8aaf-1e12-9295-8e9ca62fcd97.png)
[**コチラ**](https://www.amazon.co.jp/%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E7%9A%84%E6%80%9D%E8%80%83%E5%8A%9B%E3%81%8C%E8%BA%AB%E3%81%AB%E3%81%A4%E3%81%8F-%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%82%B3%E3%83%B3%E3%83%86%E3%82%B9%E3%83%88AtCoder%E5%85%A5%E9%96%80-%E5%A4%A7%E6%A7%BB-%E5%85%BC%E8%B3%87/dp/404604408X/ref=sr_1_1_sspa?__mk_ja_JP=%E3%82%AB%E3%82%BF%E3%82%AB%E3%83%8A&crid=24X3A4JMXF6VG&keywords=%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%82%B3%E3%83%B3%E3%83%86%E3%82%B9%E3%83%88&qid=1663822099&sprefix=%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%82%B3%E3%83%B3%E3%83%86%E3%82%B9%E3%83%88%2Caps%2C227&sr=8-1-spons&psc=1&spLa=ZW5jcnlwdGVkUXVhbGlmaWVyPUFGQkRUSVZZS0hERSZlbmNyeXB0ZWRJZD1BMDQxMjQ1OEFDTlk5VTIzS0NSUyZlbmNyeXB0ZWRBZElkPUExTE01SlYyUFNVR1pPJndpZGdldE5hbWU9c3BfYXRmJmFjdGlvbj1jbGlja1JlZGlyZWN0JmRvTm90TG9nQ2xpY2s9dHJ1ZQ==)の書籍により
色々と解けるようになりました、筆者、および関係者に感謝です。

自力で解けるたびに喜び、
雄叫びを上げて、ツイートしています。
https://twitter.com/idawFsB1WU6wVUe

今回は D-Card Eater を解説の HELP のもと攻略。
自らの思考を振り返り、ゴールに至るまでの
道筋を自分に解説します。

# [問題](https://atcoder.jp/contests/abc053/tasks/arc068_b)
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/58a9367f-a519-9a0e-6bc3-a36e3bffd88c.png)
# 思考の整理
## Step 1:とりあえず手を動かす
&emsp;入力例2 を使って考察。本文には上から**任意に 3 枚取れる**とあるので
&emsp;実質、入力 A をソートして考えても差し支えない。
&emsp;下図のように、まずはやってみる。
&emsp;<font color="Red">**赤字**</font>にあるように 3 つ選び、min/max を食べていく。
![無題1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/7ab5096f-c539-a376-1e79-c590bf5c15e0.png)
&emsp;御覧のように重複する数字を優先的に食べることで残すカードが最大となる。
&emsp;上記の表の動きを見方を変えて再度整理する

![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/3a314a2a-7c89-f129-4741-6f8e8e2cf596.png)
&emsp;右図にあるように各要素の個数を眺めながら
&emsp;左図にある取得した組み合わせを頭で泳がせる。
&emsp;これにより、重複数が 3 以上の奇数の場合、左図 4th にあるように
&emsp;連続して同じ数を配置する事で、**重複した個数を自力で 1 に集約できる**事が分かった。
&emsp;~~地味に喜んだが、まだまだゴールへは道のりが長い~~

&emsp;残りの要素、重複要素が偶数の子たちの処遇に詰まった。
&emsp;上図 1st ~ 3rd にあるように重複要素たちの組み合わせを作ればよいのだろうが、
&emsp;問題では 3 枚必ず抜くように書かれているのでアプローチが思いつかず力尽きる。

## Step 2:[解説を見る](https://www.youtube.com/watch?v=Y9v0a4d0vzk&t=1575s)

&emsp;解説を見て気づいたのだが、
&emsp;**途方に暮れたときこそ、手を動かすべきのようだ。**

&emsp;step1 にあるように重複個数が **1個** もしくは、**3個**以上の奇数は無視 
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/efffb125-5ce3-ac6c-47a6-62b3778e010b.png)
&emsp;偶数要素が偶数個あれば打ち消しあうようだ。
&emsp;念のため以下の 2 例も試したが、問題なさそう。
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/3f55f45b-385b-6906-818d-a42a4defff23.png)

逆に偶数要素が奇数個の場合、要素 3 を消して試してみた。
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/b63dff75-4ce8-fabb-eabd-7c239653f6a1.png)
右図にあるように**要素数が 1 個である要素を消費**してしまう事が分かった。
これは直感的にも分かる事だと思う。

# まとめ
以上から、重複個数が偶数である要素をカウントし、
これが**偶数個なら全種類、奇数個なら全種類-1** が答えであることが分かった。

下記コードで AC.

```abc053d.cpp
#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main() {
	int N,A; cin >> N;
	map<int, int>num;

	for (int i = 0; i < N; i++) {
		cin >> A;
		num[A]++;
	}

	int cnt = 0;
	for (auto x : num) {
		if (x.second % 2 == 0)
			cnt++;
	}

	if (cnt % 2 == 0)
		cout << num.size();
	else
		cout << num.size() - 1;

	//while (1) {}
	return 0;

}
```

思考の海は広く、一旦潜ると周りは見えなくなる。

更に潜るべきか
浮上して別のポイントに移動して潜るべきか
孤独な戦いだ

だからこそ、自力で AC という宝箱に辿り着くと歓喜できる。
まだまだ浅瀬で苦しんでいるが
もっと潜れるようになりたい今日この頃。