結果

問題 No.252 "良問"(良問とは言っていない (2)
ユーザー startcppstartcpp
提出日時 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;
}
0