はじめに
コチラの書籍により
色々と解けるようになりました、筆者、および関係者に感謝です。
自力で解けるたびに喜び、
雄叫びを上げて、ツイートしています。
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.
#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 という宝箱に辿り着くと歓喜できる。
まだまだ浅瀬で苦しんでいるが
もっと潜れるようになりたい今日この頃。