Good Bye 2015 - C. New Year and Domino
概要
H*Wのグリッドを与える。そのグリッドには"."と"#"の2つがある。あなたは1*2のサイズのドミノを持っていて、縦向きか横向きのいずれかの向きで、グリッドの2つ連続で"."になってる場所における。
次のq個のこqueryに答えよ。
- グリッドを1-idxとして、[a, b] * [c, d]の範囲のグリッドに、ドミノは何通りの起き方が存在するか？
制約： 1 <= a <= c <= h <= 500, 1 <= b <= d <= 500
ACするまで
1. query大量にあるから、O(1)で答えられるようにしたいなぁ。
2. 2次元累積和をやるとうまくいきそう。
3. しかし、縦向きと横向きの両方があるので、単純に厳しい。この2種類をごちゃまぜにして実装すると、実装がすごいことになる。
4. このタイプの問題は、縦向きと横向きの2種類の置き方があるので、別々に、縦向きにいくつ置けるかと横向きにいくつ置けるか、分けて考える。
5. それぞれ分けると、2次元累積和が簡単に書ける->AC！
考察
Point
2次元や3次元でまとめづらい状態があるのならば、それぞれの軸ごとに考えてうまくいくか？を考えてみる。
今回の場合、この場合ドンピシャであるので、そのまま実装する。
ちなみに、2次元累積和の実装においては、丁寧に図を書いて、indexに注意したほうがいい。今回の場合、ドミノミノが2マス以上にわたるので、いつもと違って少し変則である。
一言
これは要反省。要反省。要反省。
