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

# 問題
https://atcoder.jp/contests/abc267/tasks/abc267_c

## 要約
長さNの整数列A = (A1, A2, ..., AN)が与えられている。

この整数列Aから、長さMの連続部分列B = (B1, B2, ..., BM)を選び出す。

選び出した部分列Bに対して、以下の式の最大値を求める

Σ(i=1からMまで) i × Bi

ここで、iは部分列Bの各要素の位置（1からMまで）を表し、Biはその位置の要素の値を表します。

- N: 元の整数列Aの長さ
- A: 与えられる整数列 (A1, A2, ..., AN)
- M: 選び出す連続部分列Bの長さ
- B: Aから選び出された連続部分列 (B1, B2, ..., BM)

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


# 解法手順1


1. 入力値N, M, および配列Aを受け取る。

2. 初期のM個の要素に対して、位置を考慮した重み付け和（s）と単純な和（t）を計算する。
   - sは Σ(i=1からMまで) i × Ai を計算
   - tは Σ(i=1からMまで) Ai を計算

3. 初期の重み付け和sを最大値（ans）として設定する。

4. 配列Aの残りの部分に対してスライディングウィンドウを適用する：
   - ウィンドウの先頭要素を除去し、次の要素を追加
   - 新しい重み付け和（next_s）を計算：
     next_s = 前回のs - 前回のt + 新しく追加された要素 × M
   - 新しい単純な和（next_t）を計算：
     next_t = 前回のt - 除去された要素 + 新しく追加された要素
   - sとtを更新
   - 最大値（ans）を更新：もし新しいsが現在のansより大きければ更新

5. すべての可能な連続部分列を確認した後、最大値（ans）を出力する。


