提出 #33627134

---

ソースコード 拡げる

// Author: Ruhan Habib (ruhanhabib39@gmail.com)

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int MAXN = 2e5;

bool dp[MAXN + 10][2][2];

bool solve (int n, string s) {
   vector<int> x(n);
   for (int i = 0; i < n; i++) {
      x[i] = int(s[i] == 'B');
   }

   for (int l = 0; l < 2; l++) {
      for (int r = 0; r < 2; r++) {
         dp[1][l][r] = l == r;
      }
   }


   int m1 = (n - 1) / 2, m2 = n / 2;
   int k;
   for (k = 2; m1 - (k - 1) >= 0 && m2 + (k - 1) < n; k++) {
      int i = m1 - (k - 1), j = m2 + (k - 1);

      for (int l : {0,1}) {
         for (int r : {0, 1}) {
            dp[k][l][r] = l == r && dp[k-1][x[i+1]][x[j-1]];
            if ((n & 1) && (k == 2)) {
               dp[k][l][r] |= 0 == r && dp[k-1][1][1];
               dp[k][l][r] |= l == 1 && dp[k-1][0][0];
            } else {
               dp[k][l][r] |= 0 == r && dp[k-1][1][x[j-1]];
               dp[k][l][r] |= l == 1 && dp[k-1][x[i+1]][0];
            }
         }
      }
   }
   k--;

   return dp[k][x[0]][x[n-1]];
}

int main() {
   ios_base::sync_with_stdio(false);
   cin.tie(0);

   int n; cin >> n;
   string s; cin >> s;
   bool res = solve(n, s);
   if (res) cout << "Yes\n";
   else cout << "No\n";
}

提出情報

ジャッジ結果