結果
問題 | No.252 "良問"(良問とは言っていない (2) |
ユーザー | startcpp |
提出日時 | 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) { ^
ソースコード
//リメイク版出題ありがとうございます!(@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; }