問題
https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/3/ALDS1_3_D (新しいタブで開く)
問題文
の格子状にあらわされた地域の模式断面図が与えられるので、地域にできる各水たまりの面積を出力してね。
制約
サンプル
I/O 1
\\//
4
1 4
\ /
\/
こんな感じの地形。
1 つだけの水たまりで、面積は 4。
I/O 2
\\///\_/\/\\\\/_/\\///__\\\_\\/_\/_/\
35
5 4 2 1 19 9
/\_/\/\ __
\ / \ / \
\/ \ _/\ / \
\/ \/ \_
\ _ _/\
\/ \/
5 箇所、合計 35。
考察
まず、各 " 座標" の "標高" を計測する。これは / なら +1, \ なら -1 として、累積和をとることで計算できる。
あとは標高が同じ所を見つけて、水たまりの面積を計算する。
これは で計算できるっぽい (実験)。
しゃくとりっぽいかんじ。
コード
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;
}