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

# 問題
https://atcoder.jp/contests/abc388/tasks/abc388_d

## 要約

ある星には N 人の宇宙人がおり、全員が未成年である。
i 人目の宇宙人は現在 A_i 個の石を所持しており、ちょうど i 年後に成人する。

この星では、誰かが成人するときに以下のルールが適用される
1. 石を1個以上所持している成人全員が、
2. 成人する宇宙人に成人祝いとして石を1個渡す。

N 年後に各宇宙人が所持している石の個数を求めることが課題である。

ただし、今後新たな宇宙人は生まれないものとする。

- N: 宇宙人の総数
- i: 宇宙人の番号 (1 ≤ i ≤ N)
- A_i: i 番目の宇宙人が現在所持している石の個数
- 
# 既存投稿一覧ページへのリンク
[一覧ページ](https://qiita.com/o_chan_t/items/fc759695acfaef8df2cc)


# 解法手順1

## 解法アプローチ

時間の経過に沿って各宇宙人の成人と石の移動を追跡し、最終的な石の分布を計算する。
優先度付きキューを使用して、効率的に成人時期と石の移動を管理する。

## 解法手順

1. 入力を受け取り、宇宙人の数Nと各宇宙人の初期石数A_iを取得する。

2. 現在の追加ボーナス数（bonus）と、ボーナスが終了する時期を管理する優先度付きキュー（bonus_end）を初期化する。
ここに記載するボーナスとは、石を渡すこと

3. 各宇宙人について、以下の処理を行う：
   a. 現在の時点でボーナスが終了する宇宙人がいれば、bonusから1を引く。
   b. 現在の宇宙人の石の数を計算する（初期石数 + 現在のボーナス数）。
   c. この宇宙人が他の宇宙人全員に石を渡した後の残りの石の数を計算し、結果リストに追加する。
   d. bonusを1増やす（この宇宙人が成人したため）。
   e. この宇宙人のボーナスが終了する時期をbonus_endに追加する。

4. 全ての宇宙人について処理が終わったら、結果リストを出力する。


# ACコード1
```python:ac.py

from heapq import heappush, heappop  # 優先度付きキューの操作のためのheapqモジュールをインポート

def io_func():
    # 入力を受け取る関数
    n = int(input())  # 宇宙人の数Nを入力
    a = list(map(int, input().split()))  # 各宇宙人の初期石数A_iを入力
    return n, a

def solve(n, a):
    # メインの処理を行う関数
    bonus = 0  # 現在の追加ボーナス数を初期化
    bonus_end = []  # ボーナスが終了する時期を管理する優先度付きキュー
    ans = []  # 結果を格納するリスト

    for i in range(n):
        # 現在の時点でボーナスが終了する宇宙人がいれば、bonusから1を引く
        while bonus_end:
            h = heappop(bonus_end)
            if h == i:
                bonus -= 1
            else:
                heappush(bonus_end, h)
                break
        
        # 現在の宇宙人の石の数を計算
        num = a[i] + bonus
        # この宇宙人が他の宇宙人全員に石を渡した後の残りの石の数を計算し、結果リストに追加
        ans.append(max(num-(n-i-1), 0))
        # bonusを1増やす（この宇宙人が成人したため）
        bonus += 1
        # この宇宙人のボーナスが終了する時期をbonus_endに追加
        heappush(bonus_end, i+num+1)

    return ans

# メイン処理
n, a = io_func()  # 入力を受け取る
result = solve(n, a)  # 問題を解く
print(*result)  # 結果を出力

###
# n: 宇宙人の数
# a: 各宇宙人の初期石数のリスト
# bonus: 現在の追加ボーナス数
# bonus_end: ボーナスが終了する時期を管理する優先度付きキュー
# ans: 各宇宙人が最終的に持つ石の数のリスト
# i: 現在処理している宇宙人のインデックス
# h: ボーナスが終了する時期
# num: 現在の宇宙人が持つ石の数（初期石数 + ボーナス）

# 1. io_func関数:
#    - 標準入力から宇宙人の数nと各宇宙人の初期石数aを読み取る
#    - nとaを返す
#
# 2. solve関数:
#    - 引数としてnとaを受け取る
#    - bonusとbonus_endを初期化
#    - 各宇宙人について以下の処理を行う:
#      a. ボーナスが終了する宇宙人がいればbonusを減らす
#      b. 現在の宇宙人の石の数を計算
#      c. 他の宇宙人に石を渡した後の残りの石の数を計算し、ansに追加
#      d. bonusを増やす
#      e. この宇宙人のボーナスが終了する時期をbonus_endに追加
#    - 最終的なansを返す
#
# 3. メイン処理:
#    - io_func関数を呼び出して入力を受け取る
#    - solve関数を呼び出して問題を解く
#    - 結果を出力する

```
## オブジェクト指向版1
```python:ac_object.py
from heapq import heappush, heappop
import logging
from abc import ABC, abstractmethod

# ロガーの設定
logging.basicConfig(filename='space_stones.log', level=logging.DEBUG)
logger = logging.getLogger(__name__)

class InputReader(ABC):
    @abstractmethod
    def read_input(self):
        pass

class ConsoleInputReader(InputReader):
    def read_input(self):
        n = int(input())
        a = list(map(int, input().split()))
        return n, a

class SpaceStoneSolver:
    def __init__(self, enable_logging=False):
        self.enable_logging = enable_logging

    def solve(self, n, a):
        bonus = 0
        bonus_end = []
        ans = []

        if self.enable_logging:
            logger.debug(f"宇宙人の人数: {n}, 各宇宙人が持っている石の個数: {a}")

        for i in range(n):
            if self.enable_logging:
                logger.debug(f"処理中の宇宙人: {i}")

            while bonus_end:
                h = heappop(bonus_end)
                if self.enable_logging:
                    logger.debug(f"処理中の宇宙人{i}のbonus_end変数: {bonus_end} ")
                if h == i:
                    bonus -= 1
                    if self.enable_logging:
                        logger.debug(f"ボーナス終了: 現在のボーナス = {bonus}")
                else:
                    heappush(bonus_end, h)
                    break

            num = a[i] + bonus
            ans.append(max(num-(n-i-1), 0))
            bonus += 1
            heappush(bonus_end, i+num+1)

            if self.enable_logging:
                logger.debug(f"宇宙人 {i} の処理後: 石の数 = {ans[-1]}, ボーナス = {bonus}")

        return ans

class OutputWriter(ABC):
    @abstractmethod
    def write_output(self, result):
        pass

class ConsoleOutputWriter(OutputWriter):
    def write_output(self, result):
        print(*result)

class SpaceStoneManager:
    def __init__(self, input_reader: InputReader, solver: SpaceStoneSolver, output_writer: OutputWriter):
        self.input_reader = input_reader
        self.solver = solver
        self.output_writer = output_writer

    def run(self):
        n, a = self.input_reader.read_input()
        result = self.solver.solve(n, a)
        self.output_writer.write_output(result)

if __name__ == "__main__":
    enable_logging = True  # ログを有効にする場合はTrueに設定
    input_reader = ConsoleInputReader()
    solver = SpaceStoneSolver(enable_logging)
    output_writer = ConsoleOutputWriter()
    
    manager = SpaceStoneManager(input_reader, solver, output_writer)
    manager.run()
```

### オブジェクト指向版1で書くメリット
#### テスト容易性
```python:ac_object.py
import unittest

class TestSpaceStoneSolver(unittest.TestCase):
   def setUp(self):
       self.solver = SpaceStoneSolver(True)

   def test_solve_simple_case(self):
       n = 3
       a = [1, 2, 3]
       expected = [0, 2, 4]
       self.assertEqual(self.solver.solve(n, a), expected)

   def test_solve_complex_case(self):
       n = 5
       a = [3, 1, 4, 1, 5]
       expected = [0, 0, 4, 3, 7]
       self.assertEqual(self.solver.solve(n, a), expected)

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