考察と呼べるほどのものでもないので自分用の考察過程と題しました。 一応ニッチな需要があると信じています、ありませんね。
まず適当に考えてみる。 ある猫が帽子の種類がa[i]だった場合、全体の帽子の種類としてありえるのは a[i]通りかa[i]+1通りのみ。なのでa[i]の種類は2種類まで。 さらに、二種類の場合は2つの差の絶対値が2以上だと不可。
まずは一種類しか無くてYesになる場合を考える。 この一種類をkind種類とする。 まず雑に、全て色がバラバラを考えるとkind=n-1の時は無条件にYesである。 それ以外には、kind*2<=nの場合である。 これは、以下のような実験をしてみた。
n=k*2として、0<=i<kの数字を2つずつ配置してみる。 このとき、猫は全員k-1と言う。 k-2と猫に言わせたければ、k-1を、k-1未満の数字で書き換えればいい。 このように帰納的に作ることが出来る。 逆に、k以上の数字を作ろうとすると、どれかの数字を書き換えなければいけなくなり、全員同じ数字は猫は言えない。 k+1からn-2の間は成り立たないことは実験出来ていないが、おそらく出来ないということで飛ばしてしまった。 nを偶数にしてしまったが、奇数でも特にこの法則は変わらない。
というわけで、1種類しか無かった場合はkind==n-1 || kind*2<=n という条件でYesとなる。
二種類の時を考える。ここも色々実験をした。 二種類のa[i]があるが、最初の条件からkind=max(a[i])となる。 小さい方のa[i]の個数をx,大きい方のa[i]の個数をyとする。 まず簡単に小さい方のa[i]の猫にx種類の帽子をx匹にバラバラに渡す。 大きい方のa[i]の猫には、それ以外の帽子1種類をy匹に渡す。 この時、小さい方の猫はx種、大きい方はx+1種類と発言する。 ここで、大きい方の猫の色を色々いじってみると、大きい方の猫と同じ色の猫が自分含め2匹以上いる必要があるとわかる。 逆に、小さい方の猫と同じ色の猫が一匹以上いると矛盾することも分かる。 小さい猫の方の条件から、x<kindである必要がある。 さらに、小さい方の猫でx種類出来ており残りは(kind-x)種類、この種類を大きい方の猫で作り出す必要があり、 一つの種類に二匹以上の猫が必要なので2*(kind-x)<=yである必要もある。
よって、これらをプログラムに落とし込むことでACとなる。 ほぼ、証明:ACですね。
