AtCoder Beginner Contest(ABC) #016 A - 12月6日
- AtCoder Beginner Contest #016 | AtCoder
[問題]
月が日で割り切れれば"YES",それ以外は"NO"を表示する。
[解答]
月%日==0で判定
[コード](Ruby)
https://paiza.io/projects/BXfPvIAk9Mn-a-amw05H_g
[感想]
頑張れば50バイトぐらいになるかなぁ?
yukicoder No.86 TVザッピング(2)
[問題]
N x Mのマス目がある。あるボタンから開始して、通れるマス目を1回づつ巡って最初のマスに戻る。ただし、ボタンを巡る際、進行方向はまっすぐか左にのみいける。
[解答]
最初のボタンの前後では実質的に右み回ることができる。
一番左上のマス目を探し、そこから下又は右向けに出発する。各ボタンでは右、真っ直ぐ、左の順番で通れるマス目か確認する。右にまわれるのは一回のみ。最初のマスに戻った時点で全部のマスを取ったか確認する。
[コード](Ruby)
https://paiza.io/projects/9y1nbsofwJYJL7IplYnF1A
[感想]
最後に全部のボタンを通ったか確認するのを忘れていた。
yukicoder No.85 TVザッピング(1)
[問題]
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 悪の算盤
[問題]
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 最大マッチング
[問題]
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 市松模様
[問題]
幅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)。