問題
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;
}