AtCoder Beginner Contest 124 C - Coloring Colorfully
今回のABC124は自己ベストのパフォーマンス949が出せてご満悦のねむーです。
今回はAtCoder(https://atcoder.jp/contests/abc124)にて開催されました、AtCoder Beginner Contest 124 C問題「C - Coloring Colorfully」の問題と僕との戦闘記です。
0.はじめに
1.問題文
左右一列に N 枚のタイルが並んでおり、各タイルの初めの色は長さ N の文字列 S で表されます。
左から i 番目のタイルは、 S の i 番目の文字が 0 のとき黒色で、1 のとき白色で塗られています。
あなたは、いくつかのタイルを黒色または白色に塗り替えることで、どの隣り合う 2 枚のタイルも異なる色で塗られているようにしたいです。
最小で何枚のタイルを塗り替えることで条件を満たすようにできるでしょうか。
2.制約
- 1 ≤ | S | ≤ 105
- S i は 0 または 1 である。
3.入力例
- 入力
10010010
- 出力
3
4.初見の感想
- 制約が105なので、入れ替える場所をすべて試す全探索的な考え方は無理そう
- 最終的な変更結果となる白黒の並びは「奇数番目が白、偶数番目が黒」もしくは「奇数番目が黒、偶数番目が白」の2パターンしかない
- 上の2パターンと入力の差を考えればよいのでは?
5.コードの簡単な解説
- まず、入力を配列に保存します
char[] input = Console.ReadLine().ToArray();
- 奇数番目が黒、偶数番目が白のパターンとの誤差をカウント
int count = 0; for (int i = 0; i < input.Count(); i++) { if (i % 2 == 0 && input[i] == '0') { count++; } else if(i % 2 == 1 && input[i] == '1') { count++; } }
- 同様に奇数番目が白、偶数番目が黒のパターンも行う
int count_another = 0; for (int i = 0; i < input.Count(); i++) { if (i % 2 == 0 && input[i] == '1') { count_another++; } else if (i % 2 == 1 && input[i] == '0') { count_another++; } }
- 結果が少ない方を出力
if (count > count_another) { Console.WriteLine(count1); } else { Console.WriteLine(count); }
6.全コード
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main(string[] args) { char[] input = Console.ReadLine().ToArray(); int count = 0; for (int i = 0; i < input.Count(); i++) { if (i % 2 == 0 && input[i] == '0') { count++; } else if(i % 2 == 1 && input[i] == '1') { count++; } } int count_another = 0; for (int i = 0; i < input.Count(); i++) { if (i % 2 == 0 && input[i] == '1') { count_another++; } else if (i % 2 == 1 && input[i] == '0') { count_another++; } } if (count > count_another) { Console.WriteLine(count1); } else { Console.WriteLine(count); } } }
7.最後にご報告
遂にAtCoder茶色になりました!
これからもレート更新できるようがんばります!