drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder ABC-E 水色diff 二次元グリッド グリッド上のDP DP 二次元累積和 累積和 二分探索 典型要素を詰め合わせた教育的問題 0と1の問題 制約条件:正方形領域 数え上げ問題 解空間:O(N^2)通りの選択肢 極大なものを考える sparseな問題 考察：一部の変数を固定して考える そのまま覚えたい典型問題 単調性に着目する 累積和テク:区間の総和を累積和で高速に求める 【問題集】累積和 【問題集】二次元累積和 AtCoder475点 NoviSteps1Q 有名な DP をするか、二次元累積和 + 二分探索をするか 問題へのリンク 問題概要 のグリッドが与えられる。グリッドの各マスのうち、指定された 個のマスには穴があいている。その他のマスは穴があいていない。 グリッドに含まれる正方形であって、その内部に穴を含まないもの何個あるかを求めよ。 制約 解法 (1)：DP 正方形の右下マスの位置で場合分けして数えることにしよう。つまり、マス を右下マスとする正方形が何個あるかを考える。 これは簡単で、マス を右下マスとする正方形のうち、内部に穴を含まない最大の正方形の一辺の長さを とすると、マス を右下マスとする正方形はちょうど 個ある (一辺が の … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2023%2F07%2F24%2F231100" title="AtCoder ABC 311 E - Defect-free Squares (1Q, 水色, 475 点) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/d/drken1215/20230724/20230724224143.png Hatena Blog https://hatena.blog 2023-07-24 23:11:00 rich https://drken1215.hatenablog.com/entry/2023/07/24/231100 1.0 100%