Official

A - 荷物の仕分け / Sorting Packages Editorial by admin

DeepSeek V3

概要

荷物の配送予定年月が今月(\(Y\)年\(M\)月)またはその翌月に該当するかどうかを判定し、それぞれの合計重量を求める問題です。

考察

問題の核心は、各荷物の配送予定年月が「今月」または「翌月」に該当するかを正確に判定することです。翌月の計算では、12月の場合は年が繰り上がる点に注意が必要です。制約条件から荷物の数\(N\)は最大100と小さいため、単純な全探索で十分効率的に処理できます。受付年月は判定に使用しないため、無視して構いません。

アルゴリズム

  1. まず、今月(\(Y\)年\(M\)月)の翌月を計算します。\(M\)が12の場合は年を1増やし月を1に、それ以外は月を1増やします。
  2. 各荷物について、配送予定年月(\(P_i\)年\(Q_i\)月)が今月と一致するかチェックし、一致すれば今月分の合計重量に加算します。
  3. 今月と一致しなかった場合、翌月と一致するかチェックし、一致すれば翌月分の合計重量に加算します。
  4. 上記のいずれにも該当しない荷物は無視します。
  5. 最後に、今月分と翌月分の合計重量を出力します。

計算量

  • 時間計算量: \(O(N)\)
    • 各荷物を1回ずつ処理するため、\(N\)に比例します。
  • 空間計算量: \(O(1)\)
    • 入力データを読み込むための定数サイズの変数のみを使用します。

実装のポイント

  • 翌月の計算を事前に行い、変数に保持しておくことで、各荷物の判定時に毎回計算する手間を省いています。

  • 入力データを一度に読み込んで分割し、インデックスをずらしながら処理することで、効率的にデータを扱っています。

  • 条件分岐は、まず今月と一致するかチェックし、その後で翌月と一致するかチェックするシンプルな構造です。

    ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    Y = int(data[1])
    M = int(data[2])
    index = 3
    this_month_total = 0
    next_month_total = 0
    
    next_year = Y
    next_month = M + 1
    if next_month > 12:
        next_month = 1
        next_year = Y + 1
    
    for i in range(n):
        A = int(data[index])
        B = int(data[index+1])
        P = int(data[index+2])
        Q = int(data[index+3])
        C = int(data[index+4])
        index += 5
        
        if P == Y and Q == M:
            this_month_total += C
        elif P == next_year and Q == next_month:
            next_month_total += C
            
    print(f"{this_month_total} {next_month_total}")

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。