結果
問題 | No.252 "良問"(良問とは言っていない (2) |
ユーザー |
|
提出日時 | 2015-07-25 12:11:53 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 264 ms / 2,000 ms |
コード長 | 2,477 bytes |
コンパイル時間 | 1,504 ms |
コンパイル使用メモリ | 168,872 KB |
実行使用メモリ | 24,252 KB |
最終ジャッジ日時 | 2024-07-16 04:52:09 |
合計ジャッジ時間 | 3,576 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 7 |
ソースコード
#include <bits/stdc++.h>#define rep(i, a) for (int i = 0; i < (a); i++)#define rep2(i, a, b) for (int i = (a); i < (b); i++)#define repr(i, a) for (int i = (a) - 1; i >= 0; i--)#define repr2(i, a, b) for (int i = (b) - 1; i >= (a); i--)#define itall(a) a.begin(), a.end()using namespace std;typedef long long ll;const ll inf = 1e9;const ll mod = 1e9 + 7;const double pi = acos(-1);const double eps = 1e-8;template<typename T> inline T sq(T a) { return a * a; }template<typename T> inline T cb(T a) { return a * a * a; }template<typename T> inline bool umin(T &a, const T &b) { return b < a && (a = b, true); }template<typename T> inline bool umax(T &a, const T &b) { return a < b && (a = b, true); }const int infP = inf;template<class T>struct RMQ {vector<T> seg;int size;RMQ(int n) {size = 1;while (size < n) size *= 2;seg.resize(size * 2 - 1, infP);}void update(int k, T x) {k += size - 1;seg[k] = x;while (k > 0) {k = (k - 1) / 2;seg[k] = min(seg[k * 2 + 1], seg[k * 2 + 2]);}}T query(int a, int b, int k, int l, int r) {if (r <= a || b <= l) return infP;if (a <= l && r <= b) return seg[k];T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);return min(vl, vr);}T query(int a, int b) {return query(a, b, 0, 0, size);}};string a = "good", b = "problem";int sum[1000010];int hamA[1000010], hamB[1000010];int main() {int q;cin >> q;rep (z, q) {string s;cin >> s;fill(sum, sum + s.length() + 10, 0);fill(hamA, hamA + s.length(), 0);fill(hamB, hamB + s.length(), 0);for (int i = s.find(b); i != string::npos; i = s.find(b, i + 1)) {sum[i + b.length()]++;}rep2 (i, 1, s.length()) {sum[i] += sum[i - 1];}rep (i, s.length() - 3) {rep (k, 4) hamA[i] += s[i + k] != a[k];}rep (i, s.length() - 6) {rep (k, 7) hamB[i] += s[i + k] != b[k];}RMQ<int> rmq(s.length());rep (i, s.length() - 6) {rmq.update(i, hamB[i]);}int ans = inf;rep (i, s.length() - 3) {umin(ans, hamA[i] + sum[i] + rmq.query(i + 4, s.length()));}cout << ans << endl;}}