#40262 (C++11（廃止可能性あり）) No.252 "良問"(良問とは言っていない (2)

• 問題: No.252 "良問"(良問とは言っていない (2)
• ユーザー: wahr69
• 提出日時: 2015-07-30 16:57:54
• 言語: C++11（廃止可能性あり） (gcc 13.3.0)
• 結果: AC
• 実行時間: 80 ms / 2,000 ms
• コード長: 2,024 bytes
• コンパイル時間: 583 ms
• コンパイル使用メモリ: 63,360 KB
• 実行使用メモリ: 12,128 KB
• 最終ジャッジ日時: 2024-07-17 22:37:00
• 合計ジャッジ時間: 1,459 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

ファイルパターン	結果
other	AC * 7

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
const string GOOD = "good";
const string PROBLEM = "problem";
int dpMinGood[1000000]; // この位置より左でgoodに書き換える場合に必要な最小の書き換え回数
int dpMinProblem[1000000]; // この位置より右でproblemに書き換える場合に必要な最小の書き換え回数
int main() {
    int T;
    cin >> T;
    vector<string> S(T);
    for (int i = 0; i < T; ++i) {
        cin >> S[i];
    }
    for (int i = 0; i < T; ++i) {
        int weight = 0;
        for (int j = 0; j <= S[i].length() - 11; ++j) {
            int goodCount = 0;
            for (int k = 0; k < 4; ++k) {
                if (S[i][j + k] != GOOD[k]) {
                    ++goodCount;
                }
            }
            if (j == 0) {
                dpMinGood[j] = goodCount;
            } else {
                dpMinGood[j] = min(goodCount, dpMinGood[j - 1]);
            }
            // 左からgoodを見ていったとき、すでにproblemがあれば1文字変更が必要なので+1する
            if (j >= 7) {
                int count = 0;
                for (int k = 0; k < 7; ++k) {
                    if (S[i][j - 7 + k] != PROBLEM[k]) {
                        break;
                    }
                    ++count;
                }
                if (count == 7) {
                    ++weight;
                }
            }
            dpMinGood[j] += weight;
        }
        for (int j = S[i].length() - 7; j >= 0; --j) {
            int count = 0;
            for (int k = 0; k < 7; ++k) {
                if (S[i][j + k] != PROBLEM[k]) {
                    ++count;
                }
            }
            if (j == S[i].length() - 7) {
                dpMinProblem[j] = count;
            } else {
                dpMinProblem[j] = min(count, dpMinProblem[j + 1]);
            }
        }
        int min1 = 99999;
        for (int j = 0; j <= S[i].length() - 11; ++j) {
            int sum = dpMinGood[j] + dpMinProblem[j + 4];
            if (sum < min1) {
                min1 = sum;
            }
        }
        //  for (int j2 = j + 4; j2 <= S[i].length() - 7; ++j2) {
        //      int problemCount = 0;
        //      for (int k = 0; k < 7; ++k) {
        //          if (S[i][j2 + k] != PROBLEM[k]) {
        //              ++problemCount;
        //          }
        //      }
        //      int sum = goodCount + problemCount;
        //      if (sum < min1) {
        //          min1 = sum;
        //      }
        //  }
        //}
        cout << min1 << endl;
    }
    getchar();
    getchar();
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX