AGC105-B:Colorful Hats

問題

https://beta.atcoder.jp/contests/agc016/tasks/agc016_b

N 匹の猫がいる。猫 i は「自分の除く猫がかぶっている帽子の色の種類数は a_i である」といっている。すべての猫の発言に矛盾しないように帽子を割り当てることができるか判定せよ。

考え方

実験することが大事っぽい。

すべての帽子の色の数を A とする。このとき、ある猫 i が唯一の色の帽子をかぶっていた場合は a_i = A - 1 となり、それ以外の猫は a_j = A となる。まず、数列の最小値と最大値の差は 1 以内におさまる。そうでない場合は割り当てることはできない。

そこで、最大値と最小値の差で場合分けする。

(i) 最大値=最小値となっている場合

N = 4 として以下のように帽子をかぶっていたとする

帽子 R B G E
a_i 3 3 3 3

猫がかぶっている帽子の色がすべて異なる場合は、最大値=最小値となる。
この時、 a_i = A-1 である。

また、N = 7 として以下のように帽子をかぶっていたとする

帽子 R R R B B G G
a_i 3 3 3 3 3 3 3

上記のようにすべての色の帽子が 2 つ以上の猫がかぶっている場合は最大値=最小値となる。

この時、2 * a_i <= N である。

(ii) 最大値 - 最小値 = 1となっている場合

以下のように、数列の値として A と A-1 が存在する場合は同じ色の帽子を 2 つ以上かぶっている猫と、唯一の色の帽子をかぶっている猫がいる。

帽子 R R B B G E
a_i 4 4 4 4 3 3

唯一の色をかぶっている帽子の色の数 x は a_i = A-1 となっている値の数である。同じ色の帽子をかぶっている色の数は A - x である。よって

x + 2 * (A - x) <= N かつ (A - x) >= 1

が満たされる条件である。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt();
            int[] a = new int[n];
            int max = -INF, min = INF;
            for (int i = 0; i < n; i++) {
                a[i] = in.nextInt();
                max = max(max, a[i]);
                min = min(min, a[i]);
            }

            if (max - min >= 2) {
                out.println("No");
                return;
            }

            if (max == min) {
                if (a[0] == n - 1 || 2 * a[0] <= n) {
                    out.println("Yes");
                    return;
                }
            } else {
                int x = 0;
                for (int i = 0; i < n; i++) if (a[i] == max - 1) x++;
                int y = max - x;
                if (y >= 1 && x + 2*y <= n) {
                    out.println("Yes");
                    return;
                }
            }

            out.println("No");
            return;

        }

ポイント

  • 実験する
  • 条件を整理する

類題