AtCoder が提供しているABC（AtCoder Beginner Contest）305 のD問題をC++とPythonで解いてみました。ABC305は、2023年6月10日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Sleep Log（Difficulty : 671）
問題はリンク先をご覧ください。
睡眠時間の累積和を求めておいて、二分探索します。AtCoder Problems による Difficulty は 671 でした。
解答案
問題の構造を理解するために、入力例1を見てみましょう。この例は正解を促すための誘導になっていました。
7
0 240 720 1320 1440 1800 2160
3
480 1920
720 1200
0 2160これを図示したのが以下となります（図は問題から借用しました。）。
対応する正解は以下となります。
480
0
960- 480 = 240（720 － 480）+ 120（1440 ー 1320）+ 120（1920 ー 1800）
- 0 = 0
- 960 = 480（720 ー 240）+ 120（1440 ー 1320）+ 360（2160 ー 1800）
方針は、以下となります。
- 睡眠時間は、累積和で求めておく。
- Q個の質問に対して、以下を行う。
- 二分探索で、各質問の li と ri がある数列の場所を見つける。
- 左端と右端の処理を行い、睡眠時間を出力する。
C++ プログラム例（ABC305D）
睡眠時間を配列 s[i] に格納していきます（13-20行目）。s[i] は、a[i] までの睡眠時間を表します（添え字は0からとします）。
二分探索を用いて、読み込んだ L と R から、それ以上の最小の a[i] を求めます（28、29行目）。
左端と右端は、特別な処理が必要な場合があります。入力例1の最初のクエリを例にとります。
- 左は、720から480までの240分の睡眠時間を加える（33行目）。
- 右は、2160から1920までの240分の睡眠時間を減らす（36行目）。
s[indexR] ー s[indexL] は、960（2160までの睡眠時間の累積和） － 480（720までの睡眠時間の累積和） = 480 を表します（38行目）。結果的に、最初のクエリの回答 480 分を得ます。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<int> s(n, 0);
for (int i = 0; i < n - 1; ++i) {
if (i % 2 == 1) {
s[i + 1] = s[i] + (a[i + 1] - a[i]);
} else {
s[i + 1] = s[i];
}
}
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int L, R;
cin >> L >> R;
int indexL, indexR;
indexL = lower_bound(a.begin(), a.end(), L) - a.begin();
indexR = lower_bound(a.begin(), a.end(), R) - a.begin();
int result = 0;
if ((L != a[indexL])&&(indexL % 2 == 0)) {
result += a[indexL] - L;
}
if ((R != a[indexR])&&(indexR % 2 == 0)) {
result -= a[indexR] - R;
}
result += s[indexR] - s[indexL];
cout << result << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC305D）
Python では、二分探索 bisect を使いました。bisect::bisect_left が C++ の lower_bound と似た動きをします（16、17行目）。
"""AtCoder Beginner Contest 305 D"""
import bisect
n = int(input())
a = list(map(int, input().split()))
s = [0] * n
for i in range(n - 1):
if i % 2 == 1:
s[i + 1] = s[i] + (a[i + 1] - a[i])
else:
s[i + 1] = s[i]
q = int(input())
for i in range(q):
L, R = map(int, input().split())
indexL = bisect.bisect_left(a, L)
indexR = bisect.bisect_left(a, R)
result = 0
if L != a[indexL] and indexL % 2 == 0:
result += a[indexL] - L
if R != a[indexR] and indexR % 2 == 0:
result -= a[indexR] - R
result += s[indexR] - s[indexL]
print(result)こちらも「AC」と判定されました。
最後に
この問題は、前準備として累積和を求めておいて、二分探索をして解くことができました。知っている手法を組み合わせて、コンテスト中に解くことができ、うれしく感じました。
引き続き ABC の問題を紹介していきます。
