codeFlyer （bitFlyer Programming Contest）-D(500) ハンコ
概要
H * W (H, W <= 10^9)のサイズの白紙に、N * M(N, M <= 1000)のハンコを左上から押せるマスすべてを押していく。ただし白紙からハンコをはみださせてならない。(問題文の図を見るとわかりやすい)
ハンコも白紙も1*1のサイズに分割されていて、ハンコはそれぞれのマスごとに黒or白がある。
白紙は一度ハンコが押されて、その時点のマスが黒となったのならば、そのマスはずっと黒となる。
左上から右下まで、押せる場所を全部押させると、白紙には1*1のマスのうち、黒いのが何個あるか？
ACするまで
1. あるマスが黒ならば、白紙のうちの特定の区間が丸ごと黒になる。あまり白紙が大きくない場合、二次元imos法を使用すれば普通にやっても間に合いそう。
2. 白紙が非常に大きいとき、普通にやると間に合わない。しかし、ここで、1の黒いマスの特定区間を考えてみると、実はハンコのどこに黒いマスがあっても、必ず重複する区間がある。その区間をカットできそう。
3. 2の考えを詰めると、白紙の四隅のハンコ分の情報さえ持っておけば、省略される区間の情報も復元できそう。
4. 二次元imos法で座標圧縮して、復元すれば数え上げできそうー＞AC
考察
紙が小さい場合は、愚直に二次元imos法すれば、どこのマスが黒で白かをO(NM)でできる。ハンコを押していくというのを実際にやってみると、紙が大きいのならば、紙の中心に黒のブロックができる。
これをさらに考えてみると、大きな白紙はつぎのように分割できる。
A A B B B A A
A A B B B A A
B B C C C B B
B B C C C B B
B B C C C B B
A A B B B A A
ただし、ハンコのサイズは2 * 2であるとする。
Cの部分は、ハンコのどこに黒があっても、最終的に形成される白紙の真ん中の黒い部分である。
Bの部分は、黒か白かはわからないが、一列or一行はすべて同じ色であり、Aの部分によって決定される。
Aの部分は、白紙の角である。
この関係を見ると、
- Cはハンコに黒いマスがあるかどうかで計算によって求まる。
- BはAの部分さえ分かれば、O(N)orO(M)で計算で求められる。
- Aの部分は、計算だけでは簡単には求まりそうにない。
とわかる。つまり、Aの部分さえ分かれば、CもBも連鎖的に求まるとわかるのである。
このように、広いフィールドを操作していく際に、ひとまず連続して同じ値をとるものに着目して座標圧縮的な考えで考え始めるとうまくいくことが多い。(そして、実装力も必要な問題も多い気がする)
ここで、Aの部分を求めることを考える。それぞれのハンコの黒いマスに対して、Aの部分だけを集めた(2*N)*(2*M)個のフィールドに、指定区間を黒塗りするという操作をする。普通にやると、1回の操作あたりO(NM)かかるが、二次元imos法というテクニックを使用すると、後処理O(N+M)かけることで、O(1)で黒塗り範囲を追加できる。
具体的な実装としては、(2*N)*(2*M)のサイズの配列を用意して、Aの部分とする。ここで、ソースコードのとおりにmin関数で実装すると、片方の軸だけハンコよりも紙がとても長い場合などでも場合分けをしなくて済む。
最後に、黒いマスを数え上げるんだけど、
- Aの部分は愚直にO(NM)で数え上げ
- Bの部分はO(N+M)でAを参考にしながら、一列黒or一列白のどちらかがわかるので数え上げ
- Cの部分はハンコにそもそも黒いマスがあるか、あるならばCの部分は全部黒なのでそれを足す
これを全部丁寧に足してあげるとACする。大きいのでlong long で実装するといい。
ACソースコード：
Submission #8690206 - codeFlyer （bitFlyer Programming Contest）
一言
二次元imos法もこういうタイプもなかなか見てなくて、思いついても実装が重かった。
