ABC 033 | C - 数式の書き換え

問題

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

考えたこと

初見では各項を0か元の数字かをbit全探索で行えば解けると思ったが$S \leq 10^5$なので間に合わない。

問題文を読むとすべて1桁の整数なのでマイナスはない。よって以下のように乗算を計算し終わったあとに項があって$0$でなければ$0$に書き換える必要があるのでその数を数えればいい。

コード

実装時のTips

• 乗算時にオーバーフローすることを考慮して1以上なら1として扱っている。

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;

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

  vector<ll> stack;
  stack.push_back(s[0] - '0');
  for (int i = 1; i < s.size(); i += 2) {  // 演算子をチェックする
    if (s[i] == '+') {
      stack.push_back(s[i + 1] - '0');
    } else {  // *
      ll v = stack.back();
      v = v > 0 ? 1 : 0;  // オーバーフローを防ぐ
      stack.pop_back();
      stack.push_back(v * (s[i + 1] - '0'));
    }
  }
  // stackを回収
  ll ans = 0;
  for (int i = 0; i < stack.size(); i++) {
    if (stack[i] != 0) {
      ans++;
    }
  }
  cout << ans << endl;
}

その他の解き方

足し算で文字列を分割して各文字列に0があるかどうかでも導ける。

参考

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