ABC175に参加してみた

初めに

ABC175はAB完でした。C問題はアルゴリズム云々って問題では無く、
問題を考察してシミュレーションするって形の問題だったんですが、回答出来ず、、、
アルゴリズムの学習をするのもそうですが、考察力も鍛えなきゃですね、、、 というわけでC問題について記載していきます。

https://atcoder.jp/contests/abc175

※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。

C - Walking Takahashi

ある座標XからK回移動した座標の絶対値が最小になるように移動する問題です。
移動可能な距離はDで正の方向と負の方向に移動する事が可能です。
(入力Kの最大値は10¹⁵なので愚直に計算していくと間に合いません。。。)

解説を見てからの回答

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const long long INF = 1LL<<60;

typedef pair<ll,ll> Pair;

int main(){

ll X,K,D;

cin >> X >> K >> D;

// 絶対値を設定
X = abs(X);

// 原点間の行き来が発生しないパターン
if(X/D >= K) cout << X - D*K << endl;
// 原点間の行き来が発生するパターン
else{
  K = K - X/D;
  X = X - D*(X/D);
  if(K % 2 == 1) X = X - D;
  cout << abs(X) << endl;
}

return 0;

}   

まずは、計算を楽にするためにXに入力された値の絶対値を格納します。
負の値が入力された場合は正の値に変更されますが、移動する際の操作が反転するだけなので
Xの絶対値で計算を行っても結果は変わりません。

イメージ

最小値を求めるためには、基本的にXから値を引いて行くことで最小値に値が近づいて行きます。
そして、操作を進めて行く原点を超えないパターンと、下記のように原点（0）を境に
行き来するようなパターンの2パターンが発生することが考えられます。

イメージ

そのため、原点を超えないパターンと原点を行き来するパターンで場合分けを行います。
場合分けはX/Dが移動回数Kを超えているかどうかで行います。

X/Dは「原点を超えずにXからDを引く事が出来る回数」を意味しており、
この値がKより大きかった場合は、K回引く操作を行っても原点を超えることは無いので
XからK回Dを引いた値(X - D*K)を出力します。

X/Dの値がKより小さかった場合は、原点を境に行き来するパターンとなります。
まずは、KからX/Dを引き「残りの操作回数」とXからD*(X/D)の値を引き
「X/D回移動した座標」を求めます。

さらにKが偶数か奇数かで場合分けを行い、偶数の場合は「X/D回移動した座標」に戻るため、
Xの値をそのまま表示し、奇数の場合は「X/D回移動した座標」からDを引いた値を表示します。

このような形で最小値を求める事が可能です。

最後に

うーん、完全に考察不足ですね。場合分けは思いついてたんで、
あとは偶数・奇数を利用すれば解けそうだなぁってとこまでは
当たりはついたんですが、回答には至りませんでしたね。。。
もうちょっと勉強時間ふやそうかなぁ、、、