問題
要約
-
N個の整数の組(L_1, R_1), (L_2, R_2), ..., (L_N, R_N)が与えられる。
-
以下の条件を満たす長さNの整数列X = (X_1, X_2, ..., X_N)を見つける必要がある：
- 各i (i = 1, 2, ..., N) に対して、L_i ≤ X_i ≤ R_i を満たす。
- X_1 + X_2 + ... + X_N = 0 を満たす。
このような整数列Xが存在するかどうかを判定し、存在する場合はその一例を出力する。
- N: 整数の組の数
- L_i: i番目の組の左側の値
- R_i: i番目の組の右側の値
- X_i: 求める整数列の i 番目の要素
既存投稿一覧ページへのリンク
解法手順
まず、合計が0になる整数列が存在するかどうかを判定する。
その後、存在する場合は具体的な整数列を構築する。
-
入力からN、L_i、R_iの値を読み取る。
-
存在性の判定を行う：
- すべてのL_iの合計が正、またはすべてのR_iの合計が負の場合、合計0の整数列は存在しないため、"No"を出力して終了する。
-
整数列Xの構築を開始する：
- 初期値として、X_iにL_iを代入する。
-
合計が0になるようにXを調整する：
- 現在のXの合計（sumX）を計算する。
- 各要素X_iについて、R_iまでの余裕（R_i - L_i）と、必要な調整量（-sumX）の小さい方を選び、その分だけX_iを増加させる。
- sumXを更新する。
-
構築が完了したら、"Yes"を出力し、続いて整数列Xを出力する。
ACコード
ac.py
def io_func():
# 入力からN、L_i、R_iの値を読み取る
N = int(input()) # 整数列の長さ
L, R = [0] * N, [0] * N # L_iとR_iを格納するリスト
for i in range(N):
L[i], R[i] = map(int, input().split()) # 各要素の下限と上限を読み取る
return N, L, R
def solve(N, L, R):
# 存在性の判定を行う
if sum(L) > 0 or sum(R) < 0:
print("No") # 合計0の整数列が存在しない場合
return
# 整数列Xの構築を開始する
X = L.copy() # 初期値としてL_iを代入
sumX = sum(X) # 現在のXの合計を計算
# 合計が0になるようにXを調整する
for i in range(N):
d = min(R[i] - L[i], -sumX) # 調整量を計算
sumX += d # sumXを更新
X[i] += d # X_iを増加
# 結果の出力
print("Yes")
print(*X) # 整数列Xを出力
# メイン処理
N, L, R = io_func() # 入力を受け取る
solve(N, L, R) # 問題を解く
###
# N: 整数列の長さ
# L: 各要素の下限値のリスト
# R: 各要素の上限値のリスト
# X: 構築される整数列
# sumX: 整数列Xの合計値
# d: 各ステップでの調整量
# 1. io_func関数:
# - 標準入力から問題のパラメータを読み取る
# - N, L, Rを返す
# 2. solve関数:
# - 合計0の整数列が存在するかを判定
# - 存在しない場合は"No"を出力して終了
# - 存在する場合、整数列Xを構築
# - 貪欲法を用いて各要素を調整し、合計が0になるようにする
# - 結果を出力
# 3. メイン処理:
# - io_func関数を呼び出して入力を受け取る
# - solve関数を呼び出して問題を解く
オブジェクト指向版1
ac.py
from abc import ABC, abstractmethod
from typing import List, Tuple
# 単一責任の原則: 入力処理を担当するクラス
class InputHandler:
@staticmethod
def read_input() -> Tuple[int, List[int], List[int]]:
"""標準入力から問題のパラメータを読み取る"""
N = int(input()) # 整数列の長さ
L, R = [0] * N, [0] * N # L_iとR_iを格納するリスト
for i in range(N):
L[i], R[i] = map(int, input().split()) # 各要素の下限と上限を読み取る
return N, L, R
# 開放/閉鎖原則: 出力処理を担当する抽象クラス
class OutputHandler(ABC):
@abstractmethod
def print_result(self, result: str, sequence: List[int] = None) -> None:
"""結果を出力する抽象メソッド"""
pass
# 具体的な出力処理を行うクラス
class ConsoleOutputHandler(OutputHandler):
def print_result(self, result: str, sequence: List[int] = None) -> None:
"""コンソールに結果を出力する"""
print(result)
if sequence:
print(*sequence)
# 単一責任の原則: 問題解決ロジックを担当するクラス
class SequenceSolver:
def __init__(self, N: int, L: List[int], R: List[int]):
self.N = N # 整数列の長さ
self.L = L # 各要素の下限値のリスト
self.R = R # 各要素の上限値のリスト
def solve(self) -> Tuple[bool, List[int]]:
"""合計0の整数列が存在するか判定し、存在する場合は構築する"""
# 存在性の判定
if sum(self.L) > 0 or sum(self.R) < 0:
return False, [] # 合計0の整数列が存在しない場合
# 整数列Xの構築を開始
X = self.L.copy() # 初期値としてL_iを代入
sumX = sum(X) # 現在のXの合計を計算
# 合計が0になるようにXを調整
for i in range(self.N):
d = min(self.R[i] - self.L[i], -sumX) # 調整量を計算
sumX += d # sumXを更新
X[i] += d # X_iを増加
return True, X
# 依存性逆転の原則: 高レベルモジュールと低レベルモジュールを抽象に依存させる
class SequenceProblemSolver:
def __init__(self, input_handler: InputHandler, output_handler: OutputHandler):
self.input_handler = input_handler
self.output_handler = output_handler
def run(self) -> None:
"""問題を解くメイン処理"""
# 入力を受け取る
N, L, R = self.input_handler.read_input()
# 問題を解く
solver = SequenceSolver(N, L, R)
exists, sequence = solver.solve()
# 結果を出力
if exists:
self.output_handler.print_result("Yes", sequence)
else:
self.output_handler.print_result("No")
# メイン処理
if __name__ == "__main__":
input_handler = InputHandler()
output_handler = ConsoleOutputHandler()
problem_solver = SequenceProblemSolver(input_handler, output_handler)
problem_solver.run()