蟻本 §2-1-1 部分和問題 ABC 079 C を Python で AtCoder Beginner Contest 079 C

蟻本 §2-1-1 部分和問題類題「ARC 061 C – Train Ticket」を Python で解説していきたいと思います。
類題はもう競プロ界隈ではおなじみとなっている，こちらのAtCoder 版！蟻本 (初級編)から参照させていただきました。
蟻本 §2-1-1 部分和問題の Python でのコードはこちらで解説しています。
それでは，まずは問題文から。
https://atcoder.jp/contests/abc079/tasks/abc079_c

C – Train Ticket

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 300 点

問題文

駅の待合室に座っているjoisinoお姉ちゃんは、切符を眺めています。

切符には 4 つの 0 以上 9 以下の整数 A,B,C,D が整理番号としてこの順に書かれています。

A op1 B op2 C op3 D = 7 となるように、op1,op2,op3 に + か - を入れて式を作って下さい。

なお、答えが存在しない入力は与えられず、また答えが複数存在する場合はどれを出力してもよいものとします。

制約

0≦A,B,C,D≦9
入力は整数からなる
答えが存在しない入力は与えられない

入力

入力は以下の形式で標準入力から与えられる。

ABCD

出力

作った式を、=7 の部分を含めて出力せよ。

ただし、記号は半角で出力せよ。

また、数字と記号の間に空白を入れてはならない。

入力例 1

1222

出力例 1

1+2+2+2=7

1+2+2+2=7 が条件を満たします。

入力例 2

0290

出力例 2

0-2+9+0=7

この他に、0−2+9−0=7 が条件を満たします。

入力例 3

3242

出力例 3

3+2+4-2=7

解説

他のもっと簡単な解き方でも解けますが，今は深さ優先探索（DFS）がテーマなので，DFSで解いていきたいと思います。
まず 1222 の１から始めて，次に１＋２と１－２で２通りに分かれます。2^3 = 8 通りの遷移図を見ることで，１＋２＋２＋２＝７を得ることができました。
ということで，ここでは i (遷移の回数，０～３），f (その時点の文字列），s (その時点での計算の結果）の３変数を用いて DFS を書いていくと分かりやすいコードを書けると思います。先ほどの１＋２＋２＋２＝７の例でこれの遷移を考えてみます。

(i, f, s) = (0, “1", 1)
(i, f, s) = (1, “1+2", 3)
(i, f, s) = (2, “1+2+2", 5)
(i, f, s) = (3, “1+2+2+2", 7)

あとはこれを実装します。毎回の分岐で + か – かを考えるので，２通りの分岐を行います。
+ の時は，f_i+1 = f_i + “+" + n[i+1]，s_i+1 = s_i + int(n[i+1]) とします。
ーの時は，f_i+1 = f_i + “-" + n[i+1]，s_i+1 = s_i – int(n[i+1]) とします。

最終的に i が 3 になった時，s （計算結果）が７であれば，その数式に =7 を加えたものを返します。そして７でなければ何も返さないように，return ' ' とします。もしこれを書かないと，i = 3 の時に s = 7 でなければ操作が終わらないということになって，i = 4 の場合に飛んでしまい，エラーを起こしてしまいます。
それでは，以下に解答例を載せておきます。

解答例

n = input()

def dfs(i, f, s):
    if i == 3:
        return f+"=7" if s == 7 else ''
    return dfs(i+1, f+"+"+n[i+1], s+int(n[i+1])) or dfs(i+1, f+"-"+n[i+1], s-int(n[i+1]))

print(dfs(0, n[0], int(n[0])))

いかがだったでしょうか。
もしよろしければ twitter のフォロー，リツイートなどよろしくお願いします。
それでは！

他の蟻本系統の問題も解説していますので，こちらも是非ご覧ください。

タムログ

プログラミングについての情報発信をしていきます！