結果

問題 No.252 "良問"(良問とは言っていない (2)
ユーザー pekempeypekempey
提出日時 2015-07-25 12:11:53
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 269 ms / 2,000 ms
コード長 2,477 bytes
コンパイル時間 1,759 ms
コンパイル使用メモリ 167,964 KB
実行使用メモリ 24,236 KB
最終ジャッジ日時 2023-09-23 04:49:08
合計ジャッジ時間 3,886 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 148 ms
7,688 KB
testcase_01 AC 129 ms
7,552 KB
testcase_02 AC 269 ms
14,884 KB
testcase_03 AC 266 ms
24,184 KB
testcase_04 AC 265 ms
24,236 KB
testcase_05 AC 266 ms
24,200 KB
testcase_06 AC 2 ms
7,528 KB
権限があれば一括ダウンロードができます

ソースコード

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;
    }
}
0