# ACコード1
```python:ac.py
def io_func():
    # 入力値N, Mを受け取る
    n, m = map(int, input().split())
    # 配列Aを受け取る
    a = list(map(int, input().split()))
    return n, m, a

def solve(n, m, a):
    # 初期のM個の要素に対して、位置を考慮した重み付け和（s）を計算
    s = sum(a[i] * (i + 1) for i in range(m))
    
    # 初期のM個の要素に対して、単純な和（t）を計算
    t = sum(a[i] for i in range(m))
    
    # 初期の重み付け和sを最大値（ans）として設定
    ans = s
    
    # 配列Aの残りの部分に対してスライディングウィンドウを適用
    for i in range(n - m):
        # 新しい重み付け和（next_s）を計算
        next_s = s - t + a[i + m] * m
        # 新しい単純な和（next_t）を計算
        next_t = t - a[i] + a[i + m]
        
        # sとtを更新
        s = next_s
        t = next_t
        
        # 最大値（ans）を更新
        ans = max(ans, s)
    
    # 最大値（ans）を出力
    print(ans)

# メイン処理
n, m, a = io_func()
solve(n, m, a)

###
# n: 配列Aの要素数
# m: 連続部分列の長さ
# a: 入力された整数列
# s: 位置を考慮した重み付け和
# t: 単純な和
# ans: 最大の重み付け和

# 1. io_func関数で入力を受け取る
# 2. solve関数で主な処理を行う
#    - 初期のM個の要素に対して重み付け和と単純な和を計算
#    - スライディングウィンドウ法を用いて残りの要素を処理
#    - 各ステップで最大値を更新
# 3. 最終的な最大値を出力
# 
```
## オブジェクト指向版1
```python:ac_object.py
import logging
from abc import ABC, abstractmethod

# ロガーの設定
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')
    file_handler.setFormatter(formatter)
    logger.addHandler(file_handler)
    
    return logger

# 入力インターフェース
class InputInterface(ABC):
    @abstractmethod
    def get_input(self):
        pass

# 標準入力クラス
class StandardInput(InputInterface):
    def get_input(self):
        n, m = map(int, input().split())
        a = list(map(int, input().split()))
        return n, m, a

# 解決戦略インターフェース
class SolveStrategy(ABC):
    @abstractmethod
    def solve(self, n, m, a):
        pass

# スライディングウィンドウ解決戦略
class SlidingWindowStrategy(SolveStrategy):
    def __init__(self, debug_mode=False):
        self.logger = setup_logger(debug_mode)

    def solve(self, n, m, a):
        self.logger.debug("スライディングウィンドウ法による解決を開始")
        self.logger.debug(f"初期の重み付け和: n:{n}, m:{m}, a:{a}")
        
        # 初期のM個の要素に対して、位置を考慮した重み付け和（s）を計算
        s = sum(a[i] * (i + 1) for i in range(m))
        self.logger.debug(f"初期の重み付け和: {s}")
        
        # 初期のM個の要素に対して、単純な和（t）を計算
        t = sum(a[i] for i in range(m))
        self.logger.debug(f"初期の単純な和: {t}")
        
        # 初期の重み付け和sを最大値（ans）として設定
        ans = s
        self.logger.debug(f"初期の最大値: {ans}")
        
        # 配列Aの残りの部分に対してスライディングウィンドウを適用
        for i in range(n - m):
            # 新しい重み付け和（next_s）を計算
            next_s = s - t + a[i + m] * m
            # 新しい単純な和（next_t）を計算
            next_t = t - a[i] + a[i + m]
            
            # sとtを更新
            s = next_s
            t = next_t
            
            # 最大値（ans）を更新
            ans = max(ans, s)
            self.logger.debug(f"ステップ {i+1}: 新しい重み付け和 = {s}, 最大値 = {ans}")
        
        self.logger.debug(f"最終的な最大値: {ans}")
        return ans

# 出力インターフェース
class OutputInterface(ABC):
    @abstractmethod
    def output_result(self, result):
        pass

# 標準出力クラス
class StandardOutput(OutputInterface):
    def output_result(self, result):
        print(result)

# メインクラス
class MaxWeightedSum:
    def __init__(self, input_handler: InputInterface, solve_strategy: SolveStrategy, output_handler: OutputInterface):
        self.input_handler = input_handler
        self.solve_strategy = solve_strategy
        self.output_handler = output_handler

    def run(self):
        n, m, a = self.input_handler.get_input()
        result = self.solve_strategy.solve(n, m, a)
        self.output_handler.output_result(result)

# メイン処理
if __name__ == "__main__":
    input_handler = StandardInput()
    solve_strategy = SlidingWindowStrategy(debug_mode=True)  # デバッグモードをTrueに設定
    output_handler = StandardOutput()
    
    max_weighted_sum = MaxWeightedSum(input_handler, solve_strategy, output_handler)
    max_weighted_sum.run()

```

### クラス図
![sequence_diagram.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/530912/af3708ed-c384-b231-8a25-7ad92dd046e9.png)


### オブジェクト指向版1で書くメリット
#### 拡張性と再利用性
```python:ac_object.py
# 新しい入力方法（ファイル入力）を追加
class FileInput(InputInterface):
   def __init__(self, filename):
       self.filename = filename

   def get_input(self):
       with open(self.filename, 'r') as f:
           n, m = map(int, f.readline().split())
           a = list(map(int, f.readline().split()))
       return n, m, a

# 使用例
input_handler = FileInput('input.txt')
max_weighted_sum = MaxWeightedSum(input_handler, solve_strategy, output_handler)
max_weighted_sum.run()
```

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

class TestSlidingWindowStrategy(unittest.TestCase):
    def setUp(self):
        self.strategy = SlidingWindowStrategy(debug_mode=True)

    def test_solve_basic(self):
        n, m, a = 5, 3, [1, 2, 3, 4, 5]
        result = self.strategy.solve(n, m, a)
        self.assertEqual(result, 26)

    def test_solve_all_same(self):
        n, m, a = 5, 3, [1, 1, 1, 1, 1]
        result = self.strategy.solve(n, m, a)
        self.assertEqual(result, 6)

    def test_solve_edge_case(self):
        n, m, a = 3, 3, [1, 2, 3]
        result = self.strategy.solve(n, m, a)
        self.assertEqual(result, 14)

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