🔖

【競技プログラミング】AtCoder Beginner Contest 305_D問題

2024/12/31に公開

 問題https://atcoder.jp/contests/abc305/tasks/abc305_d

 要約睡眠記録は奇数長の数列A=(A1(=0), A2, ..., An)で表される。
睡眠パターンは以下の通り
奇数番目の要素は起床時刻、偶数番目の要素は就寝時刻を表す。
1 ≤ i ≤ (N-1)/2 を満たす整数iについて、A2i分後に寝て、A_2i+1分後に起きる。
それ以外の時間は寝ることも起きることもない。
Q個の質問に答える。

各質問iでは、0 ≤ li ≤ ri ≤ Anを満たす整数の組(li, ri)が与えられる。
(ri - li)分間のうち、高橋くんが寝ていた時間は何分間か？
N: 睡眠記録の数列の長さ（奇数）
A: 睡眠記録を表す数列
Q: 質問の数
li, ri: i番目の質問で与えられる時間範囲

 既存投稿一覧ページへのリンク一覧ページ

 アプローチ累積睡眠時間を計算する。
二分探索を用いて、指定された時間に対応する睡眠時間を効率的に求める。
各質問に対して、指定された時間範囲の睡眠時間を計算する。

 解法手順入力を受け取る：睡眠記録の長さ N と睡眠記録 A を読み込む。
累積睡眠時間 R を計算する：
R[0] = 0 とする。
奇数インデックスでは前の値をそのまま使用（起床時刻なので睡眠時間は増えない）。
偶数インデックスでは、前の値に睡眠時間（A[i] - A[i-1]）を加算する。
時刻 x における累積睡眠時間を計算する関数 f(x) を定義する：
二分探索で x が含まれる区間を特定する。
区間が奇数番目（起床中）なら、その直前までの睡眠時間を返す。
区間が偶数番目（睡眠中）なら、その区間の開始時刻からの経過時間を加算して返す。
質問の数 Q を読み込む。
各質問に対して：
l と r を読み込む。
f(r) - f(l) を計算して出力する。これが、l から r までの間の睡眠時間となる。

 ACコードac.py
import bisect

def io_func():
    # 睡眠記録の長さNと睡眠記録Aを読み込む
    N = int(input())
    A = list(map(int, input().split()))
    
    # 質問の数Qを読み込む
    Q = int(input())
    
    # 各質問のlとrを読み込む
    queries = [list(map(int, input().split())) for _ in range(Q)]
    
    return N, A, Q, queries

def solve(N, A, Q, queries):
    # 累積睡眠時間Rを計算する
    R = [0]
    for i in range(1, N):
        if i % 2 == 1:
            # 奇数インデックスでは前の値をそのまま使用
            R.append(R[-1])
        else:
            # 偶数インデックスでは、前の値に睡眠時間を加算
            R.append(R[-1] + A[i] - A[i-1])

    def f(x):
        # 二分探索でxが含まれる区間を特定
        idx = bisect.bisect_right(A, x)
        if idx % 2 == 1:
            # 区間が奇数番目（起床中）なら、その直前までの睡眠時間を返す
            return R[idx-1]
        else:
            # 区間が偶数番目（睡眠中）なら、その区間の開始時刻からの経過時間を加算して返す
            return R[idx-1] + x - A[idx-1]

    # 各質問に対して処理を行う
    for l, r in queries:
        # f(r) - f(l)を計算して出力
        print(f(r) - f(l))

if __name__=="__main__":
    # メイン処理
    N, A, Q, queries = io_func()
    solve(N, A, Q, queries)

###
# N: 睡眠記録の長さ
# A: 睡眠記録（起床時刻と就寝時刻の交互のリスト）
# Q: 質問の数
# queries: 各質問のlとrのリスト
# R: 累積睡眠時間のリスト
# f(x): 時刻xにおける累積睡眠時間を計算する関数

# 1. io_func関数:
#    - 標準入力から必要なデータを読み込む
#    - 睡眠記録の長さN、睡眠記録A、質問の数Q、各質問のlとrを取得
# 2. solve関数:
#    - 累積睡眠時間Rを計算
#    - 時刻xにおける累積睡眠時間を計算する関数f(x)を定義
#    - 各質問に対して、f(r) - f(l)を計算して出力
# 3. メイン処理:
#    - io_func関数を呼び出してデータを取得
#    - solve関数を呼び出して結果を計算・出力```

問題

要約

既存投稿一覧ページへのリンク

アプローチ

解法手順

ACコード

Discussion