[AtCoder] ABC 189 D – Logical Expression

2021年2月16日

問題

方針

変数の組 \( (x_0, \cdots, x_N) \) について以下の式が成り立ちます。

\[ x_0 \ \mathrm{S_1} \ x_1 \ \mathrm{S_2} \ x_2 \cdots \ x_{N – 1} \ \mathrm{S_N} \ x_N = 1\]

ここで、\( d(i, 0) \) を \( x_0 \ \mathrm{S_1} \ x_1 \cdots \ x_{i – 1} \ \mathrm{S_i} \ x_i = 0 \) となる \( (x_0, x_1, \cdots, x_i)\) の組の数とし、\( d(i, 1) \) を \( x_0 \ \mathrm{S_1} \ x_1 \cdots \ x_{i – 1} \ \mathrm{S_i} \ x_i = 1 \) となる \( (x_0, x_1, \cdots, x_i)\) の組の数とします。初期値は、\( d(0, 0) = 1 \wedge d(0, 1) = 1 \) です。遷移式は、

• \( S_i = \) AND のとき

\[\begin{eqnarray}
d(i + 1, 0) &=& 2d(i, 0) + d(i, 1) \\
d(i + 1, 1) &=& d(i, 1)
\end{eqnarray}\]

• \( S_i = \) OR のとき

\[\begin{eqnarray}
d(i + 1, 0) &=& d(i, 0)\\
d(i + 1, 1) &=& d(i, 0) + 2d(i, 1)
\end{eqnarray}\]

となります。したがって、\( d(N, 1) \) が答えとなります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int N;
    cin >> N;
    string S[N];
    for (int i = 0; i < N; i++) {
        cin >> S[i];
    }
    ll d[N + 1][2] = {};
    d[0][0] = 1;
    d[0][1] = 1;
    for (int i = 0; i < N; i++) {
        if (S[i] == "AND") {
            d[i + 1][0] = 2 * d[i][0] + d[i][1];
            d[i + 1][1] = d[i][1];
        } else {
            d[i + 1][0] = d[i][0];
            d[i + 1][1] = d[i][0] + 2 * d[i][1];
        }
    }
    cout << d[N][1] << "\n";
    return 0;
}