ABC415 C - Mixture
https://atcoder.jp/contests/abc415/tasks/abc415_c
コンテスト中の動き
5分でAとBを片付けた後、Cに取り組みました。割とすぐに解法を思いつき、27分で提出。結果は……WAとTLE。少し悩んだ後、D問題を解いてからまた戻ってきました。おかしな点にすぐ気づいてなんとか正解できました。今回も4完できて嬉しいです。
考察
まず問題文が長くて複雑です。しかし、入力例を紙に書きながら頑張って考えて、この問題が何を言いたいのか理解できた頃には解法が頭に自然と浮かんできました。
文字列 S の長さが $2^N - 1 $ であることと、
例えば、 13 を 2 進法で表記すると 1101(2) となるため、状態 13 は薬品 1,3,4 が混ざった状態を表現します。
の記述に助けられました。$ N $ 種類の薬品が入っている／入っていないを管理するなら $2^N$ 通りですよね。各桁の0/1が1種類の薬品を表します。-1 されているのは瓶が空の初期状態は必ず安全だからですね。ということは S の頭に "0" を足してやると管理が楽になります。
さて、1種類ずつ薬品を足していくということは0を1つずつ1に変えていくことに相当します。例えば $N = 4$ の場合なら 0000 -> 0001 -> 1001 -> 1101 -> 1111 みたいに変わっていきますね。「この過程で危険な状態にならないようにせよ」というのがこの問題です。ここまで理解したところで、この遷移をグラフに見立てることを思いつきます。一見グラフに見えないものをグラフに見立てて解くのはよくあるパターンです。今回は使いませんが、これで Union-Find なんかが意外なところで利用されたりしますね。
頂点は 0000, 0001, 0010, 0011, 0100, ...... です。1回の操作でできることは
まだ瓶に注いでいない薬品を 1 種類選択し、瓶に注ぐ。
なので、1に変えられる0は1回の操作につき1個ずつです。ですから 0000 の隣接点は 0001, 0010, 0100, 1000 の4つになります。あとはこの中で無効になる頂点（危険とされる状態）があるのでそこを省き、それ以外の頂点へと辺を張ります。
入力例を例に取ります。コンテスト中にこれを紙に書いて丁寧に確認していました。
N = 4
S = "001110010101110"
なら安全な状態は 0, 1, 2, 6, 7, 9, 11, 15 です。これらが遷移可能な頂点になります。ということで
0 = 0000 から 0001, 0010
1 = 0001 から 0010
2 = 0010 から 0110, 1001
6 = 0110 から 0111
7 = 0111 から 1111
9 = 1001 から 1011
11 = 1011 から 1111
という辺が作れます。これを辿れば 0000 から 1111 までたどり着くことができますね。たどり着けるかどうかは BFS なり DFS なりで確かめられそうです。
計算量
気になるのは計算量ですが、0000 から 1111 への BFS は最悪でも各頂点を 1 回ずつ見ればいいので $2^N$ 回の計算で行えます。$ 2 ^N - 1 の総和 \leq 5 \times 10^5$ という制約より、全てのテストケースについてこのBFSを実行しても計算は間に合いそうです。
実装
bit 演算の基本ですね。
- ループするときは10進数でやる。2進数として扱いたいときは bit 演算を利用するとスムーズ。
- 特定の1桁が 0 になっているのを確かめるにはその桁だけ1にした値をぶつけて AND をとる。
- 特定の1桁の値だけを 0 から 1 にするにはその桁だけ1にした値をぶつけて OR をとる。
それと BFS です。余談ですが僕はデバッグ用 print 文の消し忘れでまず 1 回目のペナルティ、その後に seen のチェックをし忘れていたため 2 回目のペナルティを負いました。「このグラフは一方通行だから戻ってくることもないし別に要らんやろ」と意味不明なことを考えていたんですね。試しに S = "000000000000000" みたいな全部たどれるグラフを作ってみたら探索数が膨れ上がったので間違いに気づきました。先に計算量の見積もりまでやっておいてこの有様…… AC できたからまだよかったものの、もったいないミスでした。
from collections import deque
ans = []
T = int(input())
for _ in range(T):
N = int(input())
S = "0" + input()
G = [[] for _ in range(2**N)]
for i in range(2**N):
if S[i] == "1": continue
for bit in range(N): # どこかのビットを 1 にしたものに遷移できる
if i & (1 << bit) == 0: # 0 になっている桁を見る
next = i | (1 << bit)
if S[next] == "0": # 遷移先も 0 （安全）なら辺を張る
G[i].append(next) # 辺は一方通行（有向辺）
que = deque([0])
seen = [False for _ in range(2**N)]
seen[0] = True
while (que):
v = que.popleft()
for v2 in G[v]:
if seen[v2]: continue # これを忘れると計算量が膨らむ！
seen[v2] = True
que.append(v2)
if seen[2**N-1]:
ans.append("Yes")
else:
ans.append("No")
for an in ans:
print(an)