Facebook Hacker Cup Round 1A

NHCタグがここまでふさわしいのは久し振り。そしてIEに感謝したのも久し振り。

After the Dance Battle

二次元グリッド上を上下左右に移動して目的地に移動する。ただし、同じ色の床は移動と同じコストでワープできる。最短移動回数を答えよ、という問題。

BFSするだけ。

Power Overwhelming

コストAのものとコストBのものを予算Mまで購入し、それぞれの数の積を最大化せよ、という問題。

二次方程式を解いて、一応不安なので近隣いくつかを探索するだけの問題。long溢れに注意。

First or Last

N個の地点で、K回の追い越しをしたいが、各地点について、追い越しをしたときの事故率と、しなかったときの事故率が与えられるので、できるだけ安全に進行するときの事故しない確率を答えよ、という問題。

追い越しをする回数が固定なので、各地点について、事故率の比率を考える。追い越しをすることで事故率の増加率が小さいところから順番にK個選択すれば良い。事故率の比率はint溢れするのだけれど、テストケースではたまたまうまくいくみたい...。