結果

問題 No.252 "良問"(良問とは言っていない (2)
コンテスト
ユーザー wahr69
提出日時 2015-07-30 16:57:54
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 80 ms / 2,000 ms
コード長 2,024 bytes
コンパイル時間 583 ms
コンパイル使用メモリ 63,360 KB
実行使用メモリ 12,128 KB
最終ジャッジ日時 2024-07-17 22:37:00
合計ジャッジ時間 1,459 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

const string GOOD = "good";
const string PROBLEM = "problem";

int dpMinGood[1000000]; // この位置より左でgoodに書き換える場合に必要な最小の書き換え回数
int dpMinProblem[1000000]; // この位置より右でproblemに書き換える場合に必要な最小の書き換え回数

int main() {
	int T;
	cin >> T;
	vector<string> S(T);
	for (int i = 0; i < T; ++i) {
		cin >> S[i];
	}

	for (int i = 0; i < T; ++i) {
		int weight = 0;
		for (int j = 0; j <= S[i].length() - 11; ++j) {
			int goodCount = 0;
			for (int k = 0; k < 4; ++k) {
				if (S[i][j + k] != GOOD[k]) {
					++goodCount;
				}
			}
			if (j == 0) {
				dpMinGood[j] = goodCount;
			} else {
				dpMinGood[j] = min(goodCount, dpMinGood[j - 1]);
			}

			// 左からgoodを見ていったとき、すでにproblemがあれば1文字変更が必要なので+1する
			if (j >= 7) {
				int count = 0;
				for (int k = 0; k < 7; ++k) {
					if (S[i][j - 7 + k] != PROBLEM[k]) {
						break;
					}
					++count;
				}
				if (count == 7) {
					++weight;
				}
			}
			dpMinGood[j] += weight;
		}

		for (int j = S[i].length() - 7; j >= 0; --j) {
			int count = 0;
			for (int k = 0; k < 7; ++k) {
				if (S[i][j + k] != PROBLEM[k]) {
					++count;
				}
			}
			if (j == S[i].length() - 7) {
				dpMinProblem[j] = count;
			} else {
				dpMinProblem[j] = min(count, dpMinProblem[j + 1]);
			}
		}

		int min1 = 99999;
		for (int j = 0; j <= S[i].length() - 11; ++j) {
			int sum = dpMinGood[j] + dpMinProblem[j + 4];
			if (sum < min1) {
				min1 = sum;
			}
		}

		//	for (int j2 = j + 4; j2 <= S[i].length() - 7; ++j2) {
		//		int problemCount = 0;
		//		for (int k = 0; k < 7; ++k) {
		//			if (S[i][j2 + k] != PROBLEM[k]) {
		//				++problemCount;
		//			}
		//		}
		//		int sum = goodCount + problemCount;
		//		if (sum < min1) {
		//			min1 = sum;
		//		}
		//	}
		//}
		cout << min1 << endl;
	}

	getchar();
	getchar();
}
0