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にしか移動できないので、二部グラフっぽい考え方ができる。
...なんでこれにみんな一瞬で気づけるん？
