TopCoder SRM 639 Div1 Medium Board Folding - yoshiokatsuneoのブログ

http://community.topcoder.com/stat?c=problem_statement&pm=13457

[問題]

N x Mのマス目がある折り紙が机に置いてある。それぞれのマスは白(1)又は黒(0)色になっている。

折り紙は机から持ち上げずに、縦又は横に折り目を付け、左、右、上、下から半分を持ち上げて反対側に持って行って折り曲げること。

ただし、折り曲げることができるのは、合わさった面の両方が同じ模様の時だけ。

最終的な長方形は何通り作れるか、長方形は同じ形・サイズ、且つ同じ位置に置いてある場合は同一とみなす。右から左に半分と、左から右に半分は、同じ形になるが、位置が違うので別と考える。最初の状態も１通りにいれる。

1<=N,M<=250

[解答](本番後)

縦と横の折り方は独立。つまり縦に折った後横に折っても、横に折った後縦に折っても同じ。なので、(縦の折り方) x (横の折り方) が答え。

縦と横は計算方法が同じなので、横の折り方について考える。

まず、左側から(何回か)折る場合について考える。

まず総当たりで考える、左側から最初に折れる方法は、1列目、2列目、３列目、さらにもう一度2列目、3列目...、... さらに3列目、4列目、4列目、...と折れる。ただし計算量はN!(より少し少ないぐらい)かかる。

ただ、できる形としては左から1列目(の右端)、2列目(の右端)、...のN通りだけなので、DPで求める。i列目(の右端)で折れるか折れないかをDP[i]で表す。iより左側のj列目が折れて、j列目からi列目を右側に折ることができれば、DP[i]はtrueになる。

i=0..N, j = 0..i-1について、DP[i] = DP[j] & (jからiを右側に折れるか)として計算する。計算量はO(N*N*(jからiを右側に折れるかの計算量))になる。(ソース中ではfoldable_edge)

jからiを右側に折れるか、についてはfoldable[j][j-i]としてあらかじめ計算しておく。累積和を用いて、foldable[j][x]=foldable[j][x-1] & ( (j-x)列目(j+x)と同じか )のように計算しておく。(x列が折れて、x+1番目の列が折れればx+1列が折れる)

さらに、a列目とb列目があらかじめ同じか計算しておく(same[a][b])。ループでO(N*N*M)で計算してもいいけど、ソートしてから同じ値を操作して探すことで　O(N*log(N)*M)で計算できる。(SHA1等のハッシュを使えばO(N*M)で計算できるけど、競技プログラミングではあまり使わなさそう)

このようにして、左から折れるかを計算し、同様に右側から折れるか計算する。

ここで、右側から折るのと、左側から折るのは独立。つまり右を折って左を折って右を折って、、、としても右側だけ最初に全部折ってから左に折っても、左側から最初に全部折ってから右に折っても結果は同じ。

なので、左からの列数lと右側からの列数rについて、l+r<Nの範囲について、右が折れて且つ左が折れる回数をカウントすればいい。計算量はO(N*N)。累積和を使えばO(N)にできると思うけど、トータルの計算量には影響しない。

トータルの計算量はO(N*N + N*M*log N + M*M + N*M*logM))となる。

実際にはN,Mは250以下なので、(N or M)の三乗ぐらいまでは大丈夫でもう少し緩くてもいいみたい。

[コード](C++)

https://paiza.io/projects/rjKgK5E_Si5Dbx8qiO0N2g

[感想]

個々の要素アイデアはそれほど難しくないけど、時間内に全てを組み合わせるのは難しい。別の日に考えてようやく全体が整理できてくる。

ただ、この問題(というか累積和的な問題？)は要素アイデアの組み合わせてオーダを下げていく感じなので、一歩づつ徐々に進めていけるのは、連鎖しているというか、レベルを上げていく感じで面白い。