yukicoder No.86 TVザッピング(2)

No.86 TVザッピング(2) - yukicoder

[問題]

N x Mのマス目がある。あるボタンから開始して、通れるマス目を1回づつ巡って最初のマスに戻る。ただし、ボタンを巡る際、進行方向はまっすぐか左にのみいける。

[解答]

最初のボタンの前後では実質的に右み回ることができる。

一番左上のマス目を探し、そこから下又は右向けに出発する。各ボタンでは右、真っ直ぐ、左の順番で通れるマス目か確認する。右にまわれるのは一回のみ。最初のマスに戻った時点で全部のマスを取ったか確認する。

[コード](Ruby)

https://paiza.io/projects/9y1nbsofwJYJL7IplYnF1A

 [感想]

最後に全部のボタンを通ったか確認するのを忘れていた。

 

 

yukicoder No.85 TVザッピング(1)

No.85 TVザッピング(1) - yukicoder

[問題]

X * Yのマス目にボタンがある。いずれかのボタンからスタートして、上下左右のいずれかのボタンに動いて最初のボタンに戻る。各ボタンは一度だけ辿ることができる。このように巡回することはできるか?ことはできるか?

[解答]

巡回するので、どこから始まってもいい。縦または横が偶数ならば、くねくね辿って直線で戻ることで巡回できる。ただし、縦又は横が1の場合、戻ってこれないのでダメ。さらに、1x2の場合は、OK。

 

[解答](Ruby)

https://paiza.io/projects/K5KiEZdvV0rzO12bbQuZIw

 

 

 

[感想]

こんなの簡単!と思いきや、縦又は横が1の場合を考えておらず、さらに1x2の場合を考えてなかった。

 

TopCoder SRM 639 Div1 Medium Board Folding

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

[問題]

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

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

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

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

1<=N,M<=250

 

[解答](本番後)

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

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

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

まず総当たりで考える、左側から最初に折れる方法は、1列目、2列目、3列目、さらにもう一度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

 

[感想]

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

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

 

yukicoder No.84 悪の算盤

No.84 悪の算盤 - yukicoder

[問題]

R行C列のマス目から1個だけ選んで"*"を書く。

作れるパターンに0から順番に番号を付けると何番まで書けるか。

1<=R,C<=10^9

[回答]

基本的にパターン数はR*C。

縦横の長さが同じ場合、90度で回転させるので4で割る。違う場合は180度で回転できるので2で割る。

縦横共に奇数の場合、真ん中のマスは回転させない。

[コード](Ruby)

https://paiza.io/projects/mdBf2tQTq7n1CXYZ0zUzaA

 

 [感想]

Rubyは桁あふれを考えなくていいのが楽。

yukicoder No.83 最大マッチング

No.83 最大マッチング - yukicoder

[問題]

0..9のデジタル数字をマッチで書く。マッチN本で数字を書く時、最大で書ける数字(複数桁)は何か?

2<=N<=10^5

[回答]

1本で書ける数字はない、2本で1が書ける、3本dで7が書ける。

桁数が多い方がいいので、1を使えるだけ使う。2で割り切れない時は3本で7を1個作る。7は一番左に使った方が大きい数字になる。

[コード](Ruby)

https://paiza.io/projects/feqKWR9BuEvapUl8vbfnwA

 [感想]

シンプルで面白い問題。

 

yukicoder No.82 市松模様

No.82 市松模様 - yukicoder

[問題]

幅W、高さH、左上C("B" or "W")で、"B"と"W"の市松模様を書く。

 

[回答]

(w + h)%2==0 or 1で"B"又は"W"を出力。

Cが"B"か"W"で出力を反転。

 

[コード](Ruby)

https://paiza.io/projects/8cO8BE7P9BK9mOHEVVh5pA

 

 [感想]

左上が"B"か"W"かは、どちらかでもいいと思って一度WA(Wrong Answer)。