AtCoder が提供しているABC（AtCoder Beginner Contest）347 のC問題をC++とPythonで解いてみました。ABC347は、2024年3月30日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Ideal Holidays（Difficulty : 926）
問題はリンク先をご覧ください。
予定の日の固まりが休日に収まるか調べます。AtCoder Problems による Difficulty は 926 でした。
解答案
予定がある日の $(A + B)$ との余りを求めて、それの最大値と最小値の差が休日に収まればよいと考えていました。ただし、以下のような場合があります。
休日を4日、平日を2日とします。予定がある日を1日後と5日後とします。この場合、6との余りを求めると、1と5になります。これは休日の4日間には入りません。一方、今日を3日とすると、
1日後＝4日（休日）、5日（平日）、6日（平日）、7日（休日）、5日後＝8日（休日）
となり、どちらも休日に収まります。1日後は6を加えた7日後と同一視できています（1日後を7日後と考えると、同じ曜日となります）。
C++ プログラム例（ABC347C）
上記のような場合にも対応するため、以下の手順で処理しました。
- 予定のある日 d[i] を読み込み、(a + b) との余りを求める（14行目）。
- ソートして、余りの日を後ろに (a + b) を加えながら加える（18行目）。
- d[i + N – 1] – d[i] の最小値を求める。
- この最小値に1を加えたものが求める解になります。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define INF (1ULL << 60)
int main()
{
ll n, a, b;
cin >> n >> a >> b;
vector<ll> d(n);
for (int i = 0; i < n; ++i) {
cin >> d[i];
d[i] = d[i] % (a + b);
}
sort(d.begin(), d.end());
for (int i = 0; i < n; ++i) {
d.push_back(d[i] + a + b);
}
ll t = INF;
for (int i = 0; i < n; ++i) {
t = min(t, d[i + n - 1] - d[i] + 1);
}
if (t <= a) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC347C）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 347 C"""
INF = 1 << 60
n, a, b = map(int, input().split())
d = list(map(int, input().split()))
for i in range(n):
d[i] = d[i] % (a + b)
d.sort()
for i in range(n):
d.append(d[i] + a + b)
t = INF
for i in range(n):
t = min(t, d[i + n - 1] - d[i] + 1)
print("Yes" if t <= a else "No")こちらも「AC」と判定されました。
最後に
コンテスト中にWA（Wrong Answer）判定をもらって、ロジックのミスに気が付きました。最初から正しく解けるようになればと思います。
引き続き ABC の問題を紹介していきます。
