SRM395

250

(0,0)から(X,Y)まで格子点上の移動で行く時に，縦横に動く時の速度と対角線に動く時の速度が与えられているとする．このとき最短到達時間を求めよという問題．
行き方としては(0,0)->(X,0)->(X,Y)と縦横移動のみで行く方法と(0,0)->(X,X)->(X,Y)(便宜上X(X,Y)のときに対角線の移動が速いときはジグザグに動いたほうが得なのでそこも考えると移動の仕方は3通りでその中で最も早い到達時間を返せばよい．

500

高さが1からn(n <= 100)までのビルディングがあるとする．このとき[1,3,5,2,4]と並んでいた場合は左端から見ると[1,3,5]のビルが見え，右端からみると[4,5]のビルが見える．問題は左端から見えるビルの数と右端から見えるビルの数が与えられた時に[1..n]の順列のうちその条件を満たす者の数を答えよというもの．
時間内に解法を思いつかなかった．
最も高いビルの位置を固定すると左端と右端を分けて考えることができ，x個のビルディングを並べたときに左からy個見えるような配置の数はどれだけかというのがわかればいい，でそれは配置を右から決めてくことにすると右端に最も高いビルを置かない場合，左端からはそのビルは見えることがないことに注意すると次の再帰式が成り立つ

f(x , y) = f(x-1,y-1) + (x - 1) * f(x - 1 , y)

あとはメモ化再帰で書いてやればよい．

900

ちょっと読んだけど問題の意味が分からなかった．