AtCoder Beginner Contest 175を見直す C - Walking Takahashi

C - Walking Takahashi

問題

数直線xにいる高橋君は、k回、正か負の方向にd移動することが出来ます。x、k、dが与えられるので原点に最も近づくように移動した場合の座標を答えなさい。

当日作成した解答

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;

int main() {
   ll x, k, d;
   cin >> x >> k >> d;
   x = abs(x);
   if( x >= k*d ) {
       cout << x - k*d << endl;
       return 0;
   }
   if((k - (x/d))%2 == 0) cout << x%d << endl;
   else cout << abs(x%d - d) << endl;
}

ループを回すこともなく結構シンプルにかけました。
最初のifは、k回d移動しても原点に到達しない場合の処理を行っています。k回d移動しても原点に到達しない場合は単純に以下の式で回答を求めることが出来ます。

原点からの距離（x） - （移動回数（d） ＊ 移動距離（k）

原点に到達する場合は原点を超えた直後、反復横跳び的に直前にいた場所に戻ることになります。そこで、まず原点を飛び越える直前の位置を求めます。原点を飛び越える直前の位置は以下の式で求めることが出来ます。

原点の直前 = 原点からの距離（x）% 移動距離（k）

さらに、最終地点が原点を超えた直後の座標なのか、超える直前の座標なのかを求めます、これは原点を超える直前の座標に到着した時点の残り移動回数から求めることが出来ます。

残り移動回数が偶数 ➡︎ 最終地点は超える直前の座標
残り移動回数が奇数 ➡︎ 最終地点は超えた直後の座標

原点を超える直前の座標に到着した時点の残り移動回数は以下の式で求めることが出来ます。

総移動回数（d） - 直前地点までの移動回数
直前地点までの移動回数 = 原点からの距離（x）// 移動距離（k）
# //は切り捨て除算

で、上記をまとめると以下のような条件分岐になります。

if((k - (x/d))%2 == 0) cout << x%d << endl;
else cout << abs(x%d - d) << endl;

ここまで、解説を書きましたが、実は上記のコードでは不正解です。

申し訳ないです。解説を見て修正したのが以下です。

解説を見て作成した解答

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;

int main() {
   ll x, k, d;
   cin >> x >> k >> d;
   x = abs(x);
   if( x/d >= k ) {
       cout << x - k*d << endl;
       return 0;
   }
   if((k - (x/d))%2 == 0) cout << x%d << endl;
   else cout << abs(x%d - d) << endl;
}

お分かり頂けただろうか。

最初の分岐の式が違っています。と言うのも制約条件を見ると以下のようになっており、

1 <= k, d < 10^15

k*dは64bitの整数型でもオーバーフローしてしまうからです。以下のように式変形しています。

x >= k*d
両辺をdで割る
x/d >= k*d/d
右辺のdが消える
x/d >= k

こうすることで、64bitの整数型でもオーバーフローすることなく利用することが出来ます。

オーバーフローで正解できなかったのは悔しいですが、次回以降の糧にしていこうと思います😭