Codeforces Round #629 (Div. 3) - D. Carousel
概要
円状にN個の数が並んでいて、時計回り順にt[i]である。次の条件を満たすように、これらの数に色を塗る。
- 隣り合った異なる値の数字どうしは、必ず異なる色が塗られている。
これを満たすように、最小限に色を使って塗ったときの一例を示せ。
制約： 1 <= N <= 2 * 10^5
ACするまで
1. ひとまず、全部同じ数字ならば1色だけで済む。
2. うまく色を赤、青、赤、青 のようにおくことができれば2色、そうでなければ3色でできそう。
3. 2色でできる条件として、偶数個あるのならば、必ずできる。
4. 奇数個存在時に、2色の条件はどうだろう？実は「1組以上の同じ数字が隣り合わせ」であればよい。
考察
1色でできる場合は、明らかにすべての数字が同じ場合である。
そうでない場合、赤、青、赤、青 と交互に置くことができるのならば、数字の値関係なく2色で塗り分けできる。
これが無条件にできるのは、Nが偶数の時であり、奇数の時は別の条件が付く。
問題文の条件は、同じ数字の間での色の制約を設けていない。よって、同じ数字が並んでいる場合、隣り合わせたいくつかを同色にしてもよい。
このとき、1つでも隣と同じのものが存在する場合、このペアを同じ色で塗ることによって、問題のサイズを1つ減らすことができる。奇数の場合、これが使えるのならば偶数パターンへ帰着でき、色2種類で塗り分けが可能。
一言
やる気を何とか戻して今日からDiv3埋めを継続せねば
