【競プロ精進ログ】ABC175-C

zuka

ABCをコツコツ解いていきます。

本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。

これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。

本記事の概要

Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC175-C「Walking Takahashi」です。

ポイント

複数の場合分けが必要になる問題でした。まず， $X$ が負の場合と正の場合を考えなくてはなりません。しかし， $X$ が負の場合は， $X$ の代わりに $-X$ を考えてあげれば，対称性から $X$ が正の場合と全く同じ操作をすればOKです。ですので，以下では$X>0$として考えます。

zuka

自分は$X<0$もあり得るという条件を見逃していてペナルティを出しまくりました…。

続いて，$X<D$ の場合を考える必要があります。今いる座標より一回で移動する座標の方が大きければ，答えの候補は今いる座標 $X$か，そこから負の方向に$D$進んだ$|X-D|=D-X$になります。

ここで，移動する回数の偶奇を考えます。一般に「パリティ」なんて呼ばれているやつです。もし移動する回数$K$が偶数であれば，2つの候補のうち答えは必ず$X$になることがわかります。同様に，移動する回数$K$が奇数であれば，2つの候補のうち答えは必ず$|X-D|=D-X$になることがわかります。

さて，この問題のポイントは動ける回数が十分に多いときは「原点の両側を行ったり来たりする」ということに気付けるかどうかです。サンプルケースはあえて原点の両側でないところを行ったり来たりしていますが，結局はどこで帳尻を合わせるかの話ですので，あまり気にする必要はありません。一律で「原点の両側で」帳尻を合わせると考えればOKです。

つまり，答えの候補は原点の両側のうち$X % D$（右側）と$(X \% D) - D$（左側）となります。

zuka

実はさっきの$X<D$の場合は「すでに最初から原点の右側の候補地点にいた」という状況を表しているよね。

最終的にどちらに行き着くかは，先ほどと同じようにパリティを考えます。つまり，「原点の右端に移動した後に残り移動できる回数$Y$」の偶奇を考えます。$Y$が偶数のときは，答えは右端になります。一方で，$Y$が奇数のときは，答えは左端になります。

ですが，これは$X/D < K$のときに限ります。$X/D > K$の場合というのは，いまいる座標から原点に向かって$K$回移動しても，原点の右端である$X % D$にたどり着けないようなケースです。このような場合は，答えは$X - (K\times D)$となります。

実装

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

ll X, K, D;

int main(){
  cin >> X >> K >> D;

  // Xが負の場合には正負を逆転する
  if (X < 0) X *= -1;

  // X < Dの場合は最初から両端にいる
  // Kのパリティを考える
  if (X < D && K%2==1) cout << abs(X-D) << endl;
  else if (X < D && K%2==0) cout << X << endl;

  // 左側に突き進んでも原点の右側の候補地点にたどり着けない場合
  else if ((X/D) > K) cout << X - (K * D) << endl;

  // 十分に移動回数が多い場合
  else {
    // 右側の候補地点にたどり着いたあとに残っている移動回数のパリティを考える
    if ((K-(X/D))%2==0) cout << X%D << endl;
    else cout << abs((X%D)-D) << endl;
  }
}