ABC331D - Tile Pattern
Difficulty: 1361 (水色diff)
あとから解いてAC
提出: https://atcoder.jp/contests/abc331/submissions/48152933
コンテスト中
この問題では$ Pとして与えられたタイルパターンが連続して並び続けている。
繰り返しパターンを用いて捉えたらいいことはわかっていた
長方形は次の四つの領域に分けられる
タイルが完全に繰り返される部分(中心部)
タイルに何個の黒が含まれるかをあらかじめカウントしておけばいい
それ以外の端
どのタイミングで区切れるかはクエリによって変わる
どう計算すればいい?...(*)
$ P\lbrack i\rbrack\lbrack j\rbrack: $ i \leq i' $ j \leq j'なる$ (i', j')に存在する黒マスの数
(*)を解決するためにあらかじめ計算していた。
漸化式による累積和
$ O(n^2)
$ P\lbrack i\rbrack\lbrack j\rbrack - P\lbrack i - 1\rbrack\lbrack j\rbrack
さらに、$ P\lbrack i\rbrack\lbrack j\rbrack - P\lbrack i - 1\rbrack\lbrack j\rbrackなどの計算式で、タイル中の部分領域にある黒マスの数が取れる。
これを用いれば、周辺の端のタイル個数も取れる!.......とでも思っていたのかぁ?
嫌な予感はしていたが、やはり8方向全てに対する端の黒タイルの数を計算するのはミスが起こりやすい
バグに悩まされて、ずっと解けず。
解法
バグを排除しやすい書き方が大事になる。
関数の性質を用いて、いかに場合分けを減らすかを考える必要があった。
D - Polyomino - AtCoder Beginner Contests 322に近い雰囲気はある。
四方にではなく、下と右だけを考慮すればいい
$ g(x, y): (0, 0), (x, y)からなる長方形内に存在する黒タイルの数
これはまだ実装しやすい
3つのタイル端だけを考慮すればいいので、混乱が生じにくい
下
右
右下
Point構造体を作っておいて、それぞれの要素に別途modを取るようなメソッドを用意しておくとやりやすい。
https://scrapbox.io/files/656b58527eddc5002640ebb6.png
上の図において、求めたいのが$ Dの中にある黒タイルの数だったとすると
(問題文中で使われている$ A, B, C, Dとは区別する。)
$ gを用いたら、次の場所にある黒タイルの個数が即座に求められる。
$ A+B+C+D
$ A+C
$ A+B
$ A
これをうまく足し引きしてやれば、$ Dだけを抽出することができる!
包除原理
これを用いて、$ gの実装だけに専念すれば実装がすごく楽になる。
どれが一番やりやすいかを先に考えて、その後にその結果を利用する
注意すべきコーナーケース
$ gについて、扱う長方形の面積が0のときを考慮し忘れやすい
AtCoder_Beginner_Contest 311 -- D - Tile Pattern