早稲田卒のAI研究者のブログ

データサイエンス、機械学習、競技プログラミング、音楽、勉強

【bit全探索】ABC079 C - Train TicketをPythonで解いてみた

atcoder.jp


今日はbit全探索です。
ちなみに苦手です。
bit処理って普段の業務で絶対使わなくないですか??
慣れる機会がないんですよね。
しかし、そろそろアルゴリズムにしっかり取り組む時期だと思うので、練習がてら解いていきます。

思考の過程

電車の切符でよくやるやつですね。
今はほとんどSuicaやPasmoなどになってしまって、切符自体を見る機会もなくなってきましたね。
今の中学生とかはこの遊びを知っているんでしょうか。
……まだまだ自分は若いと思いこんでいるので、そういうのは考えたくないですね。考えません。


さて、話を戻します。
そもそもbit全探索は、

「n 個の選択肢それぞれに Yes or No の二択があるが、その部分集合(選択できるパターン)の全てを網羅的にチェックしたい」

引用:
Python de アルゴリズム(bit全探索) - Qiita

ときに用います。
この問題では、数字と数字の間に、+ or -の二択を選択するので、bit全探索で解けそうですね。

実装の方針としては、あらかじめ"-"のリスト作成しておき、bit全探索で2進数表示で1の箇所を "+" で上書きしていく、ということにします。

コード実装

プログラムの流れは以下のようにする。
1. スキマの数を計算
2. +, -の組み合わせの数だけ、for文でbit全探索
3. 2進数表示で1の箇所を "+" で上書き
4. 更新したリストを用いて方程式作成
5. 数値に戻し、等式を満たせば出力

s = input()
n = len(s) - 1  # スキマの数を計算
for i in range(2**n):  # +, -の組み合わせの数だけ、for文でbit全探索
    p_or_m = ["-"] * n
    for j in range(n):
        if ((i >> j) & 1) == 1:  # 2進数表示で1の箇所を "+" で上書き
            p_or_m[n - 1 - j] = "+"

    formula = ""
    for k in range(n):  # 更新したリストを用いて方程式作成
        formula += s[k] + p_or_m[k]
    formula += s[3]
    if eval(formula) == 7:  # 数値に戻し、等式を満たせば出力
        print(formula+"=7")
        break


無事ACでした!
しかし、まだまだ慣れない。。
また直近でbit全探索の問題を解こうと思います。