結果

問題 No.252 "良問"(良問とは言っていない (2)
ユーザー pekempeypekempey
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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