AtCoder が提供しているABC（AtCoder Beginner Contest）325 のB問題をC++とPythonで解いてみました。ABC325は、2023年10月21日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 World Meeting（Difficulty : 171）
問題はリンク先をご覧ください。
世界標準時について全探索します。AtCoder Problems による Difficulty は、171 でした。
解答案
世界標準時 $i$ 時は、各拠点 $j$ で $i + X_j \pmod{24}$ 時となります。各拠点において 9:00-18:00 の時間帯に1時間の会議を開くためには、会議の開始時間が $9 \leqq i + X_j \leqq 17\pmod{24}$ である必要があります。
世界標準時 0 時から 23 時までの24通りを会議の開始時間として、各拠点が参加できるか判定して、参加人数の合計の最大値を求めます。
C++ プログラム例（ABC325B）
上で整理したことをプログラムにしました。以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> w(n), x(n);
for (int i = 0; i < n; ++i) {
cin >> w[i] >> x[i];
}
int result = 0;
for (int i = 0; i < 24; ++i) {
int sanka = 0;
for (int j = 0; j < n; ++j) {
int t = (i + x[j]) % 24;
if ((9 <= t)&&(t <= 17)) {
sanka += w[j];
}
}
result = max(result, sanka);
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC325B）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 325 B"""
n = int(input())
w = [0] * n
x = [0] * n
for i in range(n):
w[i], x[i] = map(int, input().split())
result = 0
for i in range(24):
sanka = 0
for j in range(n):
t = (i + x[j]) % 24
if 9 <= t <= 17:
sanka += w[j]
result = max(result, sanka)
print(result)こちらも「AC」と判定されました。
最後に
B問題やC問題は、全探索を考える場合が多いです。時間と拠点がありますが、今回は時間を全探索して解きました。
引き続き ABC の問題を紹介していきます。
