結果
問題 | No.252 "良問"(良問とは言っていない (2) |
ユーザー |
![]() |
提出日時 | 2015-07-24 22:46:02 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 85 ms / 2,000 ms |
コード長 | 1,090 bytes |
コンパイル時間 | 709 ms |
コンパイル使用メモリ | 90,480 KB |
実行使用メモリ | 12,188 KB |
最終ジャッジ日時 | 2024-07-08 13:22:04 |
合計ジャッジ時間 | 1,601 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 7 |
ソースコード
#include <algorithm>#include <climits>#include <algorithm>#include <functional>#include <iostream>#include <map>#include <queue>#include <random>#include <set>#include <string>#include <vector>using namespace std;typedef long long ll;typedef pair<int, int> i_i;int MOD = 1000000007;bool check(string& S, int i, string s) {for (int j = 0; j < s.length(); j++)if (S[i + j] != s[j])return false;return true;}int main() {int T; cin >> T;while (T--) {string S; cin >> S;int n = S.length();vector<int> a(n + 1);for (int i = 1; i <= n; i++) {a[i] = a[i - 1];if (i >= 7 && check(S, i - 7, "problem"))a[i]++;}vector<int> b(n + 1, INT_MAX / 2);for (int i = n - 7; i >= 0; i--) {int cnt = 0;for (int j = 0; j < 7; j++)if (S[i + j] != "problem"[j])cnt++;b[i] = min(b[i + 1], cnt);}int mini = INT_MAX / 2;for (int i = 0; i + 4 <= n; i++) {int sum = a[i] + b[i + 4];for (int j = 0; j < 4; j++)if (S[i + j] != "good"[j])sum++;mini = min(mini, sum);}cout << mini << endl;}}