クルトンのプログラミング教室

Pythonの使い方やPythonを使った競技プログラミングの解法などを解説しています。

Pythonで解くAtCoder(ABC175:C)

Pythonで解くAtCoder

こんにちは、クルトンです！
この記事では

AtCoderの「AtCoder Beginner Contest 175」のC問題をPythonを使って解説します。

問題のリンクを載せておきます。

解法
サンプルコード
まとめ

解法

まず、左右対称性に注目すると

$X=p$ のときと $X=-p$ のときの答えが等しいことがわかります。

よってここからは $X=|X|$ として $X\geq0$ のときについて考えます。

絶対値が最小となるような移動後の座標について考えてみましょう。

・ $K$ が小さいとき（ $X\geq{K}\times{D}$ のとき）

f:id:kuruton456:20200816143844j:plain

図の黄色丸は、K回目の移動後に止まる可能性がある座標を表し、

水色丸は、K回目の移動中に通ることができるが、K回目の移動後には止まる可能性がない座標を表し表しています。

この場合、K回の移動では0にたどり着かないため、 $X-K\times{D}$ が答えとなります。

・ $K$ が大きいとき（ $X<{K}\times{D}$ のとき）

この場合は2パターンに場合分けができます。

パターン1
f:id:kuruton456:20200816143957j:plain

このときは、0以上の座標にある黄色丸の方が0に近いため、答えは $X$ を $D$ で割った余り（ $X\%D$ ）となります。

パターン2
f:id:kuruton456:20200816144009j:plain

このときは、0以下の座標にある黄色丸の方が0に近いため、答えは $X$ を $D$ で割った余りを $D$ から引いたもの（ $D-X\%D$ ）となります。

この2パターンのうちどちらに該当するかは、 $\lfloor{X}/D\rfloor$ と $K$ の偶奇が同じか、つまり $(\lfloor{X}/D\rfloor-K)\%2$ が0か1かによって判断することができます。

以上のことを実装すれば $O(1)$ で解くことができます。

サンプルコード

Pythonで書いた解答を載せておきます。

まとめ

今回は

対称性に注目する

答えの座標に対応して場合分けをする

という問題でした。

ではまたお会いしましょう！さようなら～