🦁

# ABC189 D - Logical Expression

2021/01/25に公開

動的計画法

ABC189 D - Logical Expression

問題へのリンク

問題概要

$N$ 個の文字列 $S_1, \dots, S_N$ が与えられる。各文字列は AND または OR である。
値が True または False であるような $N + 1$ 個の変数の組 $(x_0, ..., x_N)$ 出会って、以下のような計算を行った際に、 $y_N$ が True となるようなものの個数を求めよ。

$y_0 = x_0$
$i \geq 1$ のとき、 $S_i$ が AND なら $y_i = y_{i - 1} \land x_i$ 、 $S_i$ が OR なら $y_i = y_{i - 1} \lor x_i$

制約

$1 \leq N \leq 60$
$S_i$ は AND または OR

ABC中の解答

要は $S$ の値によって True と False が並ぶ間に論理積と論理和がずらずらと並んで最終的に True ってなるのは何個ありますか？という問題。
まずはノートでちょこちょこ考えてみた。論理積と論理和は順番を入れ替えてもいい(この理論そもそも間違い？)ので、論理積を左側に論理和を右側に固めると結局論理積の塊は一個でも False だとダメで、一方論理和は一個でも True ならOKと言える。最後、論理積と論理和の塊を OR でまとめると(これ多分 AND でまとめたほうが楽)

論理積の塊 False $\times$ 論理和の塊 False

のとき False になる。よって全体の組み合わせ $2^N$ からその個数を引いてやればいい。
制約が $1 \leq N \leq 60$ なのでこのぐらいならPythonだと計算できる。

論理積が A 個ある時、全体が False になる組み合わせ： $2^A$ - 1
論理和が B 個ある時、全体が False になる組み合わせ：1 (全部 False のときだけ)

よって求める計算式は $2^N - (2^A - 1) \times 1$ となる。

以下のように実装しsampleではACとなったものの提出したらWAとなってしまった。
どこかの理論に穴があったようで、固執してあれこれ考えたけどタイムアップ。

from collections import Counter
N = int(input())
S = Counter([input() for _ in range(N)])
if len(S) == 1:
    key = list(S.keys())[0]
    if key == 'AND':
        print(1)
    else:
        print(2**(N + 1) - 1)
    exit()

v1 = 2**(S['AND'] + 1) - 1
v2 = 2**S['OR'] - 1
ans = 2**(N + 1) - v1 * v2
print(ans)

公式解法1

たまにある解き方の 後ろから考えていくパターン の問題であった。

$S_N =$ 'AND' のとき、 $y_N$ が True になるためには $y_{N-1}$ と $x_N$ は必ず True である必要がある。
$S_N =$ 'OR' のとき、 $y_N$ が True になるためには $x_N$ が True なら $y_{N-1}$ はなんでもよく、 False なら $y_{N-1}$ は True でなければならない。

このルールで後ろから順に一つずつ $x_N$ を処理していく。実装は以下のように非常にスッキリする。
一度こうだと考えてハマったときに別解法を考えるきっかけってみんなどうしているんだろうか？

N = int(input())
S = [input() for _ in range(N)]
ans = 1
for i, s in enumerate(S[::-1]):
    if s == 'OR':
        ans += 2**(N - i)
print(ans)