Candy Jars

アルゴリズム概要

ステップバイステップ解説

Python 実装

from __future__ import annotations
import os
from typing import List


# ─────────────────────────────────────────────────────────
# 競技プログラミング向け実装
# Time:  O(m)  ← 操作数のみ（n に非依存）
# Space: O(1)  ← 追加配列なし
#
# 核心式:
#   S = Σ v_i × (b_i - a_i + 1)
#   answer = floor(S / n) = S // n
# ─────────────────────────────────────────────────────────
def solve(n: int, operations: List[List[int]]) -> int:
    # Δ S = v × (b - a + 1)  を全操作分加算
    total: int = sum(v * (b - a + 1) for a, b, v in operations)
    # S // n は floor(S/n) と等価（S≥0, n>0 保証）
    return total // n


# ─────────────────────────────────────────────────────────
# 業務開発向け実装（型安全・バリデーション付き）
# ─────────────────────────────────────────────────────────
def solve_production(n: int, operations: List[List[int]]) -> int:
    """
    全操作後の平均キャンディ数の床関数を返す。

    Args:
        n:          瓶の数 (1 ≤ n ≤ 10^7)
        operations: [[a, b, v], ...] 形式の操作リスト

    Returns:
        floor(全瓶の平均キャンディ数) の整数値

    Raises:
        ValueError: n が正でない、または操作が制約違反の場合
    """
    if not isinstance(n, int) or n <= 0:
        raise ValueError(f"n は正の整数である必要があります: {n}")
    if not operations:
        return 0

    total: int = 0
    for op in operations:
        if len(op) != 3:
            raise ValueError(f"操作は 3 要素のリストである必要があります: {op}")
        a, b, v = op
        if not (1 <= a <= b <= n):
            raise ValueError(f"無効なインデックス範囲 [{a}, {b}]（n={n}）")
        if v < 0:
            raise ValueError(f"v は非負である必要があります: {v}")
        total += v * (b - a + 1)   # Δ S = v × (b - a + 1)

    return total // n              # floor(S / n)


# ─────────────────────────────────────────────────────────
# HackerRank エントリポイント
# ─────────────────────────────────────────────────────────
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    first_multiple_input = input().rstrip().split()
    n = int(first_multiple_input[0])
    m = int(first_multiple_input[1])

    operations: List[List[int]] = []
    for _ in range(m):
        operations.append(list(map(int, input().rstrip().split())))

    result = solve(n, operations)
    fptr.write(str(result) + '\n')
    fptr.close()

処理フローチャート

フローの解説：
1. 入力受付: n（瓶の数）、m（操作数）、全操作リストを受け取る
2. 初期化: 総和 S を 0 で初期化（追加配列は不要）
3. 操作ループ: 各操作の寄与 Δ S = v × (b - a + 1) を S に加算
4. 核心式: 差分配列展開をスキップ、O(m) で完結する直接総和計算
5. 床関数: S // n で平均の floor を計算
6. 出力: 結果を返す

計算量分析