atcoder abc189 D - Logical Expression

AtCoder DP

問題

D - Logical Expression

解法

DPを使った解法。入力例1で考えてみる。

2
AND
OR

以下のDP配列を定義する。

dp[n][x]:= n個までの文字列で結果がx(0/1)になるケースの数

n = 0

true / false それぞれ1通りのみ

  • dp[0][0] = 1
  • dp[0][1] = 1

n = 1

AND(積集合)

  • dp[1][0] = dp[0][0] + dp[0][0] + dp[0][1]
    • 0になるケースは 00, 01, 10 の3通り
  • dp[1][1] = dp[0][1]
    • 結果が1になるケースは 11 の1通り

n = 2

OR(和集合)

  • dp[2][0] = dp[1][0]
    • 0になるケースは 00 の1通り
  • dp[2][1] = dp[1][0] + dp[1][1] + dp[1][1]
    • 1になるケースは 01, 10, 11 の3通り

DPテーブル

x/n 0 1
0 1 1
1 3 1
2 3 5 
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
using ll = long long;

int n;
vector<string> s;
ll dp[65][2]; // dp[n][x]:= n個までの文字列で結果がx(0/1)になるケースの数

void solve() {
  dp[0][0]=1; // dp[0][0]の場合は false のみで1通り
  dp[0][1]=1; // true のみで1通り

  REP(i,n) {
    // jの状態にｋを追加する
    // 4通りの組み合わせ: 00,01,10,11
    REP(j,2) REP(k,2) {
      if (s[i] == "AND") {
        // ANDは論理積 j&k
        dp[i+1][j&k] += dp[i][j];
      } else {
        // ORは論理和 j|k
        dp[i+1][j|k] += dp[i][j];
      }
    }
  }

  // n個の文字列で結果が1になるケースの数
  cout << dp[n][1] << endl;
}

int main() {
  cin >> n;
  s.resize(n);
  REP(i,n) cin >> s[i];

  solve();
  return 0;
}