結果

問題 No.252 "良問"(良問とは言っていない (2)
ユーザー startcppstartcpp
提出日時 2015-07-25 00:04:04
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 376 ms / 2,000 ms
コード長 1,892 bytes
コンパイル時間 566 ms
コンパイル使用メモリ 78,308 KB
実行使用メモリ 59,076 KB
最終ジャッジ日時 2023-09-23 00:58:20
合計ジャッジ時間 3,448 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 196 ms
7,700 KB
testcase_01 AC 162 ms
7,484 KB
testcase_02 AC 276 ms
19,912 KB
testcase_03 AC 376 ms
59,076 KB
testcase_04 AC 373 ms
59,004 KB
testcase_05 AC 375 ms
58,980 KB
testcase_06 AC 2 ms
7,700 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:39:38: warning: ISO C++ forbids converting a string constant to ‘char*’ [-Wwrite-strings]
    g[i] = gethamming("good", s + i, 4);
                                      ^
main.cpp:42:41: warning: ISO C++ forbids converting a string constant to ‘char*’ [-Wwrite-strings]
    p[i] = gethamming("problem", s + i, 7);
                                         ^
main.cpp:49:51: warning: ISO C++ forbids converting a string constant to ‘char*’ [-Wwrite-strings]
    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;
}
0