問題：D - 登山家
解答①：Submission #10974270 - CODE FESTIVAL 2014 予選B
解答②：Submission #10977004 - CODE FESTIVAL 2014 予選B
解答③：Submission #10993670 - CODE FESTIVAL 2014 予選B
解法：i番目の山小屋について、その山小屋より左側、右側でそれぞれどこで突き当たるかを調べてゆく。
①DP
右側の場合を考える。dpr[i]：i番目の山小屋が右側で突き当たる山小屋の番目 とすると、右側に見える山小屋の数はdpr[i] - i - 1個である。dprは次の手順で高速に算出できる。
- 最初はdpr[i] = i + 1 と設定
- dpr[i] < n かつ h[dpr[i]] ≦ h[i]のとき、dpr[i] = dpr[dpr[i]] と更新
これは、i番目の山小屋より右の突き当たる山小屋を次々と辿ってゆくイメージである。山小屋を辿る回数は、n個の山小屋を通して合計n回までであるため、全体としてはO(N)である。
左側も同様。
②Stackを使う
右側の場合を考える。dpr[i]：i番目の山小屋が右側で突き当たる山小屋の番目 とするのは①と同じ。
山小屋の番目を保持するStackを準備し、i番目の山小屋の調査に対し、Stackを次のように更新していく。
- h[Stack.top()] ≦ h[i]である限り、Stack.pop()
- Stackが空なら突き当たる山小屋はなく、そうでないならStack.top()が突き当たる山小屋
- Stack.push(i)
i番目の山小屋より小さい山小屋がそれ以降に調査対象とはならないため、Stackから落としてゆくイメージ。
左側も同様。
③二分探索
山小屋の高い順に山小屋の個数を調べてゆけばよい。山小屋の番目をsetに格納し、upper_boundとその1つ手前の要素が突き当たる両端の山小屋である。調べ終わったらその山小屋の番目をsetに格納する。
注意点として、同じ高さの山小屋がある場合は、各山小屋について先に全て調査し、その後各山小屋の番目をsetに格納する必要がある。
