Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

JOI春合宿 2009-day1 Stamps

問題文 : 判子

解法 :
まず, この作業でスタンプを作ることは, スタンプからIOIOI...OIの形を復元することを考える. このとき, 境界条件を考えないために, IO と OI を文字列に連結する.
このとき, "OOO"や"III"の形で連結されている箇所があれば, 真ん中を変えることで作業を最短で追われる. (真ん中を抜いて文字を挿入すると2倍のコストがかかる.)
それでも連続している文字があれば, 該当する文字(の2番目)を抜けばよい. これを繰り返すことで元のスタンプの形が再現でき, IO...OIの形をしているので, 長さも奇数文字になっている.

コード:

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
	char str[1000010];
	int n;
	int mlen, mrep = 0;
	
	strcpy(str, "IO");
	scanf("%d", &n);
	scanf("%s", &str[2]);
	strcpy(str + n + 2, "OI");
	
	mlen = n;
	for (int i = 0; i < n + 4; i++){
		if (strncmp(&str[i], "III", 3) == 0 || strncmp(&str[i], "OOO", 3) == 0){
			str[i + 1] = (str[i + 1] == 'I' ? 'O' : 'I');
			mrep++;
		}
		if (i && str[i - 1] == str[i]){
			mrep++;
			mlen--;
		} 
	}
	
	printf("%d\n%d\n", mrep, mlen);
	
	return (0);
}