【競技プログラミング】AtCoder Beginner Contest 362_C問題

# 問題
https://atcoder.jp/contests/abc362/tasks/abc362_c

## 要約

- N個の整数の組(L_1, R_1), (L_2, R_2), ..., (L_N, R_N)が与えられる。

- 以下の条件を満たす長さNの整数列X = (X_1, X_2, ..., X_N)を見つける必要がある：
1. 各i (i = 1, 2, ..., N) に対して、L_i ≤ X_i ≤ R_i を満たす。
2. X_1 + X_2 + ... + X_N = 0 を満たす。

このような整数列Xが存在するかどうかを判定し、存在する場合はその一例を出力する。

- N: 整数の組の数
- L_i: i番目の組の左側の値
- R_i: i番目の組の右側の値
- X_i: 求める整数列の i 番目の要素


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


# 解法手順


まず、合計が0になる整数列が存在するかどうかを判定する。
その後、存在する場合は具体的な整数列を構築する。


1. 入力からN、L_i、R_iの値を読み取る。

2. 存在性の判定を行う：
   - すべてのL_iの合計が正、またはすべてのR_iの合計が負の場合、合計0の整数列は存在しないため、"No"を出力して終了する。

3. 整数列Xの構築を開始する：
   - 初期値として、X_iにL_iを代入する。

4. 合計が0になるようにXを調整する：
   - 現在のXの合計（sumX）を計算する。
   - 各要素X_iについて、R_iまでの余裕（R_i - L_i）と、必要な調整量（-sumX）の小さい方を選び、その分だけX_iを増加させる。
   - sumXを更新する。

5. 構築が完了したら、"Yes"を出力し、続いて整数列Xを出力する。


# ACコード
```python: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
```python: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()
```