yukicoder No.321 (P,Q)-サンタと街の子供たち

問題文

http://yukicoder.me/problems/849

解法

この問題を見て何となくナイト巡回問題を思い出していた。 ナイト巡回問題ではすべてのマスに移動できたはずなので、一般化してもすべてのマスに移動できるのではないかと思ったが、サンプル4が合わない。 さて、どうしようか。

とりあえずP,Qが互いに素のときを考える。

実験してみると移動可能範囲は次の2パターンしかないことがわかる。

f:id:pekempey:20151216192707p:plain

1つ目のパターンになるのは、PとQがともに奇数のとき。何故なのかは市松模様から察してください。

f:id:pekempey:20151216192948p:plain

yukicoder No.321 (P,Q)-サンタと街の子供たち

いろいろ迷走してた。実験は重要(本当に重要)。