問題
既存投稿一覧ページへのリンク
解法手順1
-
入力を受け取り、睡眠記録の配列Aを作成する。
-
累積和を計算する：
- X: 起床時間の累積和
- Y: 睡眠時間の累積和
-
クエリの数Qを入力として受け取る。
-
各クエリに対して以下の処理を行う：
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]を加算
- s > tの場合：
-
計算した睡眠時間を出力する。
ACコード1
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
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()
オブジェクト図
オブジェクト指向版1で書くメリット
拡張性と再利用性
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()
オブジェクト図
テスト容易性
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()