D - Areas on the Cross-Section Diagram

問題

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/3/ALDS1_3_D

問題文

$1 \times 1$ の格子状にあらわされた地域の模式断面図が与えられるので、地域にできる各水たまりの面積を出力してね。

制約

• $1 \le |S| \le 20000$

サンプル

I/O 1

\\//

4
1 4

\  /
 \/

こんな感じの地形。
1 つだけの水たまりで、面積は 4。

I/O 2

\\///\_/\/\\\\/_/\\///__\\\_\\/_\/_/\

35
5 4 2 1 19 9

    /\_/\/\           __
\  /       \         /  \
 \/         \  _/\  /    \
             \/   \/      \_
                            \  _  _/\
                             \/ \/

5 箇所、合計 35。

考察

まず、各 "$x$ 座標" の "標高" を計測する。これは / なら +1, \ なら -1 として、累積和をとることで計算できる。

あとは標高が同じ所を見つけて、水たまりの面積を計算する。
これは $\sum_{k = l+1}^{r} (h_l - h_k)$ で計算できるっぽい (実験)。
しゃくとりっぽいかんじ。

コード

https://onlinejudge.u-aizu.ac.jp/status/users/a01sa01to/submissions/1/ALDS1_3_D/judge/6764762/C++17

int main() {
  string s;
  cin >> s;
  const int n = s.size();
  vector<int> sum(n + 1, 0);
  rep(i, n) {
    sum[i + 1] = sum[i];
    if (s[i] == '/') sum[i + 1]++;
    if (s[i] == '\\') sum[i + 1]--;
  }
  int minim = *min_element(sum.begin(), sum.end());
  rep(i, n + 1) sum[i] -= minim;
  Debug(sum);
  vector<int> ans;
  for (int i = 0; i < n; i++) {
    int idx = -1;
    for (int j = i + 1; j <= n; j++) {
      if (sum[j] > sum[i]) break;
      if (sum[j] == sum[i]) {
        idx = j;
        break;
      }
    }
    if (idx != -1) {
      int t = 0;
      for (int j = i + 1; j < idx; j++) t += sum[i] - sum[j];
      Debug(i, idx, t);
      if (t != 0) ans.push_back(t);
      i = idx - 1;
    }
  }
  cout << accumulate(ans.begin(), ans.end(), 0) << endl;
  cout << ans.size();
  for (auto x : ans) cout << " " << x;
  cout << endl;
  return 0;
}