SRM406

250

8!個のすべての順列に対して何本線が引けるかを計算して最大のものをとればよい．

500

高々12*12ぐらいの数字(-100から100)が書かれた紙を折っていく、折った時に重なった数字は合計する。折ってった時のセルの数字が最大となるように折れという問題。
縦と横はそれぞれ独立に折ってよく、各折方に対してセルの重なりの組み合わせは2^12程度しかないので2^12 * 2^12なら間に合う．(本当は2^24 * 12^2だとかなり厳しいけど実際は長さが12の時でも折ってできるセルの重なり方は400通り程度しかないので大丈夫)

1000

k-th shortest pathという単語が見えて、やる気をなくす。