の種類数が2個以下でないとNoというのは自明なので
- 条件が多く大変だがサンプルが豊富なので、ある程度サンプルから条件を整理できる
https://atcoder.jp/contests/agc016/submissions/24577904
自分と同じ色が存在しない猫を「uniqueな猫」とするとuniqueでない猫はuniqueな猫より大きい を答えるはずである。つまり uniqueな猫iを
とすると uniqueでない猫jは
と分かる。
の種類数は最大でも 2 なので 種類数 1, 2 で場合分けして考える。
の種類数 1 のとき
- if (Linear(0, count).first <= N / 2) aout("Yes");
uniqueな猫が存在すると の種類数が 2 になりがちなので全てuniqueでない猫とする
サンプル５のようにuniqueでない猫が2匹ずついると の種類数が最大で N/2
- if (Linear(0, count).first == N - 1) aout("Yes");
ただし、サンプル４のように全ての猫がuniqueなコーナーケースがあり、その場合は の種類数は N-1
- 上記以外は No
サンプル６のような入力は矛盾
の種類数 2 のとき
- if (Linear(1, count).second <= 1) aout("No");
大きい方の はuniqueでない猫のはずなので、任意の（大きい方の）
は2回以上出現しなければならない
したがってサンプル２のような入力は矛盾
- if (Linear(0, count).first + 1 != Linear(1, count).first) aout("No");
uniqueな猫iを とすると uniqueでない猫jは
矛盾するサンプルが存在しないので自力で気づく必要がある
- if (Linear(1, count).first > Linear(1, count).second / 2 + Linear(0, count).second || Linear(1, count).first <= Linear(0, count).second) aout("No");
uniqueでない猫が答える について「uniqueでない猫の数 / 2 + uniqueな猫の種類数」以下である必要がある
uniqueな猫が答える について「uniqueでない猫が答える
つまり全種類数」未満である必要がある
したがってサンプル３のような入力は矛盾
なお、テストケースが弱く if (Linear(1, count).first != Linear(1, count).second / 2 + Linear(0, count).second) aout("No"); のような嘘でも通る
- 上記以外は Yes
感想：珍しく自力ACできた…と思っていたがテストケースが弱くて嘘解法を通していたことに気づいた…（＾＾；
