Edited at

ABC124 C - Coloring Colorfully (300点)


問題概要

問題のリンク

0か1で構成された長さ$N$の文字列$S$が与えられる。

0を1に変えるあるいは、1を0に変える操作を文字列に加え、0と1が交互に並ぶようにしたい。必要な操作の最小回数は何回か。


制約条件


  • $1≤|S|≤10^5$

  • $S_i$ は 0 または 1 である。


考えたこと

文字列の最終形は0と1が交互に並んでいるものであるため、二通りが想定される。例えば長さ3であれば、$010$か$101$が最終形になる。

よって、この想定される二通りの最終形と初めに与えられる文字列を比較し、異なっている部分の数をそれぞれ数え上げ、小さい方が答えとなる。

なお、実装時の注意点として string 型で比較しようとして以下のような実装をすると、TLEする。

string s = "";

for(int i = 0; i < n; i ++) {
if(i%2==0) s += "1";
else s += "0";
}

以下の記事を参照すると s += "1" のような+演算子による文字列結合は200000回で2秒以上かかっている。

文字列処理を高速に行う

よって +演算子を使って文字列結合をするのではなく、 char型の配列を作って比較を行った。この時計算量は$O(N)$となる。


解答


c.cs

using System;

using System.Linq;

class Program
{
static void Main(string[] args) {
char[] s = Console.ReadLine().ToCharArray();
Console.WriteLine(solve(s, s.Length));
}
static int solve(char[] s, int n) {
char[] s1 = new char[n];
char[] s2 = new char[n];
for(int i = 0; i < n; i ++) {
if(i%2==0) {
s1[i] = '1';
s2[i] = '0';
}
else {
s1[i] = '0';
s2[i] = '1';
}
}
int count1 = 0;
int count2 = 0;
for(int i = 0; i < n; i ++) {
if(s[i] != s1[i]) count1 ++;
if(s[i] != s2[i]) count2 ++;
}
return Math.Min(count1,count2);
}
}