【競プロ】1日1AC : ABC33 C問題

毎日競プロに触れられるように1日1問（以上）を解き、ブログとしてまとめることにしました。A, B問題だと大体は楽すぎて書く内容が薄くなるのでしばらくはC問題を解いていきます。

今日の問題はこれです。

余裕のある方は是非解いてから続きを読んでください。

提出コードと考えたこと

具体例を考えると、掛け算を先に計算するとSは非負整数の和に整理されるので、その時の0でない項の数が答えになります。（下図を参照）

掛け算の部分を整理した項のデータを持っておくことで答えがわかりそうです。

しかし、これには一つ問題があります。Sの長さがそこそこ長いため、例えば途中に2^100などの大きい数が含まれる入力の場合は、項の数値を保存する際にオーバーフローするので正しい結果が得られません。

積で繋がれている部分を塊と見たときに、その中に0が含まれるならばその値は0ですし、含まれないなら1つの項を0に書き換える必要があります。

すなわち、+に挟まれた部分について、0が含まれるか見ればいいことになります。

以上を踏まえて次のようなコードを書きました。

#include <bits/stdc++.h>
using namespace std;

int main(){
    string S;
    cin >> S;

    int ans = 0;
    bool flag = false;
    for(int i = 0;i < S.size();i++){
        if(S[i] == '+'){
            if(!flag) ans++;
            flag = false;
            continue;
        }
        if(S[i] == '0') flag = true;
    }
    if(!flag) ans++;
    
    cout << ans << endl;
    return 0;
}

これでACを貰えます。Sの末端にある積で繋がれた部分（あるいは1つの項）は、ans++をするかの判定をする前にループが終わってしまうので、それは18行目で行っています。