AtCoder Grand Contest 016 B: Colorful Hats
N匹の猫が色付き防止をかぶっている。それぞれの猫は自分以外の猫の帽子の色がa[i]種類あるといっている。このような組み合わせは存在するか？
ある猫に注目したときにその猫をカウントする・しないで最大1種類しか違わない。よってa[i]はすべてある数xがあって、xまたはx + 1のみである。この条件に当てはまらないものはまず除外する。
次に、x+1が存在しない、つまりすべてのa[i]が同一の数の時を考える。これは全体でN色あって、a[i] = N - 1のとき、またはa[i] * 2 <= Nで、各色の帽子が2匹以上の猫によってかぶられているときである。
次にx+1が存在する場合を考える。この時、2匹以上の猫によってかぶられている帽子の色については、その猫が他の猫のかぶってる帽子の色の数をカウントしても全体の数と変わらない。一方でそうでない猫は全体の数 - 1個の色の種類しか見えない。
Type1. x+1: 2匹以上の猫が同じ帽子をかぶっている…p匹
Type2. x: それぞれが違う色の帽子をかぶっている...q匹
となる。ここでそれぞれp匹、q匹とする。 この条件を考えると、Type1の猫はType2の猫が全部みえており、Type2の猫は全部違う種類なので、Type1の猫がType1の他の猫のかぶっている帽子の種類として、x+1-q種類の色が見える。この色がそれぞれ2匹以上かぶっているので、(x+1-q) * 2 <= p を満たす。
また、Type2についてはq匹がそれぞれ違う色なので、x >= q を満たす 。この条件をともに満たすときにYesである。
