読者です 読者をやめる 読者になる 読者になる

SRM 514 Div1

Easy MagicalGirlLevelOneDivOne

nが複数与えられて、今居る地点から、(n, 1), (n, -1), (-n, 1), (-n, -1), (1, n), (-1, n), (1, -n) , (-1, -n)のどれかに移動できるn-kight jumpが許されている。

x,yが与えられるので、(0,0)から(x,y)にいけるかどうか判定しろ。

悩む。難しい。実験したいけど面倒くさい。

よくわからないけど直感的に幾何的な解法をしてみる→全くうまくいかない。

ひたすら悩むけど分からないのでしょうがなく実験する。→法則性見つかる。

  • 使えるnに偶数のものがあればどこにでもいけるからYES
  • 使えるnに奇数のものしかなければ、xとyの偶奇が一致していればYES、それ以外はNO

提出してみる、110点くらい。

レート下がらないならいいかと思っていたら、マイナスの余りはマイナスになることに気づく。

訂正してresubmit → 75.0点

Challenge

余りがマイナスのケース絶対誰かいると思って探すけど、(x+y)%2==0とかしていて悔しい。

でも、実はうちの部屋だけでも半分以上居て、そのうち2人を落とすことができました。

結果

75.0 + 100.0 = 175.0で170位くらい。レートは1373→1465になったのであとすこしで黄色や!

Easyの解法のりくつ

実はシステムテスト通ったものの、自分の解法でなんで良いのか分からなかったんだけど、少し考えたら納得できる理由が思いついた。

無限に広がる平面に偶奇でパリティを振ると、

xoxoxo

oxoxox

xoxoxo

oxoxox

みたいになるけど、nが偶数の場合oからx、xからoに移動できて(ていうか隣のマスにいける)、nが奇数の場合はxからxかoからoにしか移動できないので、二部グラフっぽい考え方ができる。

...なんでこれにみんな一瞬で気づけるん?