CF Round #713 C - A-B Palindrome


Tags:cpcodeforcesdiv3stringgreedyconstructive

問題

https://codeforces.com/contest/1512/problem/C

問題文

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

制約

  • 1t1041 \le t \le 10^4
  • 0a,b2×1050 \le a, b \le 2 \times 10^5
  • s=a+b1|s| = a + b \ge 1
  • s|s| の総和は 2×1052 \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=sn = |s| としておく。

  1. nn が奇数なら、中央の文字は a,ba, b のうち奇数である方である必要があるので、チェック。 ? なら置き換えて、 a,ba, b の適当なほうから 1 引いておく。
  2. この時点で a,ba, b が奇数なら、むり。
  3. 前から半分まで見て行って、前半と後半で回文を満たしているかチェック。 ? なら置き換えておく。a,ba, b からいい感じに引いておく。
  4. もし a,ba, b が負になったら、むり。というのも、すでに a,ba, 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;
}