Codeforces Round #629 (Div. 3)-D 「Carousel」

Problem - D - Codeforces
問題概要は
「n個の模様を円形にならべたカルーセルについて、隣り合う模様が異なるときは違う色に塗る。このとき使用する色の最小数と、その塗り方を答えよ」
というものです。ちなみにカルーセルはメリーゴーランドという意味の言葉なんですね、知らなかったです。

◇さて、まずすべての模様が同じ場合は1色で塗ればよいですね。すべて1で塗ります。
　以下、異なる模様が存在する場合を考えます。

◇nが偶数のときは、隣り合う模様が異なるかどうかによらず、1と2で交互に塗れば良いです。なぜかというと、例えばn=6のとき、
　1-2-1-2-1-2　となり、1番目と6番目の色が異なります。nが偶数であれば問題なく2色で塗れるわけです。

◇やっかいなのがnが奇数のときです。以下の3パターンに分かれます。

①1番目とn番目が同じ模様の場合
...この場合は、nが偶数のときと同様に1と2で交互に塗れば良いです。1番目とn番目は同じ模様なので、同じ色で塗ってokです。

②どの模様も隣り合う模様と異なっているとき
...この場合は1と2で交互に塗っていくしかないですが、n番目の模様を1で塗る（nは奇数なので）とき、1番目の模様も1で塗られていて被ってしまいます。そのため、n番目の模様を3で塗ります。3色必要ですね。

③同じ模様が隣り合っている箇所がある場合
...①のパターンを含みます。この場合は隣り合っている部分の2つの模様を同じ色で塗り、それ以外は1と2を交互に塗る方法で良いです。例えばn=3のとき、
　1-2-1-2-2-1-2　となります。1か所だけ同じ色で連続して塗れば、n番目は2で塗られ、1番目の1と異なります。

やや複雑でしたが、そこまで難しい考察は必要ない問題ですね。僕は解けていないんですが（）
↓コードです。

int main()
{
    
    ll q;
    cin >> q;
    
    while(q--){
        ll n;
        cin >> n;
        vector<ll> t(n);
        bool ok=true; //すべて同じ模様ならtrue
        rep(i,n){
            cin >> t[i];
            if(i){
                if(t[i]!=t[i-1]) ok=false;
            }
        }
        //すべて同じ模様の場合
        if(ok){
            cout << 1 << endl;
            rep(i,n){
                if(i) cout << " ";
                cout << 1;
            }
            cout << endl;
            continue;
        }
        //nが偶数のとき
        if(n%2==0){ 
            cout << 2 << endl;
            rep(i,n){
                if(i) cout << " ";
                if(i%2==0) cout << 1;
                else cout << 2;
            }
            cout << endl;
            continue;
        }
        ll p=1;
        ll q=2;
        ll pos=-1;
        //奇数の場合１
        if(t[n-1]==t[0]){
            cout << 2 << endl;
            rep(i,n){
                if(i) cout << " ";
                if(i%2==0) cout << 1;
                else cout << 2;
            }
            cout << endl;
            continue;
        }
        rep(i,n){
            if(i){
                if(t[i]==t[i-1]){
                    pos=i;
                    break;
                }
            }
        }
        //奇数の場合２
        if(pos==-1){
            cout << 3 << endl;
            rep(i,n){
                if(i) cout << " ";
                if(i==n-1){
                    cout << 3;
                    break;
                }
                if(i%2==0) cout << 1;
                else cout << 2;
            }
            cout << endl;
            continue;
        }
        //奇数の場合３
        cout << 2 << endl;
        rep(i,n){
            if(i) cout << " ";
            if(i==pos){
                p=2;
                q=1;
            }
            if(i%2==0) cout << p;
            else cout << q;
        }
        cout << endl;
        
        
    }
    return 0;
} 

奇数の場合の①と③はまとめてしまった方がきれいなコードかもしれません。

類題としてはAGC035-A「XOR Circle」等が挙げられそうです（こちらは実装というより考察が必要です）。
atcoder.jp