AtCoder Beginner Contest 175 Task C - Walking Takahashi の解説(Python)

はじめに

最近、競プロをはじめたばかりですが、AGC175-C問題で圧倒的に簡潔なPyPy3解答が提出されており驚嘆しました。
しかし、読み解くのにかなりの時間を要したので忘れないうちに投稿しておきます。

※Safariやスマホで見るとMathjaxの数式の箇所でレイアウト崩れが起きるようです。気になる方はPC版のChromeでご覧ください。
訂正：2020/8/19 -> コメントを受けて一部文言をより正確な記述に変更

問題

数直線上で暮らす高橋君は、今座標$X$にいます。これから高橋君はちょうど$K$回、座標の正または負の方向に$D$移動する行為を繰り返そうと考えています。
より正確には、$1$回の移動では 座標$x$から$x+D$または$x−D$に移動できます。
高橋君は、ちょうど$K$回移動した後にいる座標の絶対値が最小となるように移動したいです。
$K$回の移動後の座標の絶対値としてあり得る値の最小値を求めてください。

制約

• $-10^{15}≤X≤10^{15}$
• $1≤K≤10^{15}$
• $1≤D≤10^{15}$
• 入力は全て整数である

解答

PyPy3で最小バイト数となるAC例です。c_r_5さんという方の回答になります。

最小バイト数AC解答

