結果

問題 No.252 "良問"(良問とは言っていない (2)
ユーザー masamasa
提出日時 2015-10-04 02:15:24
言語 C++11
(gcc 13.3.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
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

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; // goodproblem
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0