https://atcoder.jp/contests/cpsco2019-s4/tasks/cpsco2019_s4_e
解説(部分点解法)
https://atcoder.jp/contests/cpsco2019-s4/submissions/5285574
以下に疑似満点解法もあるが、こちらも紹介。
まずは、自明なNoパターンを弾いておこう。
「ox,xo,o,xの個数から使えるo,xの個数」と「文字列Sに含まれるo,xの個数」が一致するかを見ておこう。
自明なNoパターンを見つけたら、そうそうに排除しておくことで、一部のコーナーケースを回避できたりする。
ここから本番だが、ox,xoを作るのは大変そうだが、o,xはどこに置いても大丈夫そうな感じがある。
つまり、文字列SにかぶらないようにoxをA個、xoをB個おければSを作れそうな感じがする。
これは直感的に正しく、実際にも正しい。
よって、「文字列SにかぶらないようにoxをA個、xoをB個おけるか」という問題に帰着した。
これば部分点解法の制約であればDPで解決できる。
dp[i][a] := i文字目まで確定していて、置くべきoxがまだa個あるときに、置くべきxoの個数の最小個数
dp[0][A] = Bで他はinfで埋めた状態でスタート。
あとは、oxで置くか、xoで置くか、何も置かずに文字を1つ進めるかの3つの遷移でDPを埋めていき、
dp[N][0]==0になっていれば、置けたことになる。
int N; string S; int A, B, C, D; int dp[4040][4040]; //--------------------------------------------------------------------------------------------------- #define yes "Yes" #define no "No" string solve() { int maru = 0, batsu = 0; fore(c, S) { if (c == 'o') maru++; else batsu++; } if (A + B + C != maru or A + B + D != batsu) return no; S += "#"; rep(i, 0, N + 1) rep(a, 0, A + 1) dp[i][a] = inf; dp[0][A] = B; rep(i, 0, N) rep(a, 0, A + 1) if(dp[i][a] < inf) { chmin(dp[i + 1][a], dp[i][a]); if (S[i] == 'o' and S[i + 1] == 'x' and 0 < a) chmin(dp[i + 2][a - 1], dp[i][a]); if (S[i] == 'x' and S[i + 1] == 'o' and 0 < dp[i][a]) chmin(dp[i + 2][a], dp[i][a] - 1); } if (dp[N][0] == 0) return yes; return no; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> S >> A >> B >> C >> D; cout << solve() << endl; }
解法(満点解法)
公式解説のつなぎ、hamayanhamayanのポエムとして見てほしい。
自分も解法わかってないし。
- DP解は思いついたけど、これの高速化は思いつかない
- 今回の問題若干マッチング問題っぽくないか?
- マッチング問題って貪欲解あるケース結構あるよね これ
- 全体見てみると、xoxoxoとかoxoxoとかの塊毎に独立して、数えることができそう
- これ貪欲やな。無理です。
コンテスト後TLにて
- oxoxoとxoxoxの価値がoxに取ってもxoに取っても一緒(beetさん)
- oxoxox...oxのうちフルに使えるものの個数で全探索。短い方から使っていく(kobaさん)
- oxかxoどちらかに全力を注いでもいいことがわかって、どっちも試す(latteさん)
- ooとかxxの部分で切って、頑張る(beetさん)
- S を oxoxo xoxo o xo とSi=Sjのところで分解して貪欲(drafearさん)