C - Mixture
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
Atcoder Liveの方で聞いた解説が一番理解できました
個人的には以下の図で考えるのが一番わかりやすいかなと思っていて、状態0から薬品を混ぜて遷移できる状態を深さ優先探索のような形で辿っていきます
この時にすでに到達していた場合や、S（瓶の中で混ぜられた薬品の状態が安全か危険かを表す）と比較して危険な状態の場合はスキップします
また、すでに混ぜた薬品を混ぜることはしたくないです。これの判定方法としてビット論理和を使います。
例えば：
011<-状態3（薬品2と薬品1）
001<-薬品1
------ ビット論理和の結果⇩
011<-薬品1を混ぜた結果が状態3と同じ上記のように論理和をとったときに元の状態と同じになれば、薬品はすでに混ぜられていることになります
pythonでは以下のように|を使って書きます
print(3 | 1) # 3（011)最終的に上記の図で全て薬品を混ぜた状態（上記の図では状態7）に到達すればYes、そうでなければNoを出力します
以下のコードでACできました
def i_map():
return map(int, input().split())
def i_list():
return list(map(int, input().split()))
t = int(input())
for i in range(t):
n = int(input())
s = list(input())
s.insert(0, "0")
st = [0]
visited = [False] * len(s)
visited[0] = True
while st:
x = st.pop()
visited[x] = True
for j in range(n):
y = x | 1 << j
if y == x:
continue
if visited[y]:
continue
if s[y] == "1":
continue
st.append(y)
if visited[-1]:
print("Yes")
else:
print("No")
コメント