TopCoder SRM 514 (Div 1)

TopCoder 参加記録

久々のhighest更新！

Result

232.18 / Opened / Unopened
2撃墜0ミス


43位
1919 -> 2020

Easy MagicalGirlLevelOneDivOne

問題

無限に広いチェス盤の(0,0)のマスにコマがあるとする。
コマは(0,0)からみて(n,1), (n,-1), (-n,1), (-n,-1), (1,n), (-1,n), (1,-n), (-1,-n)の位置に動くことができる。


このコマが(x,y)に行けるかを答えよ。コマは何回移動してもいい。

試行錯誤

x,yは10億以下なので探索は無理。
えーと、nが偶数だったら(n,1)に動いてから上下移動して左に戻ってくれば(1,0)に移動できる。ってことはnが偶数なら無条件でどのマスにも行ける。


nが奇数だと？(1,1)は上と同様にして行ける。(1,0)は行けなさそう。
行けないことを証明しよう。
コマの座標を(x,y)とすると、nが奇数のとき、x+yの偶奇は移動の前後で変わらない。


おｋ証明できた。つまりnが奇数ならx+yが偶数のときかつそのときに限り移動できる。
コードにした。サンプル合った。
剰余のマイナスやオーバーフロー等に注意しながら何回か見直し。大丈夫そうなので提出。

Medium MagicalGirlLevelTwoDivOne

問題

hxwマスの長方形の板がある。それぞれのマスには1-9の数字または'.'が書かれている。
i行j列目の数をf[i][j]とするとき、任意のi,jについて

  • f[i][j]+f[i][j+1]+f[i][j+2]+…+f[i][j+n-1]が奇数
  • f[i][j]+f[i+1][j]+f[i+2][j]+…+f[i+m-1][j]が奇数

になるように'.'を埋める場合の数はいくつか。mod1000000007で求めよ。

試行錯誤

制約条件h,w≦50かー。ビットDPとか無理だからなんか上手い具合にオーダー落としてDPにできるのだろうか。


なんか上手いことやれないかを考える。
とりあえず、偶奇はnxmの長方形を敷き詰めたような感じになる。
つまり、f[i][j]とf[i+n][j+m]の偶奇は一致する。うーん。だから何だ。


残り30分切ったくらいで気付く。n,mは10以下であると書いてあることに。
なんじゃそりゃー。ビットDP出来そうじゃんorz
nxmマスの偶奇を1行ずつループしてビットDPしたらいけそうな気が。


タイムアップ。うーんなんか今回も解けそうだったなあorz

Hard

開けてない。

Challenge Phase

赤が一人もいない部屋！これはチャンス。

  • なんか普通に間違えてる人がいたので落とす。
  • もう一人普通に間違ってる。落とそうと思ったら先に落とされる。
  • マイナスの剰余がマイナスになることがわかってない奴がいたので落とす。

そんなんで2撃墜0ミス。部屋全体では6個くらい落ちてる。
こんなに撃墜回になるような問題じゃなかった気がするんだけど。。。

System Test

通った。部屋で撃墜されてない奴は全部通ってた。