x,k,d=map(int,input().split())
print(max(abs(x)-k*d,(x%d,d-x%d)[k-x//d&1]))

2行ってヤバくないですか。入力除けば単文ですよ。
いろいろこねくり回してようやくTLEを回避した身としては、見た瞬間卒倒するかと思いました。

解説

$K$が大きいので、現在座標$x$に対し、$+D$と$-D$で移動後の$|x|$が小さい方を取得していくというゴリ押しの貪欲解だと余裕でTLEになります。
したがって、このやり方は当然除いて考えます。個人的には$K$が小さいならこのやり方でいいと思います。

X≧0かつ移動回数の制約を除いて考える

与えられる$X$に正負がありますが、最終的に出力するのは絶対値で、正負を反転させても同じ答えになります。
したがって、単純化して$X$が正の場合のみを考えていきます。また、考える内容を減らしたいので、さらに$K$に制限がない場合のみを考えてみましょう。

すると、最初の位置$X$から、ひたすら原点$O$に向かうことだけを考えればよいということが分かります。

正の方向から$-D$だけ移動を繰り返して“原点を追い越す直前”で止まったときの位置は$X \bmod D$です。
これは、$X$から引けるだけ$D$を引いたときの余りなので、理解できると思います。

一瞬、$X<D$かどうかで場合分けを考えてしまいますが、$X \bmod D=X$なので分ける必要はありません。
また、ちょうど割り切れたなら$0$です。

原点をいったん通り越したら

さて、ここからもう$1$度だけ$D$を引いた場合の位置はどうなるでしょうか。
$(X \bmod D)-D$ですね。これは単純に$D$を引いただけです。

となると、$K$に回数制限がないのなら$(X \bmod D)-D$と$X \bmod D$の絶対値の大小を比較して小さい方を選べばよいことが分かります。また、剰余の性質を考えれば$(X \bmod D)<D$のため、$\left| (X \bmod D)-D\right| =D-(X\bmod D)$です。

移動回数Kの制約について考える

実際には$K$に制限があるため、

• 原点を追い越す直前の位置まで到達できない
• 直前の位置まで到達できても移動回数が余っている

という可能性を考慮する必要があります。つまり、$K$が足りなかったり$K$が余ったりします。

Kが足りない場合

これは、一心不乱に原点$O$に向かっている途中で残機がなくなるという状況です。
つまり$-D$の移動を$K$回繰り返した後なので、最終的な位置$x$は、$x=X-KD$で表せます。

Kが余る場合

原点の直前位置まで到達したときに移動回数が余っている場合です。
少し考えると、原点をまたぐ往復移動をひたすら繰り返すしかないことが分かります。

さらに考えると、最初に$X \bmod D$まで到達したときに、残りの回数が偶数か奇数かで場合分けになります。

• 偶数回なら最終位置は$X \bmod D$
• 奇数回なら最終位置は$D-(X \bmod D)$

これで全ての場合分けが完了しました。

原点の直前位置まで行くのに必要な移動回数

次に、場合分けを実装するにあたり、原点直前まで到達するのに必要な移動回数を求めていきます。
必要な移動回数$k$は、最初の位置から原点直前に到達した位置を引いたものを$D$で割ればよいです。したがって、以下の式です。
$\displaystyle k=\frac{X-(X\bmod D)}{D}$

これは、$X$を$D$で割ったときの商（整数部分）ですから、$X$が正であれば、Pythonでは以下のように記述できます。

# 以下のように書ける（正の数なら「X/D」の小数点切り捨て）
X//D

# 負数の場合は注意が必要！
print(5//3)   # ->  1
print(-5//3)  # -> -2

# 小数点含みの除算の結果を「超えない」最大の整数となる
#  5/3 =  1.66666... ≧ 1
# -5/3 = -1.66666... ≧ -2

愚直な解答

では、上記の内容を素直に実装してみます（下記でACを確認しています）。

愚直解

x,k,d = map(int,input().split())
x = abs(x)
if x//d > k:
  print(x-k*d)
elif (k-x//d)%2 == 0:
  print(x%d)
else:
  print(d-x%d)

最短解に近づける

さて、上記で解けることは確認したので、これをいかに美しく書くかということが残る課題になります。
1行目は同じなので省略します。これ以上は、短くしようもないと思います。

k-x//dの場合分けをタプル化する

if (k-x//d)%2 == 0:
  print(x%d)
else:
  print(d-x%d)

これをタプルとビット演算で書き直します。

# 偶数か奇数かを判定する -> &1でビット演算する
print((x%d,d-x%d)[k-x//d&1])

# 【補足】演算子の優先順位
# (%,*,@,/,//) -> (+,-) -> &
# 乗除系 -> 加減系 -> ビットAND

どういうことか2進数を見てみましょう。

# 0 ->    0b0
# 1 ->    0b1
# 2 ->   0b10
# 3 ->   0b11
# 4 ->  0b100
# 5 ->  0b101
# 6 ->  0b110
# 7 ->  0b111
# 8 -> 0b1000
# 9 -> 0b1001

# -> 2進数で奇数の末尾は1

つまり1とANDをとると、末尾以外は必ず0となり、奇数か偶数かで1または0が返ることが分かります。

Kが余る場合と足りない場合の場合分けをmaxで行う

さらに考えていくと、最初の場合分けに使っているx-k*dの値は$K$が足りない場合はプラスの座標、余る場合は通り越してマイナスの座標となります。この大小関係を使って場合分けを実装できます。

というのも、先ほどの(x%d,d-x%d)[k-x//d&1]がどちらで評価されたとしても、$K$が足りない場合はx-k*dの方が大きくなります。
逆に、$K$が余る場合もx-k*dは必ず(x%d,d-x%d)[k-x//d&1]以下になります。

式の値は、境界条件であるx-k*d == x%dとなる場合に最大を取り、それ以降どれだけ$K$が増えても(x%d,d-x%d)[k-x//d&1]より大きくなることはありません。

したがって、以下のように整理できます。

x,k,d=map(int,input().split())
x = abs(x)
print(max(x-k*d,(x%d,d-x%d)[k-x//d&1]))

x = abs(x)もついでに消す

ここまで来たら、x = abs(x)とかいうダサい行も消したいですね。
安心してください。ちゃんと消せます。

要するに$X$が負でも成り立つことを証明すればOKです。つまり、以下を言いたいということになります。

(x%d,d-x%d)[k-x//d&1] == ((-x)%d,d-(-x)%d)[k-(-x)//d&1]
# xの正負が反転しても同じ結果になっていればよい

結論を書いていくと、以下のようになるので負の場合も成り立ちます。

# x%d!=0の場合
(-x)%d == d-x%d
# Pythonの剰余は除数の正負と剰余の符号が一致する
# 符号以外は非負最小剰余に則り実装されている（C言語などは絶対値最小剰余で実装されている）

# 上の関係を用いれば d-(-x)%d == d-(d-x%d) より
d-(-x)%d == x%d  #ちょうど入れ替わった！

# x%d != 0の場合は以下を満たす
(-x)//d == -(x//d)-1

# つまり、必ず1ズレるので偶奇は反転する
k-(-x)//d&1 != k-x//d&1

# 【補足】EvenとOddを考えると、以下が成り立つ
# A + B = Cのとき、
# isEven(A) XOR isEven(B) == isEven(C)

# 一方で、x%d == 0の場合
(x%d,d-x%d)[k-x//d&1] == ((-x)%d,d-(-x)%d)[k-(-x)//d&1]  # 元の式が
(0,d)[k-x//d&1] == (0,d)[k-x//d&1]  # こうなる（両辺同じものになる）

結局、Xが負になっても、そっくりそのまま順序が反転するので成り立つということがよ〜〜く考えると分かります。
したがって、絶対値が必要なのはabs(x)-k*dの部分のみとなり、最初の式が得られます。

最小バイト数AC解答

x,k,d=map(int,input().split())
print(max(abs(x)-k*d,(x%d,d-x%d)[k-x//d&1]))

いや、理解するのにめちゃくちゃ時間かかりました。精進します。