ABC415のC問題Mixture

2025-07-24

日本レジストリサービス（JPRS）プログラミングコンテスト2025#2（AtCoder Beginner Contest 415）に参加しましたが、当日回答できなかったC問題 Mixtureに改めて挑戦しました。

C - Mixture

N種類の試薬がある。これを任意の順番で１種類ずつ混ぜて、最終的に全ての試薬を混合できるか判定する問題。ただし、混合物の組み合わせによっては危険な状態があり、この状態をとることができない。

危険な常態化は、それぞれの組み合わせが安全か危険かを01で表す\(2^N-1\)桁の危険性を示す数列が与えられる。例えば3種類の試薬があり、この内1と3を混合したときの状態は、0b101 = 5となり危険性を示す数列の5番目を確認すると危険・安全を判定できる。

考え方

試薬\(1,2, \cdots N\)を\(2^{1-1}, 2^{2-1}, \cdots 2^{N-1}\)と表せば、混合の状態をN bitで管理でき、危険な状態かも判定しやすくなる。

そして、空の状態0b0に1bitずつセットして行き、最終的に全てのビットをセットして\(2^N-1\)にできたらOKとなる。

具体的には、次の操作を全ての試薬が混合されるまで行います。

まず0b0の任意の1bitを選んで1にする。
危険な状態でないか確認する。
危険でなかったら、混合されていない試薬、すなわち0となっているbitを1つ選んで1にする。
2に戻る。

また混合状態0b001と0b100どちらも、混合状態0b101を取ります。そこで、混合されている試薬の種類数毎にまとめて処理することで、重複して調べる無駄を省きます。他には調べた状態をメモしておく方法もありますが、状態数が膨大なのでメモリー不足になる可能性を考え採用しませんでした。

技術的工夫

混合していない試薬を見つけるためには、混合状態を表すbit列から0となっているbitを見つける必要があります。

しかし、その方法が思い浮かばなかったので、とりあえず混合状態を表すbit列の全桁に対してビット演算ORで1をセットして、元の値と変わっていたらbitを0→1に変化させた、すなわち新しい試薬を混合させた判断しました。

T = int(input())

for _ in range(T):
    N = int(input())
    S = input()

    ALL_MIXED = 2**N - 1
    if S[ALL_MIXED - 1] == "1":
        print("No")
        continue

    solutions = [2**i for i in range(N)]

    state = solutions
    while len(state) > 0:
        if ALL_MIXED in state:
            # already checked safe
            print("Yes")
            break

        next_state = set()
        for s in state:
            # check the state is safe
            if S[s - 1] != "1":
                # add solutions
                for t in solutions:
                    # 1 + 1 should 1 => use bit OR
                    u = s | t
                    if u != s:
                        # added new solution
                        next_state.add(u)
        state = next_state
    else:
        print("No")