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

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

# 既存投稿一覧ページへのリンク
[一覧ページ](https://qiita.com/o_chan_t/items/fc759695acfaef8df2cc)


# 解法手順1

1. 入力を受け取り、睡眠記録の配列Aを作成する。

2. 累積和を計算する：
   - X: 起床時間の累積和
   - Y: 睡眠時間の累積和

3. クエリの数Qを入力として受け取る。

4. 各クエリに対して以下の処理を行う：
   a. クエリの範囲[l, r]を入力として受け取る。
   b. 二分探索を使用して、l以上の最小のインデックスsと、r以下の最大のインデックスtを見つける。
   c. sとtの関係に応じて、以下のように睡眠時間を計算する：
      - s > tの場合：
        - sが奇数なら睡眠時間は0
        - sが偶数なら睡眠時間はr - l
      - それ以外の場合：
        - 基本の睡眠時間：Y[t] - Y[s]
        - sが偶数の場合、A[s] - lを加算
        - tが奇数の場合、r - A[t]を加算

5. 計算した睡眠時間を出力する。


# ACコード1
```python:ac.py
from bisect import bisect_left, bisect  # 二分探索のためのモジュールをインポート

def io_func():
    # 入力を受け取る関数
    n = int(input())  # 睡眠記録の数を入力
    A = list(map(int, input().split()))  # 睡眠記録を入力
    q = int(input())  # クエリの数を入力
    queries = [list(map(int, input().split())) for _ in range(q)]  # クエリを入力
    return n, A, q, queries

def calculate_cumulative_sums(n, A):
    # 累積和を計算する関数
    X, Y = [0], [0]  # 起床時間と睡眠時間の累積和を初期化
    for i in range(n-1):
        if i % 2 == 0:  # 偶数インデックスは起床時間
            X.append(X[-1] + A[i+1] - A[i])
            Y.append(Y[-1])
        else:  # 奇数インデックスは睡眠時間
            X.append(X[-1])
            Y.append(Y[-1] + A[i+1] - A[i])
    return X, Y

def solve(n, A, q, queries):
    X, Y = calculate_cumulative_sums(n, A)  # 累積和を計算

    for l, r in queries:
        s = bisect_left(A, l)  # l以上の最小のインデックスを見つける
        t = bisect(A, r) - 1  # r以下の最大のインデックスを見つける

        if s > t:
            # 範囲内に睡眠記録がない場合
            if s % 2:
                print(0)  # sが奇数なら睡眠時間は0
            else:
                print(r - l)  # sが偶数なら睡眠時間はr - l
        else:
            # 範囲内に睡眠記録がある場合
            ans = Y[t] - Y[s]  # 基本の睡眠時間
            if s % 2 == 0:
                ans += A[s] - l  # sが偶数の場合、開始時の睡眠時間を加算
            if t % 2 == 1:
                ans += r - A[t]  # tが奇数の場合、終了時の睡眠時間を加算
            print(ans)

# メイン処理
n, A, q, queries = io_func()  # 入力を受け取る
solve(n, A, q, queries)  # 問題を解く

###
# n: 睡眠記録の数
# A: 睡眠記録の配列
# q: クエリの数
# queries: クエリの配列
# X: 起床時間の累積和
# Y: 睡眠時間の累積和
# l, r: クエリの範囲
# s, t: 二分探索で見つけたインデックス
# ans: 計算された睡眠時間

# 1. io_func関数:
#    - 入力を受け取り、必要なデータを返す
# 2. calculate_cumulative_sums関数:
#    - 睡眠記録から累積和を計算する
# 3. solve関数:
#    - メインの処理を行う
#    - 累積和を計算し、各クエリに対して睡眠時間を計算して出力する
# 4. メイン処理:
#    - io_func関数を呼び出して入力を受け取る
#    - solve関数を呼び出して問題を解く

```
## オブジェクト指向版1
```python:ac_object.py
import logging
from abc import ABC, abstractmethod
from bisect import bisect_left, bisect
from typing import List, Tuple

def setup_logger(debug_mode):
    logger = logging.getLogger(__name__)
    logger.setLevel(logging.DEBUG if debug_mode else logging.INFO)
    formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')
    
    file_handler = logging.FileHandler('program_trace.log', encoding="utf-8")
    file_handler.setFormatter(formatter)
    logger.addHandler(file_handler)
    
    return logger

# 入力ハンドラーの抽象基底クラス
class InputHandler(ABC):
    @abstractmethod
    def get_input(self) -> Tuple[int, List[int], int, List[List[int]]]:
        pass

# 標準入力ハンドラー
class StandardInputHandler(InputHandler):
    def get_input(self) -> Tuple[int, List[int], int, List[List[int]]]:
        n = int(input())  # 睡眠記録の数を入力
        A = list(map(int, input().split()))  # 睡眠記録を入力
        q = int(input())  # クエリの数を入力
        queries = [list(map(int, input().split())) for _ in range(q)]  # クエリを入力
        return n, A, q, queries

# 出力ハンドラーの抽象基底クラス
class OutputHandler(ABC):
    @abstractmethod
    def output(self, result: int) -> None:
        pass

# 標準出力ハンドラー
class StandardOutputHandler(OutputHandler):
    def output(self, result: int) -> None:
        print(result)

# 累積和計算クラス
class CumulativeSumCalculator:
    @staticmethod
    def calculate(n: int, A: List[int]) -> Tuple[List[int], List[int]]:
        X, Y = [0], [0]  # 起床時間と睡眠時間の累積和を初期化
        for i in range(n-1):
            if i % 2 == 0:  # 偶数インデックスは起床時間
                X.append(X[-1] + A[i+1] - A[i])
                Y.append(Y[-1])
            else:  # 奇数インデックスは睡眠時間
                X.append(X[-1])
                Y.append(Y[-1] + A[i+1] - A[i])
        return X, Y

# 睡眠時間計算クラス
class SleepTimeCalculator:
    def __init__(self, debug_mode: bool = False):
        self.logger = setup_logger(debug_mode)

    def calculate(self, n: int, A: List[int], q: int, queries: List[List[int]]) -> List[int]:
        self.logger.debug(f"引数n(={n}), A(={A}), q(={q}), queries(={queries})")
        self.logger.debug("累積和の計算を開始します")
        X, Y = CumulativeSumCalculator.calculate(n, A)
        self.logger.debug(f"累積和の計算が完了しました: X={X}, Y={Y}")

        results = []
        for l, r in queries:
            self.logger.debug(f"クエリ処理開始: l={l}, r={r}")
            s = bisect_left(A, l)  # l以上の最小のインデックスを見つける
            t = bisect(A, r) - 1  # r以下の最大のインデックスを見つける
            self.logger.debug(f"二分探索結果: s={s}, t={t}")

            if s > t:
                # 範囲内に睡眠記録がない場合
                if s % 2:
                    ans = 0  # sが奇数なら睡眠時間は0
                else:
                    ans = r - l  # sが偶数なら睡眠時間はr - l
            else:
                # 範囲内に睡眠記録がある場合
                ans = Y[t] - Y[s]  # 基本の睡眠時間
                if s % 2 == 0:
                    ans += A[s] - l  # sが偶数の場合、開始時の睡眠時間を加算
                if t % 2 == 1:
                    ans += r - A[t]  # tが奇数の場合、終了時の睡眠時間を加算
            
            self.logger.debug(f"計算結果: ans={ans}")
            results.append(ans)

        return results

# メインアプリケーションクラス
class SleepTimeApp:
    def __init__(self, input_handler: InputHandler, output_handler: OutputHandler, calculator: SleepTimeCalculator):
        self.input_handler = input_handler
        self.output_handler = output_handler
        self.calculator = calculator

    def run(self):
        n, A, q, queries = self.input_handler.get_input()
        results = self.calculator.calculate(n, A, q, queries)
        for result in results:
            self.output_handler.output(result)

class FileInputHandler(InputHandler):
    def __init__(self, filename):
        self.filename = filename

    def get_input(self) -> Tuple[int, List[int], int, List[List[int]]]:
        with open(self.filename, 'r') as f:
            n = int(f.readline().strip())
            A = list(map(int, f.readline().split()))
            q = int(f.readline().strip())
            queries = [list(map(int, line.split())) for line in f.readlines()]
        return n, A, q, queries

class FileOutputHandler(OutputHandler):
    def __init__(self, filename):
        self.filename = filename

    def output(self, result: int) -> None:
        with open(self.filename, 'w') as f:
            f.write(f"{result}\n")

import unittest

class TestSleepTimeCalculator(unittest.TestCase):
    def setUp(self):
        self.calculator = SleepTimeCalculator(debug_mode=True)

    def test_calculate(self):
        n = 7
        A = [0, 240, 720, 1320, 1440, 1800, 2160]
        q = 3
        queries = [[480, 1920], [720, 1200], [0, 2160]]
        expected_results = [480, 0, 960]

        results = self.calculator.calculate(n, A, q, queries)
        self.assertEqual(results, expected_results)


if __name__ == '__main__':
    unittest.main()

```

### オブジェクト図

![2025年01月21日19時57分_abc303d.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/530912/c58a1531-1852-2576-9e79-e5458918160a.png)


### オブジェクト指向版1で書くメリット
#### 拡張性と再利用性
```python:ac_object.py
class FileInputHandler(InputHandler):
    def __init__(self, filename):
        self.filename = filename

    def get_input(self) -> Tuple[int, List[int], int, List[List[int]]]:
        with open(self.filename, 'r') as f:
            n = int(f.readline().strip())
            A = list(map(int, f.readline().split()))
            q = int(f.readline().strip())
            queries = [list(map(int, line.split())) for line in f.readlines()]
        return n, A, q, queries

class FileOutputHandler(OutputHandler):
    def __init__(self, filename):
        self.filename = filename

    def output(self, result: int) -> None:
        with open(self.filename, 'w') as f:
            f.write(f"{result}\n")

# メイン処理を変更
if __name__ == "__main__":
    input_handler = FileInputHandler("input.txt")
    output_handler = FileOutputHandler("output.txt")
    calculator = SleepTimeCalculator(debug_mode=True)
    app = SleepTimeApp(input_handler, output_handler, calculator)
    app.run()
    
```

#### オブジェクト図

![2025年01月22日23時51分_abc305d2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/530912/bf31def6-eb8e-6b86-2c8f-7e55b1a60690.png)

#### テスト容易性
```python:ac_object.py

import unittest

class TestSleepTimeCalculator(unittest.TestCase):
    def setUp(self):
        self.calculator = SleepTimeCalculator(debug_mode=True)

    def test_calculate(self):
        n = 7
        A = [0, 240, 720, 1320, 1440, 1800, 2160]
        q = 3
        queries = [[480, 1920], [720, 1200], [0, 2160]]
        expected_results = [480, 0, 960]

        results = self.calculator.calculate(n, A, q, queries)
        self.assertEqual(results, expected_results)


if __name__ == '__main__':
    unittest.main()

```