問題
要約
長さ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)
既存投稿一覧ページへのリンク
解法手順1
-
入力値N, M, および配列Aを受け取る。
-
初期のM個の要素に対して、位置を考慮した重み付け和（s）と単純な和（t）を計算する。
- sは Σ(i=1からMまで) i × Ai を計算
- tは Σ(i=1からMまで) Ai を計算
-
初期の重み付け和sを最大値（ans）として設定する。
-
配列Aの残りの部分に対してスライディングウィンドウを適用する：
- ウィンドウの先頭要素を除去し、次の要素を追加
- 新しい重み付け和（next_s）を計算：
next_s = 前回のs - 前回のt + 新しく追加された要素 × M - 新しい単純な和（next_t）を計算：
next_t = 前回のt - 除去された要素 + 新しく追加された要素 - sとtを更新
- 最大値（ans）を更新：もし新しいsが現在のansより大きければ更新
-
すべての可能な連続部分列を確認した後、最大値（ans）を出力する。
ACコード1
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
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()
クラス図
オブジェクト指向版1で書くメリット
拡張性と再利用性
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()
テスト容易性
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()