Language: C++

<!-- wp:block {"ref":262} /-->

<!-- wp:loos/balloon {"balloonID":"80","balloonTitle":"zuka"} -->
<div class="swell-block-balloon">[ふきだし set="zuka"]<p>ABCをコツコツ解いていきます。</p>[/ふきだし]</div>
<!-- /wp:loos/balloon -->

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

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

<!-- wp:loos/button {"hrefUrl":"https://cod-aid.com/atcoder-toc","className":"is-style-btn_solid"} -->
<div class="swell-block-button is-style-btn_solid"><a class="swell-block-button__link" href="https://cod-aid.com/atcoder-toc">目次へジャンプ[icon class="icon-more_arrow"]</a></div>
<!-- /wp:loos/button -->

<!-- wp:heading -->
<h2>本記事の概要</h2>
<!-- /wp:heading -->

<!-- wp:paragraph -->
<p>Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回は<a href="https://atcoder.jp/contests/abc175/tasks/abc175_c" target="_blank" rel="noreferrer noopener">ABC175-C「Walking Takahashi」</a>です。</p>
<!-- /wp:paragraph -->

<!-- wp:heading -->
<h2>ポイント</h2>
<!-- /wp:heading -->

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

<!-- wp:loos/balloon {"balloonID":"80","balloonTitle":"zuka"} -->
<div class="swell-block-balloon">[ふきだし set="zuka"]<p>自分は$X&lt;0$もあり得るという条件を見逃していてペナルティを出しまくりました…。</p>[/ふきだし]</div>
<!-- /wp:loos/balloon -->

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

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

<!-- wp:separator {"color":"swl-main"} -->
<hr class="wp-block-separator has-text-color has-background has-swl-main-background-color has-swl-main-color"/>
<!-- /wp:separator -->

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

<!-- wp:paragraph -->
<p>つまり，答えの候補は原点の両側のうち$X % D$（右側）と$(X % D) - D$（左側）となります。</p>
<!-- /wp:paragraph -->

<!-- wp:loos/balloon {"balloonID":"80","balloonTitle":"zuka"} -->
<div class="swell-block-balloon">[ふきだし set="zuka"]<p>実はさっきの$X&lt;D$の場合は「すでに最初から右端にいた」という状況を表しているよね。</p>[/ふきだし]</div>
<!-- /wp:loos/balloon -->

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

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

<!-- wp:loos/cap-block {"className":"is-style-default"} -->
<div class="swell-block-capbox cap_box is-style-default"><div class="cap_box_ttl">おさえるべき内容</div><div class="cap_box_content"><!-- wp:paragraph -->
<p>[icon class="icon-check"]　パリティの利用</p>
<!-- /wp:paragraph --></div></div>
<!-- /wp:loos/cap-block -->

<!-- wp:heading -->
<h2>実装</h2>
<!-- /wp:heading -->

<!-- wp:loos-hcb/code-block {"langType":"cpp","langName":"C++"} -->
<div class="hcb_wrap"><pre class="prism undefined-numbers lang-cpp" data-lang="C++"><code>#include &lt;bits/stdc++.h&gt;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i &lt; (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i &lt; (int)(b); i++)
using namespace std;
typedef long long ll;

ll X, K, D;

