masuTomo’s blog

競技プログラミングの勉強メモです.主にPythonを使用します.数学の記事も書くかもしれません.

ABC 079 C - Train Ticketを再帰関数で解く

再帰関数と全探索の勉強

問題

atcoder.jp

参考にしたサイト

qiita.com

qiita.com

いずれもこの方のページ。他にもたくさん競プロ向け記事を書いていらっしゃいます。 qiita.com

考察(とりあえず再帰を使ってみる)

全探索と再帰の勉強のための解きなおしなので,頑張って再帰で書くことを目標にした。 再帰関数自体は知っているし,使ったこともあるがいまいちピンと来ていないという自覚があったので,上記参考サイトを読んだ。わかっていたつもりで分かっていなかったことは

  • ベースケースを必ず書いて,そこにreturn処理を必ず入れる

ということだ。いつ再帰処理を終了するか明確にせよ,ということと理解した。たしかに。 今回の場合は,4つの数の足し算と引き算の組み合わせが7になるときを探すのが目的なので,list[0]~list[3]に4つの数を格納しておいて,足すパターンと引くパターンを再帰で実装すればよい。 とりあえず,組み合わせが7になるかどうかを求めるコードを先に書いてみた。

#iはlistのindex, xは計算結果を格納
def func(i,x):
    #ベースケース
    if i == 4:
        if x == 7: return True
        else: return False

    #足す場合
   if  func(i+1, x + int(S[i])) : return True 

    #引く場合
    if func(i+1, x - int(S[i])): return True

    return False

これを

S = input()
func(1,S[0]):

として,呼び出せばうまい組み合わせで7が作れるときはTrue,できないときはFalseが返却される。

考察2(問題に合うように少し書き換える)

今回の問題は,どのような計算で7になるかという式も出力しなくてはならない。内部的には計算しているわけだが,どのような演算により7を得たのかは保持していないので,それを取得しないといけない。

ここに地味に苦労した。yeildを使ってその都度,演算子を返却しようかとも考えたが,再帰の最後まで処理をすすめてTrueのときにしか返却する必要はないし,,,,という感じで少しさまよった。 結局,1つ1つの計算をするときの演算子を文字列として渡すことにして,最後まで行ったらその演算子が格納された文字列を返却することにした。

こんな感じ。

#引数としてopを追加
#opには計算で用いた演算子が文字列として格納されている
def func(i,x,op):
    #ベースケース
    if i == 4:
        if x == 7: return op
        else: return ""

    #足す場合
    opP = func(i+1, x + int(S[i]), op+"+")
    if opP != "": return opP

    #引く場合
    opM = func(i+1, x - int(S[i]), op+"-")
    if opM != "": return opM

    return ""

こうすることで,最終的に返却された文字列が空文字列なら7にできない,そうでないなら7にでき,しかも演算子情報もあるので,それを合わせて出力してやればよい。

なんかもっとスマートな書き方がある気がするが,とりあえずこれで良しとする。

おまけ

ちなみに,AtCoder上に提出された他の方のコードも見せてもらったが,多くの方がitertools.product

itertools --- 効率的なループ実行のためのイテレータ生成関数 — Python 3.8.1rc1 ドキュメント

を使用していました。