yukicoder : No.1924 3 color painting on a line

実装は軽いが。
https://yukicoder.me/problems/no/1924

問題

1列に並んだNマスを、3色で塗り分けることを考える。
初期状態で、各マスは何も塗られていない。
また、最終的な塗り分け方が入力で与えられる。

1回の操作で、1つのマスの区間を1色で塗ることができる。
その際、すでに色が塗られたマスがあれば、上塗りする。

最終的な塗り分け方を達成するのに対し、最小の操作回数を求めよ。

解法

stackを使い、入力の塗り分け方を1マスずつ見て行き、以下を貪欲に行おう。

• stackが空なら、見ているマスの色を追加
• stackが空でない場合、
  • stackのtopと、今見ているマスの色が一致するなら、それらはまとめて塗れるので、今見ているマスは無視してよい。
  • stackの上から2色目と、今見ているマスの色が一致する場合、1操作掛けてstackの最上位の色を(後で塗りつぶすとみなして)stackから削除しよう。
  • 上のいずれでもない場合、stackの末尾に見ているマスの色を追加する。

上記を完了すると、stackはabcabcabc....と3色が同じパターンで繰り返すことになる。
その時、最多登場であるaを先に1操作で全部塗りつぶした後、残ったb・cをそれぞれ1マス1操作で上塗りしていくとよい。

int N;
string S,T;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	int ret=0;
	FORR(c,S) {
		if(T.empty()) {
			T+=c;
		}
		else if(T.back()==c) {
			continue;
		}
		else if(T.size()>=2&&T[T.size()-2]==c) {
			ret++;
			T.pop_back();
		}
		else {
			T+=c;
		}
	}
	
	FORR(c,T) if(c!=T[0]) ret++;
	ret++;
	
	cout<<ret<<endl;
}

まとめ

あとで類題出そうだし、この貪欲は覚えておきたい。