mitsu's techlog

通信ネットワークの研究してる大学院生です。備忘録も兼ねて技術系の話を適当に

Areas on the Cross-Section Diagram 解き方メモ

模式断面図の面積 | アルゴリズムとデータ構造 | Aizu Online Judgeを解く時に苦労したのでそのメモφ(・

問題

模式断面図の面積 | アルゴリズムとデータ構造 | Aizu Online Judgeに書いてある通りです、ってのも素っ気ないので以下にスクショ貼ります。

f:id:mtdtx9:20170424200941p:plain

図のような状況において、水たまりそれぞれの面積と全体の面積を出すという問題です。

入力として\_/の列を受け取り、出力は全総面積、水たまりの数、各水たまりの面積になります。

上の図に対応する入力、出力は以下のようになります。 出力は総面積が35、水たまりの数が5、各水たまりの面積が4 2 1 19 9となっていることを示しています。

f:id:mtdtx9:20170424201033p:plain

考え方

最初自力で考えてたんですが、全くわからなかったのでALDS1_3_D: Areas on the Cross-Section Diagram - State-of-the-Arsのコードを参考にしながら考えていきました。

コードを読んで参考になった考え方は、

  • \の場所をスタックに保存することで、/を受け取った時にそれと対応する\を見つけることができる
  • 上記の方法で、対応する\/を用いて面積を計算すること = 横向きに面積を計算していくということ

アルゴリズムとしては、

  • 入力が\のときはそのインデックスをスタックに保存する
  • 入力が/の時はスタックからpopし、現在のインデックスと組み合わせて横向きに面積を計算する
  • 計算した面積の総和をとって総面積を計算する

といった感じです。

ただ、これだけでは各水たまりの面積を計算できないので、

  • /の時にpopしたインデックスと計算した面積のタプルを保存する
  • 必要に応じて上記のタプルを結合していく(水たまりを結合する操作に相当)

ということもします。

以上のために2つのスタックを用意します。

  1. \のインデックスを保存するスタック
  2. popしたインデックスと計算した面積のタプルを保存するスタック

これだけだと意味不明なので例を出しながら説明します。

具体例で説明

具体例として、先ほどの問題の水たまりが1, 19となっている箇所を用いて説明します。

ちなみに入力は\/\\\\/_/\\///となります。 今後はこの入力をインデックスと合わせて説明するので、簡単な表を書いておきます。

index 0 1 2 3 4 5 6 7 8 9 10 11 12 13
value \ / \ \ \ \ / _ / \ \ / / /

index = 0

\なのでスタック1にインデックスを保存します。

stack stack2
0

index = 1

/なのでスタック1からpopします。

面積 = (現在のindex) - (popしたindex) = 1 - 0 = 1となります。 popしたインデックスとこの計算結果をスタック2に保存します。

stack stack2
(0, 1)

index = 2 ~ 5

\らをスタック1に積んでいきます。

stack stack2
5
4
3
2 (0, 1)

index = 6

/なのでスタック1からpopします。

面積 = 6 - 5 = 1となります。

popしたindexの5は、スタック2に保存したタプルに入っているindexである0より大きいので、そのままスタック2に保存します。

stack stack2
4
3 (5, 1)
2 (0, 1)

スタック2が水たまりの様子を表しているので、これは面積1の水たまりが2つあることを示しています。 実際にここまで読み込んだ時の様子は以下のようになっています。

f:id:mtdtx9:20170424225147j:plain:w300

index = 7, 8

index = 7のとき_なので特に何もしません。 index = 8のとき/なので、スタック1からpopします。

面積 = 8 - 4 = 4となります。

popしたindexである4はスタック2に積まれているタプルに保存されたindexである5より小さいので、水たまりは結合されます。 したがって、popしたindexである4と面積 = (タプルに保存されていた面積である) + (先ほど計算した面積) = 1 + 4 = 5を合わせて保存します。 この時のスタックの状態は以下のようになります。

stack stack2
3 (4, 5)
2 (0, 1)

f:id:mtdtx9:20170424225138j:plain:w300

index = 9, 10

ちょっと面倒になってきたのでスタックの状態だけ、、

stack stack2
10
9
3 (4, 5)
2 (0, 1)

index = 11

stack stack2
9 (10, 1)
3 (4, 5)
2 (0, 1)

index = 12

stack stack2
(9, 4)
3 (4, 5)
2 (0, 1)

この時の状態はこんな感じ。

f:id:mtdtx9:20170424225915j:plain:w300

index = 13

/なのでスタック1から3をpopする。

面積 = 13 - 3 = 10となる。

popしたindexである3に対して、スタック2にある(4, 5), (9, 4)はindexの値が大きいのでこれらを結合する。

stack stack2
(3, 19)
2 (0, 1)

図的にはこんな感じ。

f:id:mtdtx9:20170424230620j:plain:w300

結果

スタックの状態は以下のとおり。

したがって、スタック2を見ると、面積1の水たまりと、面積19の水たまりがあることがわかる。

stack stack2
(3, 19)
2 (0, 1)

コード

rubyで書きました。

コードは以下の通り。まだ最適化できそうやけどとりあえずはこれで解けます。

sum = 0
stack = [] # \を受け取ったindexのstack
res = [] # /に対応する\のindexとその時に計算した面積のtupleのstack. 最後に各断面の面積として表示する
gets.split("").each_with_index { |v, i|
  if v == "\\"
    stack << i
  elsif v == "/"
    j = stack.pop
    if !j.nil? # \より先に/が来たときのため
      a = i - j # indexの引き算で横向きに計算する
      sum += a

      loop do
        k, b = res.pop
        if !k.nil?
          if j < k
            a += b
          else
            res << [k, b] # 一旦popしてるので特に何もなければ再度pushして戻す
            break
          end
        else
          break
        end
      end
      res << [j, a]
    end
  end
}
puts sum
if res.size() == 0
  puts "0"
else
  puts "#{res.size()} #{res.map{|n| n[1]}.join(" ")}" # size == 0の時にmapがうまくいかない??
end

githubにもあげてます。

github.com

最後に

今回は最初さっぱりわからず30分くらい問題とにらめっこしてたのですが、横向きに面積を計算する、その時面積はインデックスの引き算で求めることができる、ということに気づくと後はすぐに解けました。

見方を変えれば簡単に解けるけど、その見方に気付けないという典型的な問題でした。

こういう見方は普段から引き出しを増やすしかないのかなーと思うので今後も勉強を続けていきたいなーと思いました。