Aizu Online Judge（AOJ）が提供している「アルゴリズムとデータ構造入門」（ALDS1）の3_D問題をC++で解いてみました。
ALDS1では、「アルゴリズムとデータ構造の基礎を体得します。」とあります。トピック#3「基本データ構造」では、スタック、キュー、リストを学びます。
問題（3_D: Areas on the Cross-Section Diagram）
問題はリンク先をご覧ください。
AOJ ALDS1 3_D問題: Areas on the Cross-Section Diagram
スタックを用いる応用問題を紹介します。
リストについて
トピック#3の問題として、応用問題を解いてみます。
問題で、以下の地形が与えられます。その地形から水たまりの面積を求めていきます（画像は、問題から借用しました）。
問題 3_A で学んだスタックを使って解きます。
C++ プログラム例（ALDS1 3_D）
水たまりの総面積を変数 sum で、各水たまりの量を配列 result に格納します。スタックは以下の2つを用意します。
- スタック pos は、右下がりの位置をpushしておきます。右上がりを検出した場合、スタックの値を取得します。その結果である (右下がりの位置, 右上がりの位置) をスタックlayerにpushします（14ー23行目）。
- スタック layer は、水たまりを各高さの行で分割した組がpushされています。スタックの値を、同じ水たまりに含まれている場合は続けて読み出し、その水たまりの量を求めることができます。結果を result に格納します（27ー41行目）。
配列 result は、右から格納していくため、逆に出力しています（45行目）。
以下が、最終的なC++プログラムとなります。
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
int main()
{
string s;
cin >> s;
stack<int> pos;
stack<pair<int, int>> layer;
for (int i = 0; i < s.length(); ++i) {
if (s[i] == '\\') {
pos.push(i);
} else if (s[i] == '/') {
if (!pos.empty()) {
layer.push(make_pair(pos.top(), i));
pos.pop();
}
}
}
int sum = 0;
vector<int> result;
while (!layer.empty()) {
pair<int, int> this_layer = layer.top();
layer.pop();
int left = this_layer.first;
int this_sum = 0;
sum += this_layer.second - left;
this_sum += this_layer.second - left;
while (!layer.empty()&&(left < layer.top().first)) {
pair<int, int> next_layer = layer.top();
layer.pop();
sum += next_layer.second - next_layer.first;
this_sum += next_layer.second - next_layer.first;
}
result.push_back(this_sum);
}
cout << sum << endl;
cout << result.size();
for (int i = result.size() - 1; i >= 0; --i) {
cout << " " << result[i];
}
cout << endl;
return 0;
}上記プログラムは、AOJ で「AC（Accepted＝正解）」と判定されました。
最後に
スタックを2個使うことによって、問題を解くことができました。実装も多めだと思います。
引き続き、ALDS1 の問題を紹介していきます。
