mayoko’s diary

プロコンとかいろいろ。

AGC016 B: Colorful Hats

面白かったので考察をメモしておこうかなと思いました。
B - Colorful Hats

考察

こういう問題は必要十分条件を考えるのが定石だろうと思います。
とりあえず考察として, 「数字は x か x+1 に絞られる」というのはちょっと考えてわかりましたが, それ以外は特に検討がつかないのでとりあえず実験してみます。

N <= 5 程度で可能なリスト, 不可能なリストを適当にピックアップしました。
実験してる間に気づいた一般的なことは, 「長さ N に対して, 全員が x 種類と主張する場合には, x <= N/2 または x = N-1 の時は必ず OK」だけでした。

「単純な例から初めて決まった動きをさせると解が構成できる」みたいな方法もできるかなと思いました。
今回の場合は, それぞれの人の帽子の色を始めに固定しておいて, そこから一人ずつ帽子の色を変えていく, みたいな方針です。
一番基本的な形とその時に感じた, 「それぞれの人の帽子がバラバラ」というのから初めて色を変えていきます。
以下は左が帽子の色で, 右がその時のそれぞれの人々の主張です。

  • ABCDE: 44444
  • BCDAA: 33344
  • BCAAA: 22333
  • BAAAA: 12222
  • BCBAA: 32333
  • ...

この実験をやって突然「帽子がユニークな人は x と主張してユニークでない人は x+1 と主張する」ことに気づきました。
全体で x 種類の帽子があり, かつ帽子がユニークな人が y 種類いる場合, (y <= x)

  • (1, 2, 3, ..., y), (y+1, y+2, ..., x), (y+1, y+2, ..., x), (...)

というように帽子がかぶられればよく, このような解が生成できる必要十分条件は, y + (x-y) * 2 <= N です。

とりあえずこれで実装して実は全てが x の場合でもうまくいかないかなーと思いましたが, そううまくは行かなかったので, 場合分けしてホイっと解きました。

感想

考察書いてみれば思考過程振り返れるかなーと思ったけど結局一番大事な考察に突然気づいてやがるのでなんかなぁ。
「どうやって思いつくか」が大事だと思うけど実験してたら突然思いついた感がある