【AtCoder】ABC 334 B - Christmas Trees | 茶コーダーが解くAtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 479

問題概要

東西に無限に伸びる道路があり、この道路のある点を基準にして東へ $x \mathrm{\, m}$ 進んだところにある地点の座標を $x$ とする。ここで、座標が $A$ である地点を基準にして東西方向に $M \mathrm{\, m}$ おきにクリスマスツリーを立てる。高橋君と青木君がそれぞれ座標が $L, R$ の地点に立っているとき、2人の間 (両社が立っている地点を含む) に立てられるクリスマスツリーの本数を求めよ。

制約

入力はすべて整数。
$-10^{18} \leq A, L, R \leq 10^{18}$
$L \leq R$
$1 \leq M \leq 10^9$

考察

この問題は数式で考えていくと見通しが良くなる。

元の問題文に、「ある整数 $k$ に対して、座標が $A + kM$ となるような地点にクリスマスツリーを立てる」とあるので、以下の不等式が成り立つ。

\begin{align*}
L \leq A + kM \leq R
\end{align*}

この不等式を満たす $k$ の個数が求めるクリスマスツリーの本数である。以下、同値変形を行うと、

\begin{align*}
L \leq A + kM \leq R & \iff \dfrac{L-A}{M} \leq k \leq \dfrac{R-A}{M} \\
& \iff \biggl\lceil \dfrac{L-A}{M} \biggr\rceil \leq k \leq \biggl\lfloor \dfrac{R-A}{M} \biggr\rfloor \: (\because k \in \mathbb{Z})
\end{align*}

なお、 $\lfloor \cdot \rfloor$ は切り捨てを表す床関数、 $\lceil \cdot \rceil$ は切り上げを表す天井関数である。

この式を満たす $k$ の個数は $\biggl\lfloor \dfrac{R-A}{M} \biggr\rfloor - \biggl\lceil \dfrac{L-A}{M} \biggr\rceil + 1$ で求められる。

あとはこれをプログラムに落とし込めばよい。床関数、天井関数の C++ における実装は以前に別の記事で紹介した。

yuulis.hatenablog.com

コード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

template <class T1, class T2>
inline auto div_floor(T1 a, T2 b)
{
    if (b < 0)
        a *= -1, b *= -1;
    if (a >= 0)
        return a / b;
    else
        return (a + 1) / b - 1;
}
template <class T1, class T2>
inline auto div_ceil(T1 a, T2 b)
{
    if (b < 0)
        a *= -1, b *= -1;
    if (a <= 0)
        return a / b;
    else
        return (a - 1) / b + 1;
}

// ======================================== //

int main()
{
    ll A, M, L, R;
    cin >> A >> M >> L >> R;

    cout << div_floor(R - A, M) - div_ceil(L - A, M) + 1 << endl;
}