ALDS1_3_D:

この問題の解法として、ソートアルゴリズムを応用するなど、いくつかのアルゴリズムが考えられますが、ここではスタックを用いたアルゴリズムを考えてみましょう。

まず、全体の総合面積（最初の出力）は次のようなアルゴリズムで求めることができます。

入力された文字 $s_i$ を順番に調べ

• \ ならば、その位置（先頭から何文字目か）を表す整数 $i$ をスタック $S1$ に積む。
• / ならば、スタック $S1$ のトップから対応する \ の位置 $i_p$ を取り出し現在の位置との距離 $i − i_p$ を総面積に加算する。

文字 _ は \ と / の組の距離を１つ増やすだけなので、$s_i$ が_の場合、特に処理は必要ありません。

次に、各水たまりの面積を求めるアルゴリズムを考えてみましょう。

各水たまりの面積はもう１つのスタック $S2$ を用いて保存していきます。スタック $S2$ には、（その水たまりの最も左の \ の位置、その水たまりのその時点での面積）の組を積んでいきます。たとえば、次の図の局面では、$i$ を現在の / を示す位置、$j$ をそれに対応する \ の位置とすると、$S2$ に は $(j + 1, 5)$ と $( k, 4)$ の２つの水たまりが積まれています。

ここで、新たにできる水たまりの面積は、$S2$ に積まれている $j$ より右側にある水たまりの面積の総和と、新しくできる面積 $i − j$ の和になります。ここで参照された（複数の）水たまりを $S2$ から取り出し、新しくできた水たまりを $S2$ に積みます。

Reference

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 (マイナビ) AIZU ONLINE JUDGE のコース問題を題材にした解説書です。初級者が体系的にアルゴリズムとデータ構造の基礎を学ぶことができる入門書となっています。