蟻本 §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で解いていきたいと思います。では,まずは入力例1の遷移図を書いていきましょう。
まず 1222 の1から始めて,次に1+2と1-2で2通りに分かれます。下の図では幅の関係上,上下にその2通りを分割して遷移図を書いています。

以上のように,2^3 = 8 通りの遷移図を見ることで,1+2+2+2=7を得ることができました。
ということで,ここでは i (遷移の回数,0~3)f (その時点の文字列)s (その時点での計算の結果)の3変数を用いて DFS を書いていくと分かりやすいコードを書けると思います。先ほどの1+2+2+2=7の例でこれの遷移を考えてみます。

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

あとはこれを実装します。毎回の分岐で + か – かを考えるので,2通りの分岐を行います。
+ の時は,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であれば,その数式に =7 を加えたものを返します。そして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 のフォロー,リツイートなどよろしくお願いします。
それでは!

他の蟻本系統の問題も解説していますので,こちらも是非ご覧ください。
AtCoder 版!蟻本 (初級編)を参考にさせていただいております。

蟻本 §2-2-1 部分和問題
ARC 061 C – たくさんの数式
ABC 079 C – Train Ticket