D - Areas on the Cross-Section Diagram

cpaojalds1

最終更新日

Table of Contents

Loading...

問題

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/3/ALDS1_3_D (新しいタブで開く)

問題文

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

制約

サンプル

I/O 1

\\//
4 1 4
\ / \/

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

I/O 2

\\///\_/\/\\\\/_/\\///__\\\_\\/_\/_/\
35 5 4 2 1 19 9
/\_/\/\ __ \ / \ / \ \/ \ _/\ / \ \/ \/ \_ \ _ _/\ \/ \/

5 箇所、合計 35。

考察

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

あとは標高が同じ所を見つけて、水たまりの面積を計算する。
これは k=l+1r(hlhk)\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; }