AtCoder が提供しているABC（AtCoder Beginner Contest）334 のB問題をC++とPythonで解いてみました。ABC334は、2023年12月23日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 Christmas Trees（Difficulty : 479）
問題はリンク先をご覧ください。
L と R の正負で場合分けして解きました。AtCoder Problems による Difficulty は 479 でした。
解答案
最初に L と R から A を引いて、A を原点と考えます。この変換によって [L, R] 間に含まれる k × M の個数をカウントする問題になります。この記事で割り算は、切り捨てとします。多くのプログラミング言語で、整数同士の割り算は切り捨てになります。
最初に、L が負、R が正の場合を考えます。
- R と 0 の間には、R / M 個ある。ここで、R は含みます。0は含みません。
- L と 0 の間には、-L / M 個ある。ここで、L は含みます。0は含みません。
- 0 は該当する。
この場合は、上記3通りの和となります。
次に 0 ≦ L ≦ R の場合を考えます。
- R と 0 の間には、R / M 個ある。ここで、R は含みます。0は含みません。
- L と 0 の間には、L / M 個ある。ここで、L は含みます。0は含みません。
上記の差を取ると、L が k × M となっている場合は、1個引きすぎています。このため、L が M の倍数になっている場合（0の場合も含む）は、1個加えます。
最後に L ≦ R ≦ 0 の場合を考えます。この場合は、R’ = -L、L’ ＝-R とすると、上記の 0 ≦ L’ ≦ R’ に帰着します。
C++ プログラム例（ABC334B）
上記の考察をそのまま実装にしました。以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
ll a, m, L, R;
cin >> a >> m >> L >> R;
L -= a;
R -= a;
ll result = 0;
if ((L < 0)&&(0 < R)) {
result = (-L) / m + R / m + 1;
} else if (L >= 0) {
result = R / m - L / m;
if (L % m == 0) {
++result;
}
} else {
result = (-L) / m - (-R) / m;
if ((-R) % m == 0) {
++result;
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC334B）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 334 B"""
a, m, L, R = map(int, input().split())
L -= a
R -= a
result = 0
if L < 0 < R:
result = (-L) // m + R // m + 1
elif L > 0:
result = R // m - L // m
if L % m == 0:
result += 1
else:
result = (-L) // m - (-R) // m
if (-R) % m == 0:
result += 1
print(result)こちらも「AC」と判定されました。
最後に
B問題としては、難しい問題だったと思います。
公式解説では、計算の工夫により、すっきりとしたプログラムになっていました。この記事のプログラムは、場合分けによって長くなっています。ただし、わたしの思考の過程を書いた方が分かりやすいと考えて、このまま紹介しました。
引き続き ABC の問題を紹介していきます。
