AtCoder

ABC305 D問題(Sleep Log)を解く

AtCoder_ABC305_D

AtCoder が提供しているABC(AtCoder Beginner Contest)305 のD問題をC++とPythonで解いてみました。ABC305は、2023年6月10日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

D問題 Sleep Log(Difficulty : 671)

問題はリンク先をご覧ください。

ABC305 D問題 Sleep Log

睡眠時間の累積和を求めておいて、二分探索します。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」と判定されました。

最後に

この問題は、前準備として累積和を求めておいて、二分探索をして解くことができました。知っている手法を組み合わせて、コンテスト中に解くことができ、うれしく感じました。

ABC305 について、引き続き問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA