結果

問題 No.252 "良問"(良問とは言っていない (2)
ユーザー masamasa
提出日時 2015-10-04 02:15:24
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 81 ms / 2,000 ms
コード長 1,460 bytes
コンパイル時間 679 ms
コンパイル使用メモリ 71,072 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-19 19:29:24
合計ジャッジ時間 2,105 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
5,248 KB
testcase_01 AC 81 ms
5,376 KB
testcase_02 AC 37 ms
5,376 KB
testcase_03 AC 39 ms
5,376 KB
testcase_04 AC 38 ms
5,376 KB
testcase_05 AC 38 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using namespace std;
const string good = "good";
const string problem = "problem";
const int INF = 1e8;

int main() {
	int t;
	string s;
	int len_g = good.size();
	int len_p = problem.size();

	cin >> t;

	vector<int> pos_g;
	vector<int> pos_p;
	vector<bool> is_p;

	int diff;
	vector<int> answers;
	while (t--) {
		cin >> s;
		int limit = s.size() - len_p + 1;

		pos_g.assign(len_g + 1, INF);
		pos_p.assign(len_p + 1, -1);
		is_p.assign(s.size(), false);

		for (int i = 0; i < limit; i++) {
			diff = 0;
			for (int j = 0; j < len_g; j++) {
				if (s[i + j] != good[j]) {
					diff++;
				}
			}
			pos_g[diff] = min(pos_g[diff], i);

			diff = 0;
			for (int j = 0; j < len_p; j++) {
				if (s[i + j] != problem[j]) {
					diff++;
				}
			}
			pos_p[diff] = max(pos_p[diff], i);
			if (diff == 0) {
				is_p[i] = true;
			}
		}

		int ans = len_g + len_p;
		int add; // goodの前方にあるproblemを壊す
		for (int i = 0; i <= len_g; i++) {
			for (int j = 0; j <= len_p; j++) {
				if (pos_g[i] + len_g - 1 < pos_p[j]) {
					if (pos_g[i] < len_p) {
						add = 0;
					} else {
						add = count(is_p.begin(), is_p.begin() + pos_g[i] - len_p + 1, true);
					}

					ans = min(ans, i + j + add);
				}
			}
		}

		answers.push_back(ans);
	}

	for (int i = 0; i < answers.size(); i++) {
		cout << answers[i] << endl;
	}
	return 0;
}
0