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

はじめに

コチラの書籍により
色々と解けるようになりました、筆者、および関係者に感謝です。

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

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

問題

思考の整理

Step 1:とりあえず手を動かす

 入力例2 を使って考察。本文には上から任意に 3 枚取れるとあるので
 実質、入力 A をソートして考えても差し支えない。
 下図のように、まずはやってみる。
 赤字にあるように 3 つ選び、min/max を食べていく。

 御覧のように重複する数字を優先的に食べることで残すカードが最大となる。
 上記の表の動きを見方を変えて再度整理する

 右図にあるように各要素の個数を眺めながら
 左図にある取得した組み合わせを頭で泳がせる。
 これにより、重複数が 3 以上の奇数の場合、左図 4th にあるように
 連続して同じ数を配置する事で、重複した個数を自力で 1 に集約できる事が分かった。
 地味に喜んだが、まだまだゴールへは道のりが長い

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

Step 2:解説を見る

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

 step1 にあるように重複個数が 1個 もしくは、3個以上の奇数は無視

 偶数要素が偶数個あれば打ち消しあうようだ。
 念のため以下の 2 例も試したが、問題なさそう。

逆に偶数要素が奇数個の場合、要素 3 を消して試してみた。

右図にあるように要素数が 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 という宝箱に辿り着くと歓喜できる。
まだまだ浅瀬で苦しんでいるが
もっと潜れるようになりたい今日この頃。