問題
https://codeforces.com/contest/1512/problem/C (新しいタブで開く)
問題文
0
, 1
, ?
からなる長さ の文字列 が与えられる。
?
を 0
か 1
に置き換えて、 0
と 1
をそれぞれちょうど , 個含むような回文にできるか?
制約
- の総和は を超えない
サンプル
9 4 4 01?????0 3 3 ?????? 1 0 ? 2 2 0101 2 2 01?0 0 1 0 0 3 1?1 2 2 ?00? 4 3 ??010?0
01011010 -1 0 -1 0110 -1 111 1001 0101010
考察
とりあえず としておく。
- が奇数なら、中央の文字は のうち奇数である方である必要があるので、チェック。
?
なら置き換えて、 の適当なほうから 1 引いておく。 - この時点で が奇数なら、むり。
- 前から半分まで見て行って、前半と後半で回文を満たしているかチェック。
?
なら置き換えておく。 からいい感じに引いておく。 - もし が負になったら、むり。というのも、すでに の文字数制限を超えてるから。
- 余った
?
を置き換えていく。これは0
に変えられるなら変えて、変えられないなら1
に変える、という感じで OK。条件を満たせば任意の解で AC なので。 - 出力。
コード
https://codeforces.com/contest/1512/submission/183571863 (新しいタブで開く)
inline bool q(char x) { return x == '?'; } void solve() { int a, b; cin >> a >> b; string s; cin >> s; int n = s.size(); if (n % 2 == 1) { if (q(s[n / 2])) { s[n / 2] = (a % 2 == 1 ? '0' : '1'); (s[n / 2] == '0' ? a : b)--; } else if (s[n / 2] == '0' && a % 2 == 1) { a--; } else if (s[n / 2] == '1' && b % 2 == 1) { b--; } else { cout << -1 << endl; return; } } if (a % 2 == 1 || b % 2 == 1) { cout << -1 << endl; return; } rep(i, n / 2) { if (!q(s[i]) && !q(s[n - i - 1]) && s[i] != s[n - i - 1]) { cout << -1 << endl; return; } if (q(s[i]) && q(s[n - i - 1])) continue; if (q(s[i]) && !q(s[n - i - 1])) s[i] = s[n - i - 1]; if (!q(s[i]) && q(s[n - i - 1])) s[n - i - 1] = s[i]; (s[i] == '0' ? a : b) -= 2; } if (a < 0 || b < 0) { cout << -1 << endl; return; } rep(i, n / 2) { if (q(s[i])) { if (a >= 2) { s[i] = s[n - i - 1] = '0'; a -= 2; } else { s[i] = s[n - i - 1] = '1'; b -= 2; } } } cout << s << endl; return; }