CODE FESTIVAL 2014 予選B
コンテストページ http://code-festival-2014-qualb.contest.atcoder.jp/
解説 http://www.slideshare.net/chokudai/codefestival2014qual-b
Cが全然わからず38位。Dの方が明らかに簡単だった。
A - あるピアニスト
maxとるだけ
puts gets.split(' ').map(&:to_i).max
B - 歩く人
和をとっていくだけ
C - 錬金術士
本番中に通せたけどたぶん嘘解法。テストケースがガバガバで明らかに間違ってる方法でも通っちゃう。フローでも解けるとの情報を得たので考えてみた。
文字の位置は必要ないので各文字の出現回数だけカウントしておく。
上図のようなグラフを生やしてs-tフローが2*N流れればS1,S2 から S3 が錬金できる。
D - 登山家
本番ではRMQで二分探索してO(n (log n)^2)で通した。segtree内で二分探索するかsparse tableを使えばO(n log n)になる。
stackを使う解法の解説がスライド一枚で済んじゃってるので簡単に解説でもしてみる。
各位置i(i=0,1,..,n-1)について降順にそこからどこまで東の小屋が見えるかを求めることを考える。スライドの操作１のスタックをpopし続ける操作について説明すると、popする条件によりスタックに詰まれているindexは昇順、対応する高さも昇順になっている。
したがってh[i]を超えるスタックに積まれている中での最初のindexを求めるにはスライドの通り操作すればよいことがわかる。ここでpopされたindexは二度と調べられないが、そのようにして問題ない理由はpopされたindexはdp[j](j
