当日は別の遊ぶ予定があったが無理やり数十分くらい時間をもらって参加したのだけど 満足に１つも解けず…。

もうちょっとやるならやるでちゃんと時間をとってやるべきだった( ；´Д｀)

本戦がかなり難しかったらしく面白そうだが、そもそも自分からしたら予選で難しいので、予選を解いてみた

D. 庭園

300x300のセルが与えられて、各セルに整数(負数を含む)が与えられており、 セルの中で長方形を二つ選んだ時に、各長方形の整数の和が最大になるように選ぶ問題。

簡単に考えられるのは事前に各行/各列で累積和を計算しておいて、あとは長方形を全列挙するという 方針の解き方で累積和の計算に O(H*W)、長方形の列挙に O(H^2*W^2)

あとは二つ選ばないといけないので、組み合わせを試すために列挙した長方形の端っこの x座標とy座標とコストのペアを覚えておいて重ならないように組み合わせを試した

http://dwango2016-prelims.contest.atcoder.jp/submissions/632337

で、結局 O(H^2 *W^2) がとれないので解説を読む。

O(H * W^2) でコスト最大の長方形を探索するが、その際にx座標でどこからどこまでの情報とコストのペアが 得られるので、(x座標で見て)重ならない組み合わせが列挙できて、あとはセルを転置して同じことをする、だった

http://dwango2016-prelims.contest.atcoder.jp/submissions/637939