結果

問題 No.252 "良問"(良問とは言っていない (2)
ユーザー startcpp
提出日時 2015-07-25 00:04:04
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 407 ms / 2,000 ms
コード長 1,892 bytes
コンパイル時間 662 ms
コンパイル使用メモリ 83,816 KB
実行使用メモリ 59,072 KB
最終ジャッジ日時 2024-07-16 01:23:56
合計ジャッジ時間 3,285 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:39:43: warning: ISO C++ forbids converting a string constant to ‘char*’ [-Wwrite-strings]
   39 |                         g[i] = gethamming("good", s + i, 4);
      |                                           ^~~~~~
main.cpp:42:43: warning: ISO C++ forbids converting a string constant to ‘char*’ [-Wwrite-strings]
   42 |                         p[i] = gethamming("problem", s + i, 7);
      |                                           ^~~~~~~~~
main.cpp:49:49: warning: ISO C++ forbids converting a string constant to ‘char*’ [-Wwrite-strings]
   49 |                         if (i > 0 && gethamming("problem", s + i - 1, 7) == 0) {
      |                                                 ^~~~~~~~~

ソースコード

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

//リメイク版出題ありがとうございます！(@startcpp)
//考察：
//
//先頭i文字目から"good"、先頭j文字目から"problem"を作ることを考える。(j >= i + 4)
//このとき、goodを作るためのコストをg[i], problemを作るためのコストをp[j]とする。
//すると、g[i] + p[j]がこの時の良問のコストであり、g[i] + p[j]の最小値が本問の答え。
//…と思いたいが、"good"の前に"problem"がある場合は、それを壊す必要があるのでそのコストも考慮する必要がある。
//壊すコストは、i-1文字目までにある"problem"の個数となる。
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<functional>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int gethamming(char *s, char *t, int len);
int t;
char s[1000002];
int g[1000000];
int p[1000000];
multiset<int> minP;
signed main() {
    cin >> t;
    while (t--) {
        cin >> s;
        int slen = strlen(s);
        for (int i = 0; i < slen - 10; i++) {
            g[i] = gethamming("good", s + i, 4);
        }
        for (int i = 4; i < slen - 6; i++) {
            p[i] = gethamming("problem", s + i, 7);
            minP.insert(p[i]);
        }
        
        int breakcost = 0;
        int ans = 114514;
        for (int i = 0; i < slen - 10; i++) {
            if (i > 0 && gethamming("problem", s + i - 1, 7) == 0) {
                breakcost++;
            }
            //p[i+4]～p[slen-6]の中の最小値を求めてans更新なり
            ans = min(ans, g[i] + *minP.begin() + breakcost);
            //p[i+4]を集合から削除っと
            multiset<int>::iterator it = minP.find(p[i+4]);
            if (it != minP.end() )
                minP.erase(it);
        }
        cout << ans << endl;
    }
    return 0;
}
int gethamming(char *s, char *t, int len) {
    int score = 0;
    for (int i = 0; i < len; i++)
        score += (s[i] != t[i]);
    return score;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0