競プロ典型90問★3コード解説 002 - Encyclopedia of Parentheses

はじめに

今回から競プロ典型90問の★3問題に挑戦していきたいと思います。★2よりもかなりアルゴリズムが複雑になるので、しっかり解説していきたいと思います。
ですので、★2問題の時は毎日2問解説していましたが、これからは毎日1問ずつ解説していきます。丁寧に解説するためです！決して文字数が多くなって面倒くさいわけではないです。

競プロ典型90問

atcoder.jp

002 - Encyclopedia of Parentheses（★3）

002 - Encyclopedia of Parentheses（★3）

問題文だけ見るとわかりにくいですが、例を見てみるとわかりやすいですね。つまりかっこが破綻しないように(と)を、長さがNになるように配置していくという問題です。

この問題で注目したい点は2点あり、 - 文字が(と)の2通り - 文字列の長さが最大20

です。このように選択肢が2通りで探索範囲が狭い場合は、
bit全探索 という手法を用いるとうまくいくことが多いです。

bit全探索とは

bit全探索とは、考えられる範囲の0と1の組み合わせをすべてに対して操作を行うアルゴリズムです。探索する範囲は、Nの最大値が20なので 2²⁰ = 1048576であり、そこまで大きな数字ではありません。（Pythonが1秒間に1億回計算できると言われています。）
今回の問題では(を1に、)を0に対応させます。
以下の流れで問題を解いていきます。

1. あるN桁の2進数について、前から0, 1の数を数える。
2. 0の数が1の数を超えたらその2進数は除外（()が破綻しないためには、)が(より先に多く出現してはならない。）
3. 0の数と1の数が等しければ解答に加える。
4. 上記をN桁の自然数すべてに行う。

コードを見ながら詳しく解説していきます。

実装

n = int(input())
ans = []
for i in range(2**n):
    sample = bin(i)
    sample = sample[2:]

    cnt1 = 0
    cnt0 = 0

    if len(sample) == n:
        for j in range(n):
            if sample[j] == "1":
                cnt1 += 1
            else:
                cnt0 += 1
            if cnt1 < cnt0:
                break
        if cnt1 == cnt0:
            sample = sample.replace("1", "(")
            sample = sample.replace("0", ")")
            ans.append(sample)
print(*ans, sep="\n")

0から2^Nまでのすべての整数に対して、2進数にします。整数を2進数にするにはbin()が便利で、0b1001のような形式（str型）で返してくれます。2進数の部分は前の2文字を除外したものになります。

ループ内において、桁数がNの2進数においてのみ、前から0と1の出現回数をカウントします。ここで、0が1の個数を超えると処理を終了させています。処理終了時に0と1の数が等しければ()が破綻しないと考えることができます。

そして0と1を()に置き換えれば処理が終了です。

お疲れさまでした。

おわりに

今回は bit全探索を使って競プロ典型90問の002を解いていきました。★2に比べてかなり難易度は上がっていると感じています。
またbit全探索ですが、2進数のシフトと論理和を用いて行う方法もあるようですね。そちらの方法も面白そうなので今度調べたいと思います。