トヨタシステムズプログラミングコンテスト2021 (AtCoder Beginner Contest 228) F - Stamp Game (500)
コンテスト中の考察
h2,w2はそれぞれh1,w1より大きくても無駄なのでそれ以下の値としておく
累積和を使って高速化しても二人の選び方を全て試すと$ \mathcal{O}(H^2W^2)で間に合わない
セグ木などを使ってある範囲の最適な値をより高速に求められそう
二次元の範囲の最大値をセグ木で求められるなら$ \mathcal{O}(HW \log H \log W)くらいになりそう
うまく二次元を高速化させる方法が分からなかった
解説の方法
青木君の結果は高橋君の範囲の取り方に依らず決まるので事前計算できる
累積和を少し広めに拡張して取っておく
行毎にセグ木を持って各列の結果を追加しておく
列毎にセグ木を持って各行毎に範囲内の最大値を値として追加しておく
各マス毎に列毎のセグ木から範囲内の最大値を取ってくる
行、列の結果を別々のループで計算するようになるので$ \mathcal{O}(HW(\log H + \log W))で解ける
問題: https://atcoder.jp/contests/abc228/tasks/abc228_f
提出: https://atcoder.jp/contests/abc228/submissions/27565526
#トヨタシステムズプログラミングコンテスト2021 #ABC228 #500pt #F #ABC #AtCoder
#二次元累積和 #セグ木 #二次元セグ木