🐡

【競技プログラミング】AtCoder Beginner Contest 033_C問題

に公開
競技プログラミング
tech

問題

https://atcoder.jp/contests/abc033/tasks/abc033_c

要約

  1. 与えられる数式Sは以下の制約を満たす

    • 演算子は加算(+)と乗算(*)のみで構成される
    • 乗算は加算より優先して計算される
    • 括弧は存在しない
    • 各項は1桁の整数である

  2. 数式の値を0にするために、数式中の数字をいくつか0に書き換える。

  3. 数式の値を0にするために0に書き換えなければならない数字の最小個数を求める。

以下のような数式が条件を満たす

  • 1+340
  • 1+2+3+4+5

以下のような数式は条件を満たさないため、入力として与えられない

  • 12+3+5 (2桁の数字を含む)
  • 467-3 (減算を含む)
  • (3+4)*5+2 (括弧を含む)

既存投稿一覧ページへのリンク

一覧ページ

アプローチ

数式を加算で区切られた項に分割し、各項を個別に評価する。
各項が0になるために必要な最小の書き換え回数を合計することで、全体の数式を0にするための最小の書き換え回数を求める。

解法手順

  1. 入力された数式を"+"で分割し、加算で区切られた項のリストを作成する。

  2. 各項に対して以下の処理を行う
    a. 項を"*"で分割し、乗算で区切られた数字のリストを作成する。
    b. リスト内の全ての数字を掛け合わせる。
    c. 結果が0でない場合、この項を0にするためには少なくとも1つの数字を0に書き換える必要があるため、カウンターを1増やす。

  3. 全ての項の処理が終わったら、カウンターの値を出力する。
    （この値が、数式全体を0にするために必要な最小の書き換え回数となる。）

ACコード

ac.py
def io_func():
    # 標準入力から数式を文字列として受け取る
    return input()

def solve(formula):
    # "+"で分割し、加算で区切られた項のリストを作成
    terms = formula.split("+")
    
    # 書き換え回数を記録するカウンター
    rewrite_count = 0
    
    # 各項に対して処理を行う
    for term in terms:
        # "*"で分割し、乗算で区切られた数字のリストを作成
        numbers = list(map(int, term.split("*")))
        
        # リスト内の全ての数字を掛け合わせる
        product = 1
        for num in numbers:
            product *= num
        
        # 結果が0でない場合、カウンターを1増やす
        if product != 0:
            rewrite_count += 1
    
    # 最小の書き換え回数を返す
    return rewrite_count

# メイン処理
if __name__ == "__main__":
    formula = io_func()  # 入力を受け取る
    result = solve(formula)  # 解を計算
    print(result)  # 結果を出力

###
# formula: 入力された数式を表す文字列
# terms: 加算で区切られた項のリスト
# rewrite_count: 書き換えが必要な回数を記録するカウンター
# numbers: 各項内の数字のリスト
# product: 各項内の数字の積

# 1. io_func関数:
#    - 標準入力から数式を文字列として受け取る
# 2. solve関数:
#    - 入力された数式を"+"で分割し、各項を処理
#    - 各項を"*"で分割し、数字の積を計算
#    - 積が0でない場合、書き換えが必要としてカウンターを増加
#    - 全ての項の処理後、最終的な書き換え回数を返す
# 3. メイン処理:
#    - io_func関数で入力を受け取る
#    - solve関数で解を計算
#    - 結果を出力

Discussion