No Caffeine, No Life

プログラミング(主にPython)

Aizu Online Judge: 面積計算

模式断面図の面積 | アルゴリズムとデータ構造 | Aizu Online Judge

この問題はやや難しい、と『 プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 』に書いてある。確かに、ちょっと考えにくい、というか、キューやスタックがよくわかっていないと書きづらいと思う。

この本に書いてあるように、スタックを用いたプログラムが考えやすい。

 

  • s1: 下り坂を示す'\'の位置を表すスタック
  • s2: 各水たまりの位置と面積を表すスタック ([ , ]で表される)
  • '\'と'/'の位置の差がそのまま面積になることに気づく。
  • 各水たまりは、まとめることができる場合がある。