Hatena::Grouptopcoder

blu_rayの日記

2011-11-30

SRM 525 Div2

| 06:40

ox-

無理。

250. RainyRoad / Passed : 168

まんまとBFSで出してしまう。遅い。

600. DropCoins / Failed

Challenge Phase始まって1分くらいで撃墜される。TLE

全部終わった後、泣きながらPracticeRoomのwriterさんのコードを見る。

わざわざO(n^4)の解き方とO(n^6)の解き方があって丁寧さに泣ける。

O(n^6)の方を写経して、自分で最悪ケースでチャレンジしたら死んだけど、6重ループでも出来てる人がいるので、なんか工夫すればいいんですね。

O(n^4)の方は

sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + g;

が脳内でイメージ出来たときにおどろいた。こういうのって思いつかないと駄目なのか。

rate

996(-75)