ebisukeプログラミング初心者脱出黙示録

30歳を過ぎてから始めたプログラミングと競プロの記録。Pythonで取り組んでいます。Arduinoで電子工作も

AtCoder-ABC189 D - Logical Expression【Python解答例】

AtCoder Beginner Contest189の復習としてD問題の解答例を記事にします。
AtCoder Beginner Contest 189 - AtCoder


AtCoder Beginner Contest189 D - Logical Expression

D - Logical Expression

問題文

N 個の文字列 S_{1},…,S_{n} が与えられます。各文字列は AND または OR です。
値が True または False であるような N+1 個の変数の組 (x_{0},…,x_{N}) であって、 以下のような計算を行った際に、y_{N} が True となるようなものの個数を求めてください。
y_{0}=x_{0}
・i≥1 のとき、Si が AND なら y_{i}=y_{i-1}x_{i}S_{i} が OR なら y_{i}=y_{i-1}x_{i}
a∧b は a と b の論理積を表し、a∨b は a と b の論理和を表します。

制約

・1≤N≤60
・Si は AND または OR

解答例

n = int(input())

t_num = 1 # i = 0のときtrueになるのはx0 = trueの1通り

for i in range(n):
    s = input()
    if s == "OR":
        t_num += 2 ** (i+1) 
#    else:  # ANDのときはt_numの数に変化なし
#        t_num = t_num
else:
    print(t_num)

解説

N個のandかorの文字列Sが与えられます。
N+1個の任意の変数の組(x0,x1,...,xn)とSの計算結果が(y0,y1,...,yn)になり、ynがtrueとなるxの組み合わせ数を解答する問題です。


i番目のyiがtrueとなる数をt_numと置いて、i =0 からNまでのループで組み合わせの数がどうなるか考えていきました。

Siがorのときは次の2通り考えられます。
・xi=Trueならi以前の結果に関係なく、yi=Trueです。
なのでyi=Trueとなるxの組み合わせは2のi+1条通りあります。

・xi=Falseのときは、y(i-1)=Trueでなければならないです。
よってyi=Trueとなるxの組み合わせはy(i-1)と同じ数です。

Siがorの場合は上記2つの組み合わせの合計なので、t_num += 2 ** (i+1) = 2 ** (i+1) + t_num です。
orの場合の 2 ** (i+1)とandの場合のt_numを足しています。


Siがandのときはxi = true かつ y(i-1) = true の条件のときのみyi = trueになります。
組み合わせの数もi-1番目のときと同じになるのでt_numは変化しません。
コメントアウトしている
# else: # ANDのときはt_numの数に変化なし
# t_num = t_num
の部分はandのときはt_numが変わらないことの説明のために書いてあるだけですので、もちろんなくてかまいません。


このループを抜けた後にt_numを出力すれば求める解答となります。



公式解説をはじめとした他の方々から勉強させてもらって理解することができました。

コンテスト中に思いつくのが難しいですが、地道に学習を続けて力をつけていきたいです。



ABC189の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com