7K12 blog

猫でも分かるアルゴリズム解説

AGC016 B - Colorful Hats

f:id:tkr987:20210727163252p:plain

  •  a_i の種類数が2個以下でないとNoというのは自明なので  a_i の種類数を基準に場合分け
  • 条件が多く大変だがサンプルが豊富なので、ある程度サンプルから条件を整理できる

f:id:tkr987:20210727170448p:plain
https://atcoder.jp/contests/agc016/submissions/24577904

自分と同じ色が存在しない猫を「uniqueな猫」とするとuniqueでない猫はuniqueな猫より大きい  a_i を答えるはずである。つまり uniqueな猫iを  a_i とすると uniqueでない猫jは  a_j = a_i+1 と分かる。  a_i の種類数は最大でも 2 なので 種類数 1, 2 で場合分けして考える。

 a_i の種類数 1 のとき

  • if (Linear(0, count).first <= N / 2) aout("Yes");

uniqueな猫が存在すると  a_i の種類数が 2 になりがちなので全てuniqueでない猫とする
サンプル5のようにuniqueでない猫が2匹ずついると  a_i の種類数が最大で N/2

  • if (Linear(0, count).first == N - 1) aout("Yes");

ただし、サンプル4のように全ての猫がuniqueなコーナーケースがあり、その場合は  a_i の種類数は N-1

  • 上記以外は No

サンプル6のような入力は矛盾

 a_i の種類数 2 のとき

  • if (Linear(1, count).second <= 1) aout("No");

大きい方の  a_i はuniqueでない猫のはずなので、任意の(大きい方の)  a_i は2回以上出現しなければならない
したがってサンプル2のような入力は矛盾

  • if (Linear(0, count).first + 1 != Linear(1, count).first) aout("No");

uniqueな猫iを  a_i とすると uniqueでない猫jは  a_j = a_i+1
矛盾するサンプルが存在しないので自力で気づく必要がある

  • 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でない猫が答える  a_i について「uniqueでない猫の数 / 2 + uniqueな猫の種類数」以下である必要がある
uniqueな猫が答える  a_i について「uniqueでない猫が答える  a_i つまり全種類数」未満である必要がある
したがってサンプル3のような入力は矛盾
なお、テストケースが弱く if (Linear(1, count).first != Linear(1, count).second / 2 + Linear(0, count).second) aout("No"); のような嘘でも通る

  • 上記以外は Yes

感想:珍しく自力ACできた…と思っていたがテストケースが弱くて嘘解法を通していたことに気づいた…(^^;