マトリョーシカ的日常

ワクワクばらまく明日のブログ。

冷静と沈着の間の赤と緑(Topcoder SRM521 div2 250pt)

文字を埋め尽くせ!

 Spaghetti con Bottarga - 無料写真検索fotoq
photo by Pabo76


 久しぶりにプログラミング記事を投稿。今回は文字列処理をやってみた。
 TopCoder Statistics - Problem Statement

 赤(R)と緑(G)のブロック塀が一列に並んでいる。それを左側が赤、右側が緑になるように色を塗り替えなくてはいけない。(並び替えるわけではない)塗り替える最小の回数を返せ。
 例:"RRRGGGGG" → 0 塗り替える必要なし。
  :"GGGGRRR"→3 Rを全てGに塗り替える。
  :"RRRGGGRGGGRGGRRRGGRRRGR"→9

 以下、コード。

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
 class RedAndGreen{
	public:
	int minPaints (string str1)	{
        cout <<"str1=:"<< str1 <<endl;
        int min=str1.size(),k=0;
        string str2;
        str2=str1;
        for(int j=0;j<str2.size();j++){
            fill(str2.begin(),str2.begin()+j,'R');
            fill(str2.begin()+j,str2.end(),'G');
            for (int i=0;i<str2.size();i++){
                if(str1[i]!=str2[i]){k++;}
            }
            cout << str2<< ":"<<k<<endl;
            if (min>k) {min=k;}
            k=0;
        }
        cout <<min <<endl;
        return min;
    }
};

int main(){
    RedAndGreen ob1;
    string row("GRRGGRGG");
    ob1.minPaints(row);
    return 0;
}
  • 引数の文字数分あらかじめ文字列をつくっておく。
  • それらはGGGG,RGGG,RRGG,RRRG,RRRRと初期化する。
  • 引数の文字列と比較して異なっている文字数を返し、最小のものを選ぶ。
  • fill(str2.begin(),str2.begin()+j,'R');で文字列str2のはじめからj個分をRで埋める。
  • fill(str2.begin()+j,str2.end(),'G');文字列str2のj番目から最後までをGで埋める。