d_tutuz https://blog.hatena.ne.jp/d_tutuz/ 数学/競プロメモ https://tutuz.hateblo.jp/ 問題 https://beta.atcoder.jp/contests/agc016/tasks/agc016_b N 匹の猫がいる。猫 i は「自分の除く猫がかぶっている帽子の色の種類数は a_i である」といっている。すべての猫の発言に矛盾しないように帽子を割り当てることができるか判定せよ。 考え方 実験することが大事っぽい。 すべての帽子の色の数を A とする。このとき、ある猫 i が唯一の色の帽子をかぶっていた場合は a_i = A - 1 となり、それ以外の猫は a_j = A となる。まず、数列の最小値と最大値の差は 1 以内におさまる。そうでない場合は割り当てることはできない。 … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftutuz.hateblo.jp%2Fentry%2F2018%2F10%2F08%2F114231" title="AGC105-B：Colorful Hats - 数学/競プロメモ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2018-10-08 11:42:31 rich https://tutuz.hateblo.jp/entry/2018/10/08/114231 1.0 100%