D. Bishwock (DP solution)

• Quiz
  • https://codeforces.com/contest/991/problem/D
• AC
  • https://codeforces.com/contest/991/submission/100399548
• 解説
  • editorialは以外にもDPではなかった。私はDPで解いた
  • 左から埋めていくとして、何か置くと次の位置も埋めてしまう。ただ、埋まり方は4パターンしかないのでDPの第2要素 j として持てばいい
  • 入力の文字列は番兵的に先端・後端をXで挟んでおいた

// j
// 0 : empty
// 1 : upper filled
// 2 : lower filled
// 3 : both  filled
ll dp[110][4];

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

    // input
    string s,t;
    cin>>s>>t;
    ll N = s.size();
    s = "X" + s + "X";
    t = "X" + t + "X";

    char x = 'X';
    char o = '0';
    
    ll ma=0;
    FOR(i,1,N+1){
      // put nothing
      rep(j,4) chmax(dp[i+1][0], dp[i][j]);

      // ■■
      // ■
      if(s[i]==o && t[i]==o && s[i+1]==o){
        chmax(dp[i+1][1], dp[i][0]+1);
      }

      // ■
      // ■■
      if(s[i]==o && t[i]==o && t[i+1]==o){
        chmax(dp[i+1][2], dp[i][0]+1);
      }

      //  ■
      // ■■
      if(t[i]==o && t[i+1]==o && s[i+1]==o){
        chmax(dp[i+1][3], dp[i][1]+1);
        chmax(dp[i+1][3], dp[i][0]+1);
      }

      // ■■
      //  ■
      if(s[i]==o && s[i+1]==o && t[i+1]==o){
        chmax(dp[i+1][3], dp[i][2]+1);
        chmax(dp[i+1][3], dp[i][0]+1);
      }

      rep(j,4)chmax(ma,dp[i+1][j]);
    }
    p(ma);
    
    return 0;
}