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

n-knuu's logs

憧れ駆動。だいたい競プロ

技術室奥プログラミングコンテスト#2 D - エンブレム(Emblem)

問題: D: エンブレム(Emblem) - 技術室奥プログラミングコンテスト#2 | AtCoder
解説: http://www.slideshare.net/maroonrk/ss-64770318

解法

Hは個数に関係なくて、KとWの比のみで決まるため、H=K/gcd(K,W), W=W/gcd(K,W)とする。
そうすると、x+y mod 2 が一定となる点を全て通ることとなる(x,yは1ずつ増えるか、片方が1増えてもう片方が1減る場合しかない)
交点はその中で0

コード


感想

  • Hが関係ない、H=Kのとき格子点上に乗る、格子点上に乗るときはx+yが一定、というところまではわかっていたが、WとKの比で決まる、x+y mod 2が一定になる、x+y=0 mod 2となる点を全て通るというところがわかっていなかった
  • こういう数学ゲー苦手