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); }