(P,Q)-サンタと街の子供たち 解説(?)
なんかめっちゃ面白い問題だなぁ、と思いかつ上手くハマって解けたので、つたないですが解説記事を書かせていただきます。
(お昼に間違ってフライング投稿しちゃってて慌てて非公開にしましたごめんなさい＞＜)
問題はこちら
No.321 (P,Q)-サンタと街の子供たち - yukicoder
ナイトはチェス盤のすべてのマスに到達できるが、それ以外の距離の移動のみではどうなるか？ というもの
まずは、例外処理から（以下、 とし、各座標はすでに絶対値を取ってあることとします）
- (p, q) = (0, 0) のとき
自明に動けないので、 となる点がいくつあるか探します（
が書いてなかったように思うのですが、できればどちらか明記していただけるとありがたかったかも、書いてあったらごめんなさい＞＜ ）。
- p = 0 のとき
ならばいけるので探します。
- gcd(p, q) > 1 のとき
必要条件として、 が挙げられます。かつ、p, q が互いに素となる状態にして後述の条件を満たすか判別すればよいです。
- p, q が互いに素のとき
とりあえず、チェス盤を考えます。
まず、ナイトと同じな (p, q) = (1, 2) のときを考えると、最初は (0, 0) の白マスにいて、移動した先は必ず黒マスになっています。
次に、(p, q) = (1, 3) を考えると、白マスにしか到達することができず、絶対に黒マスに到達することができません。
ここで、次のような仮定をすることができます。
「すべてのマスに到達できる ⇔ gcd(p, q) == 1 かつ (p + q) % 2 == 1」
かつ、
「gcd(p, q) == 1 かつ (p + q) % 2 == 0 ⇔ すべての白マス( (x + y) % 2 == 0 ) に到達できる」
本番では、私はこれを証明せずに投げて通してしまいました。
ここに証明を書いてもいいのですが、writerさんが解説ページで証明っぽいのをなされているのでここでは割愛させていただきます（めんどいし）。
http://yukicoder.me/problems/849/editorial
23分ほどでACし、7番目くらいでした。あんまこじらせないでさっと行けてよかった……。
