C - A-B Palindrome

問題

https://codeforces.com/contest/1512/problem/C (新しいタブで開く)

問題文

0, 1, ? からなる長さ $a + b$ の文字列 $s$ が与えられる。
? を 0 か 1 に置き換えて、 0 と 1 をそれぞれちょうど $a$, $b$ 個含むような回文にできるか？

制約

• $1 \le t \le 10^4$
• $0 \le a, b \le 2 \times 10^5$
• $|s| = a + b \ge 1$
• $|s|$ の総和は $2 \times 10^5$ を超えない

サンプル

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

考察

とりあえず $n = |s|$ としておく。

1. $n$ が奇数なら、中央の文字は $a, b$ のうち奇数である方である必要があるので、チェック。 ? なら置き換えて、 $a, b$ の適当なほうから 1 引いておく。
2. この時点で $a, b$ が奇数なら、むり。
3. 前から半分まで見て行って、前半と後半で回文を満たしているかチェック。 ? なら置き換えておく。$a, b$ からいい感じに引いておく。
4. もし $a, b$ が負になったら、むり。というのも、すでに $a, b$ の文字数制限を超えてるから。
5. 余った ? を置き換えていく。これは 0 に変えられるなら変えて、変えられないなら 1 に変える、という感じで OK。条件を満たせば任意の解で AC なので。
6. 出力。

コード

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