D - おいしいたこ焼きの焼き方 (abc005_4)

Quiz

https://atcoder.jp/contests/abc005/tasks/abc005_4

Submit

https://atcoder.jp/contests/abc005/submissions/4079770

学び

• 2D累積和を求める前に、行毎に累積和を求めておけば矩形和もO(N)で求まる

その他

• 発想は難しくなく、きっちり実装すればいい
• 途中まで上手くいっていることも確認しやすいので、D問題の入門としてよさそう

2020/10/31

• 焼く位置として左上と右下を全探索。O(N⁴) = 6250000
• 領域が決まったらその内部の美味しさの和は高速に求めたい
• 2次元累積和を使えばO(1)。2次元累積和の構築にO(N²)
• それらで事前準備しておけば各クエリにはO(1)で答えられる
• よって計算量は、max(N⁴, Q)