この記事は拙著「AtCoder 凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185
前：https://qiita.com/sano192/items/002198d775b77e04cb40
次：https://qiita.com/sano192/items/a86795c3851db8a897b9
この問題からdifficultyが茶色(400～)になる。今灰色コーダーの人は苦戦するかもしれないが、頑張っていこう。
【目標】
・数直線を使った問題の解き方を身につける
【概要】
数直線上を移動するタイプの問題。数直線が登場する問題は頻出であるが、慣れないうちはどのように考えたらいいかすぐにわからないと思う。まずはこの問題で数直線問題の基礎を身に着けよう。
【方針】
問題に数直線が出てきたら必ず紙に数直線を書いて考える。
その際、X、Dなどの文字は使わずに具体例を使って考えるようにしよう。
絶対値を減らしたいという問題なのでともかく0に近づくように移動すればいいということはわかる。
(1)K回移動しても0にたどり着けないパターン
「例」
X=100
K=3
D=3
まず数直線を書き、0、100(=X)を書く。
ここから3回(=K)移動できる。3回とも0に向かって-3(=D)進むのが最善の移動方法だ。
答えは
|100-3*3|=91
書いた数直線を見ながら一般化して考えよう。
このパターンはXからK回0に向かってD移動しても0に到達できないパターン。
つまり
0<X-KD
(上記例でいうと0<100-33)
その場合答えは
|X-KD|
(上記例でいうと|100-33=91|)
で表せる。
Xがマイナスの場合は最初にXの絶対値を取ってプラスに変換してしまえば良い。
例えば
X=-100
K=3
D=3
の場合、
-100から0に向かって3回+3移動するため答えは
|-100+3*3|=91
で、X=100の場合(=Xの絶対値を取ってプラスに変換した場合)と変わらない。
(2)K回移動する途中で0にたどり着くパターン
「例」
X=10
K=10
D=3
まず数直線を書き、0、10(=X)を書く。
3回の移動で10-3*3＝1に移動できる。
しかし4回目、-3移動して0を飛び越え、-2に到着してしまう。
-2に到着したら今度は+3移動して1に到着する。
1に到着したら-3移動して-2に到着する。
つまり3回目の移動で1に到着した後の座標は
1→-2→1→-2→1…
となり
「0を飛び越える直前の座標」=1
と
「0を飛び越えた直後の座標」=-2
を行ったり来たりする。
では最終的に1と-2のどちらの座標になるか。
これは残りの移動回数から計算できる。
「0を飛び越える直前の座標」=1に至るまでの移動回数は3回。
つまり1にたどり着いた時点で残り操作回数は10-3=7回。
このあと7回、-2と1を行ったり来たりする。7，6，5，4，3，2，1、0と順番に数えてみれば最終的な座標は-2になることがわかる。
答えは|-2|=2。
書いた数直線を見ながら一般化して考えよう。
このパターンはK回移動する途中で0にたどり着くパターン。
つまり
X-KD<=0
(上記例でいうと10-103<=0)
0を飛び越える直前までの移動回数=X//D
(上記例でいうと10//3=3)
「0を飛び越える直前の座標」=X-(X//D)*D。
(上記例でいうと10-(10//3)3=10-33=1)
「0を飛び越えた直後の座標」=「0を飛び越える直前の座標」-D
(上記例でいうと1-3=-2)
残りの移動回数=K-X//D
(上記例でいうと10-(10//3)=10-3=7)
残りの移動回数が
偶数→答えは「0を飛び越える直前の座標」の絶対値
奇数→答えは「0を飛び越えた直後の座標」の絶対値
【実装】
入力を受け取る。
X,K,D=map(int, input().split())
Xがマイナスの場合はプラスに変換したい。
if X<0:X*=-1
と書いても良いが面倒なのでabsで絶対値を取ってしまえば良い。
X=abs(X)
(1)K回移動しても0にたどり着けないパターン
・0<X-KDのパターン
答えは
|X-KD|(この絶対値はなくてもOK)
if 0<X-K*D:
print(abs(X-K*D))
(2)K回移動する途中で0にたどり着くパターン
・(1)以外(X-K*D<=0)の場合
まず「0を飛び越える直前の座標」まで来たときの残り操作回数(K-X//D)を計算する。
else:
move_count=K-X//D
次に
「0を飛び越える直前の座標」(X-(X//D)*D)
「0を飛び越えた直後の座標」(「0を飛び越える直前の座標」-D)
を計算する。
jump_before=X-D*(X//D)
jump_after=jump_before-D
残り移動回数が
偶数→答えは「0を飛び越える直前の座標」の絶対値
奇数→答えは「0を飛び越えた直後の座標」の絶対値
if move_count%2==0:
print(abs(jump_before))
else:
print(abs(jump_after))
【コード全文】
X,K,D=map(int, input().split())
X=abs(X)
if 0<X-K*D:
print(abs(X-K*D))
else:
move_count=K-X//D
jump_before=X-D*(X//D)
jump_after=jump_before-D
if move_count%2==0:
print(abs(jump_before))
else:
print(abs(jump_after))
この記事は拙著「AtCoder 凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185
前：https://qiita.com/sano192/items/002198d775b77e04cb40
次：https://qiita.com/sano192/items/a86795c3851db8a897b9