Coloring Colorfully

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

左右一列に N 枚のタイルが並んでおり、各タイルの初めの色は長さ N の文字列 S で表されます。

左から i 番目のタイルは、S の i 番目の文字が 0 のとき黒色で、1 のとき白色で塗られています。あなたは、いくつかのタイルを黒色または白色に塗り替えることで、どの隣り合う 2 枚のタイルも異なる色で塗られているようにしたいです。

最小で何枚のタイルを塗り替えることで条件を満たすようにできるでしょうか。

制約

1≤|S|≤10⁵ Si は 0 または 1 である。

とこんな感じ

O(N)で解けるのを想定したら結構簡単に解法がでてきたんでよかったです。

考えたこと

1箇所分かれば完成系の文字列がわかるので最初にそのデータ構造作ってしまって、そのあと線形的に照合をしていってカウントし、文字列の長さから引くと言う方法で行けるかなと思いました。最後の出力は文字列の長さからカウントを引いたものとカウントを比較し、小さい方を出力すれば問題は解けました。

フロー

入力の受け取り
最初の文字が0の時は以下の処理をする
- 文字の個数分繰り返しながら以下の処理をする
  - 偶数の時 0 奇数の時 1 を配列に格納する
0以外の時以下の処理をする
- 文字の個数分繰り返しながら以下の処理をする
  - 偶数の時 1 奇数の時 0 を配列に格納する
文字列に1文字つつアクセスする
- 作った配列と要素が違った場合カウントを1つ増やす
文字列の要素数からカウントを引いたものとカウントの比較をし小さい方を出力する

と考えました。最後の最初の算出は結局入れ違えの反転を考慮するものなので反転回数は |S|/2より以上にはならないのでここで比較を行います。

プログラム

このようになりました。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;

int main(void){
    string S;
    cin >> S;
    int N = S.size();
    vector<char> Trans(S.size());
    if (S[0] == '0'){
        for(int i = 0;i < S.size(); i++){
            Trans[i] = i % 2 == 0 ? '0' : '1';
        }
    }else{
        for(int i = 0;i < S.size(); i++){
            Trans[i] = i % 2 == 0 ? '1' : '0';
        }
    }
    int count = 0;
    for(int i = 0;i < S.size();i++){
        if(S[i] != Trans[i]){
            count++;
        }
    }
    cout << min(count,N-count) << endl;
    return 0;
}

これでAC取れました

xlkeiの日記

ABC-124 C Coloring Colorfully を解いてみた

Coloring Colorfully

問題文

制約

考えたこと

フロー

プログラム