Fine Tuning

解説

ロボットが $x$ 軸正の向きに動き始めてから、再び $x$ 軸正の向きに動き始める直前までを $1$ 周とします。 すると、この $1$ 周の動きでのロボットの座標の変位は、入力した $K$ を用いて、 $(2K,2K)$ と表すことが出来ます。 これを用いて、ロボットの軌道を、 $4$ パターンに分けて考えましょう。すなわち、ロボットが停止前に最後に動いた向きによって場合分けします。

例えば、「①ロボットが最後に動いた向きが $x$ 軸正の向き」である場合を考えると、 $s$ 周した後に最後の動きをしたと考えた場合、 $s$ 周した時点でのロボットの座標は $(2sK,2sK)$です。このあと、 $x$ 軸正の向きに $a$ だけ進んだとしましょう。ロボットのプログラムより、 この直後に停止するためには $1\leq a \leq K$ であればよいです。そのため、 $r=K-a$ とすると $0\leq r \leq K-1$ なる $r$ を用いて、 ロボットの停止する座標は $((2s+1)K-r,2sK)$ となります。

同様に考えると、他の場合にロボットが停止する座標も、以下のように求まります。

「②ロボットが最後に動いた向きが $y$ 軸正の向き」である場合： $((2s+2)K-a,(2s+1)K-a)$

「③ロボットが最後に動いた向きが $x$ 軸負の向き」である場合： $((2s+2)K,(2s+2)K-a)$

「④ロボットが最後に動いた向きが $y$ 軸負の向き」である場合： $(2sK,2sK)$

したがって、これらの式のいずれかで $(X,Y)$ が表せていればよいということになります。ただ、 $s$ という変数があるため、 これを残したままでは直接的に求めることは出来ません。これについては、具体的に条件を見て対処法を考えます。

①の場合、 $((2s+1)K-r,2sK)$ ですので $Y$ が偶数でなければいけないことが分かります。また、 $1\leq K-r=X-Y\leq K$ が必要です。（ $1$ 以上の部分は、 $0$ 以上としてもよいです。） したがって、 $K$ の値が分かれば判定が出来ますが、 $Y=2sK$ より一意には決まりません。しかし、問われているのはこのような表し方を構成することであり、 成立条件としては明らかに $K$ が大きいほど有利です。このことから、$s=0$ の場合を除いては全て $s=1$ と決めてしまって構いません（これで構成できなければ、他の $s$ でも無理です）。 よって、この形で構成できる条件は、「 $Y$ が偶数かつ、 $1\leq X-Y\leq Y/2$ $(s\geq 1$ の場合 $)$ 」または「 $Y=0$ $(s=0$ の場合 $)$ 」です。

③の場合の $((2s+2)K,(2s+2)K-a)$ も、同様に $s=1$ と決め打つ考察が有効です。この場合は、「 $X$ が偶数かつ、 $0\leq X-Y< X/2$ 」という条件に帰着します。 また、④の場合の条件も実はこの中に含まれますので、④は改めて考えなくてもよいです。

最後に、②の場合の $((2s+2)K-a,(2s+1)K-a)$ ですが、この場合は $K=X-Y$ と定まりますので、直接確かめることが出来ます。 $Y=2sK+(K-a)$ と表したとき、これを$2K$ で割った余りが $K$ 以下であることが分かります。 逆にこの条件を満たすならば、 $a$ と $s$ は一意に適切に定めることが出来るはずです。よって、「 $Y mod (2K)\leq K$ 」が最後の条件です。

以上の $4$ つの条件のいずれかを満たす場合、その点でロボットを停止させることが可能、というのが最終的な答えです。

まとめ：

「 $Y$ が偶数かつ、 $1\leq X-Y\leq Y/2$ 」または

「 $Y=0$ 」または

「 $X$ が偶数かつ、 $0\leq X-Y< X/2$ 」または

「 $Y mod (2(X-Y))\leq (X-Y)$ 」

考察のポイント

①：実験によって法則をつかみ問題を分解する

手で軌道を書いてみることで、「 $1$ 周」の規則性に気づくことが出来ます。 （これが出来なかった場合、手元で大きめのケースでも実験することを意識するとよいかもしれません。小さいケースがコーナーケースであり、 ある程度の大きさからしか一般性のある性質が見えない場合も少なくありません。） すると、「 $1$ 周」に含まれない最後の部分の進み方によって停止点の座標が特徴づけられることが分かり、場合分けによって問題をいくつかの小問題に分割できます。

②：分かりやすい特徴量を定義する

この問題では、 $N$ と $K$ という数を選んでロボットの動きを決める、という設定ですが、考察においては $K$ が直接的に登場するのに対して、 $N$ は直接的に登場しません。 $N$ というのは、一番初めの進み方を直接的に特徴づける量なのですが、 問題を解くための場合分けにおいて着目するべきなのは（つまり、状況に差異があらわれるのは）むしろ「止まる直前」の動きであるからです。 そこで、 $N$ のかわりに、最後に進んだ量 $a$ や、 $K$ との差を取って $r$ という変数を定義します。これと、 $s$ および、場合分けのパターンから一意に $N$ を再構成できます。 このように、問題文において与えられた変数よりも、状況を分かりやすく説明できる「特徴量」に着目し両者の言い換えを行うことで見通しよく解くことが出来ます。

③：最も有利な状況を考える

場合分けの後、少々数学的な操作をすると成立条件を取り出すことが出来ますが、条件中の変数が確定していません。 十分な時間があれば、ありうる可能性を全探索するのも一手です（今回では、約数を全探索することになります）が、本問題ではTLEします。 今回は構成できるかどうかを聞かれていますので、Noと言い切るためには何が必要かと考えると、一番有利なケースでNoである必要がある、ということが出来る可能性に気づきます。 今回は条件が単純ですので、成立可能性に（広義の）単調性があり、この言い換えが成立します。 様々な可能性の中で、目的のために最善の状況を考えて絞り込むと問題がシンプルになることは少なくありません。