ABC331D - Tile Pattern
あとから解いてAC
コンテスト中
この問題では$ 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方向全てに対する端の黒タイルの数を計算するのはミスが起こりやすい
バグに悩まされて、ずっと解けず。
解法
関数の性質を用いて、いかに場合分けを減らすかを考える必要があった。
四方にではなく、下と右だけを考慮すればいい
$ 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のときを考慮し忘れやすい