int main(){
  cin &gt;&gt; X &gt;&gt; K &gt;&gt; D;

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

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

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

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

Compiler output:
a.cc:4:58: error: extended character 。 is not valid in an identifier
    4 | <div class="swell-block-balloon">[ふきだし set="zuka"]<p>ABCをコツコツ解いていきます。</p>[/ふきだし]</div>
      |                                                          ^
a.cc:8:4: error: extended character 。 is not valid in an identifier
    8 | <p>本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。</p>
      |    ^
a.cc:8:4: error: extended character 。 is not valid in an identifier
a.cc:12:4: error: extended character 。 is not valid in an identifier
   12 | <p>これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。</p>
      |    ^
a.cc:12:4: error: extended character 。 is not valid in an identifier
a.cc:24:70: error: extended character 。 is not valid in an identifier
   24 | <p>Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回は<a href="https://atcoder.jp/contests/abc175/tasks/abc175_c" target="_blank" rel="noreferrer noopener">ABC175-C「Walking Takahashi」</a>です。</p>
      |                                                                      ^
a.cc:24:225: error: extended character 「 is not valid in an identifier
   24 | <p>Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回は<a href="https://atcoder.jp/contests/abc175/tasks/abc175_c" target="_blank" rel="noreferrer noopener">ABC175-C「Walking Takahashi」</a>です。</p>
      |                                                                                                                                                                                                                                 ^
a.cc:24:236: error: extended character 」 is not valid in an identifier
   24 | <p>Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回は<a href="https://atcoder.jp/contests/abc175/tasks/abc175_c" target="_blank" rel="noreferrer noopener">ABC175-C「Walking Takahashi」</a>です。</p>
      |                                                                                                                                                                                                                                            ^
a.cc:24:251: error: extended character 。 is not valid in an identifier
   24 | <p>Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回は<a href="https://atcoder.jp/contests/abc175/tasks/abc175_c" target="_blank" rel="noreferrer noopener">ABC175-C「Walking Takahashi」</a>です。</p>
      |                                                                                                                                                                                                                                                           ^
a.cc:32:4: error: extended character 。 is not valid in an identifier
   32 | <p>複数の場合分けが必要になる問題でした。まず， $X$ が負の場合と正の場合を考えなくてはなりません。しかし， $X$ が負の場合は， $X$ の代わりに $-X$ を考えてあげれば，対称性から $X$ が正の場合と全く同じ操作をすればOKです。ですので，以下では$X>0$として考えます。</p>
      |    ^
a.cc:32:53: error: extended character 。 is not valid in an identifier
   32 | <p>複数の場合分けが必要になる問題でした。まず， $X$ が負の場合と正の場合を考えなくてはなりません。しかし， $X$ が負の場合は， $X$ の代わりに $-X$ を考えてあげれば，対称性から $X$ が正の場合と全く同じ操作をすればOKです。ですので，以下では$X>0$として考えます。</p>
      |                                                     ^
a.cc:32:180: error: extended character 。 is not valid in an identifier
   32 | <p>複数の場合分けが必要になる問題でした。まず， $X$ が負の場合と正の場合を考えなくてはなりません。しかし， $X$ が負の場合は， $X$ の代わりに $-X$ を考えてあげれば，対称性から $X$ が正の場合と全く同じ操作をすればOKです。ですので，以下では$X>0$として考えます。</p>
      |                                                                                                                                                                                    ^
a.cc:32:241: error: extended character 。 is not valid in an identifier
   32 | <p>複数の場合分けが必要になる問題でした。まず， $X$ が負の場合と正の場合を考えなくてはなりません。しかし， $X$ が負の場合は， $X$ の代わりに $-X$ を考えてあげれば，対称性から $X$ が正の場合と全く同じ操作をすればOKです。ですので，以下では$X>0$として考えます。</p>
      |                                                                                                                                                                                                                                                 ^
a.cc:36:70: error: extended character … is not valid in an identifier
   36 | <div class="swell-block-balloon">[ふきだし set="zuka"]<p>自分は$X&lt;0$もあり得るという条件を見逃していてペナルティを出しまくりました…。</p>[/ふきだし]</div>
      |                                                                      ^
a.cc:36:70: error: extended character 。 is not valid in an identifier
a.cc:40:21: error: extended character 。 is not valid in an identifier
   40 | <p>続いて，$X&lt;D$ の場合を考える必要があります。今いる座標より一回で移動する座標の方が大きければ，答えの候補は今いる座標 $X$か，そこから負の方向に$D$進んだ$|X-D|=D-X$になります。</p>
      |                     ^
a.cc:40:167: error: extended character 。 is not valid in an identifier
   40 | <p>続いて，$X&lt;D$ の場合を考える必要があります。今いる座標より一回で移動する座標の方が大きければ，答えの候補は今いる座標 $X$か，そこから負の方向に$D$進んだ$|X-D|=D-X$になります。</p>
      |                                                                                                                                                                       ^
a.cc:44:4: error: extended character 。 is not valid in an identifier
   44 | <p>ここで，移動する回数の偶奇を考えます。一般に「パリティ」なんて呼ばれているやつです。もし移動する回数$K$が偶数であれば，2つの候補のうち答えは必ず$X$になることがわかります。同様に，移動する回数$K$が奇数であれば，2つの候補のうち答えは必ず$|X-D|=D-X$になることがわかります。</p>
      |    ^
a.cc:44:4: error: extended character 「 is not valid in an identifier
a.cc:44:4: error: extended character 」 is not valid in an identifier
a.cc:44:4: error: extended character 。 is not valid in an identifier
a.cc:44:4: error: extended character 。 is not valid in an identifier
a.cc:44:248: error: extended character 。 is not valid in an identifier
   44 | <p>ここで，移動する回数の偶奇を考えます。一般に「パリティ」なんて呼ばれているやつです。もし移動する回数$K$が偶数であれば，2つの候補のうち答えは必ず$X$になることがわかります。同様に，移動する回数$K$が奇数であれば，2つの候補のうち答えは必ず$|X-D|=D-X$になることがわかります。</p>
      |                                                                                                                                                                                                                                                        ^
a.cc:52:4: error: extended character 「 is not valid in an identifier
   52 | <p>さて，この問題のポイントは動ける回数が十分に多いときは「原点の両側を行ったり来たりする」ということに気付けるかどうかです。サンプルケースはあえて原点の両側でないところを行ったり来たりしていますが，結局はどこで帳尻を合わせるかの話ですので，あまり気にする必要はありません。一律で「原点の両側で」帳尻を合わせると考えればOKです。</p>
      |    ^
a.cc:52:4: error: extended character 」 is not valid in an identifier
a.cc:52:4: error: extended character 。 is not valid in an identifier
a.cc:52:4: error: extended character 。 is not valid in an identifier
a.cc:52:4: error: extended character 「 is not valid in an identifier
a.cc:52:4: error: extended character 」 is not valid in an identifier
a.cc:52:4: error: extended character 。 is not valid in an identifier
a.cc:56:68: error: extended character 。 is not valid in an identifier
   56 | <p>つまり，答えの候補は原点の両側のうち$X % D$（右側）と$(X % D) - D$（左側）となります。</p>
      |                                                                    ^
a.cc:60:76: error: extended character 「 is not valid in an identifier
   60 | <div class="swell-block-balloon">[ふきだし set="zuka"]<p>実はさっきの$X&lt;D$の場合は「すでに最初から右端にいた」という状況を表しているよね。</p>[/ふきだし]</div>
      |