結果

問題 No.252 "良問"(良問とは言っていない (2)
ユーザー wahr69wahr69
提出日時 2015-07-30 16:20:26
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,664 bytes
コンパイル時間 508 ms
コンパイル使用メモリ 63,712 KB
実行使用メモリ 12,068 KB
最終ジャッジ日時 2024-07-17 22:36:12
合計ジャッジ時間 1,386 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 AC 35 ms
7,200 KB
testcase_03 AC 37 ms
12,068 KB
testcase_04 AC 37 ms
11,988 KB
testcase_05 AC 38 ms
12,016 KB
testcase_06 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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) {
		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]);
			}
		}

		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