解答:Submission #74875019 - Codeforces
解法:解説AC。配列Tの長さの偶奇が本質的。
まず、全ての要素が同じ場合は、全部1としてよい。これ以降は、配列Tの中の(n-1→0を含めた)隣接2項で異なる要素があるため、少なくとも1と2を使わないといけない。
Tの長さが偶数の場合は1, 2, 1, 2, ...のように1と2を交互にすると、どのような配列Tにも対応できる。
Tの長さが奇数の場合、次の2つの場合分けがある。
①(n-1→0を含めた)隣接2項で1か所でも同じ要素のものがある場合、その要素に対応する答えをどちらも同じ数字にできる。そうすると、その2つの要素をまとめて1つとして考えて偶数長の場合に見なすことができる。
②(n-1→0を含めた)隣接2項が全て異なる場合、1, 2, 1, 2, ... と交互に置くと、n-1項目が1で0項目も1となり適切でない。よってn-1項目を3にすればよい。