hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 競技プログラミング https://yukicoder.me/problems/no/866 解説 https://yukicoder.me/submissions/370328 結構計算量が厳しいらしいので、ゴリゴリ計算系であろうと思う。 全探索で考えると、左上をHW通り試し、正方形の一片を試してmin(W,H)通り試す。 これだと間に合わない。 間に合わないが、正方形の一片をどんどん大きくしていくと、種類数はどんどん増えていく。 二分探索すればちょうどP種類の時が見つけられる。 あとは、区間にある種類数を高速に求めたい。 26種類を二次元累積和で管理して、何種類あるか求めよう。 これで計算量はO(HWlog(… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2019%2F08%2F18%2F090115" title="レベルKの正方形 [yukicoder 866] - はまやんはまやんはまやん" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2019-08-18 09:01:15 rich https://blog.hamayanhamayan.com/entry/2019/08/18/090115 1.0 100%