概要

\(N\) 個の宝石が順番に流れてくる中で、高橋君が特定のルール（自身の合計が \(K\) を超えない限り取る）に従って宝石を確保し、残りを青木君が受け取った際の最終的な合計価値を比較する問題です。

考察

この問題のポイントは、「高橋君が宝石を取るかどうかの判断基準が、その時点までの自分の合計価値のみに依存している」という点です。

宝石はベルトコンベアで流れてくるため、順番を変えることはできません。したがって、前から順番に「高橋君が取れるかどうか」を判定していくシミュレーションを行うことで解くことができます。

考慮すべき点

• 制約の大きさ: 宝石の数 \(N\) は最大 \(2 \times 10^5\)、閾値 \(K\) は最大 \(10^{15}\)、各宝石の価値 \(A_i\) は最大 \(10^9\) です。
• 数値の型: 合計価値は最大で \(2 \times 10^5 \times 10^9 = 2 \times 10^{14}\) 程度になる可能性があります。Pythonでは整数の大きさに制限がないため問題ありませんが、他の言語（C++など）では 64bit 整数型（long long など）を使用する必要があります。
• 計算量: \(N\) 個の要素を一度ずつ確認する \(O(N)\) のアルゴリズムであれば、実行時間制限に十分間に合います。

アルゴリズム

以下の手順でシミュレーションを行います。

1. 高橋君の合計価値 takahashi_sum と青木君の合計価値 aoki_sum を \(0\) で初期化する。
2. 宝石の価値 \(A_1, A_2, \ldots, A_N\) を順番に取り出し、以下の処理を繰り返す：
   • もし takahashi_sum + A_i が \(K\) 以下ならば、高橋君がその宝石を取る。
     • takahashi_sum に \(A_i\) を加算する。
   • そうでなければ、青木君がその宝石を取る。
     • aoki_sum に \(A_i\) を加算する。
3. すべての宝石を処理した後、takahashi_sum と aoki_sum を比較する：
   • takahashi_sum > aoki_sum ならば Takahashi を出力。
   • aoki_sum > takahashi_sum ならば Aoki を出力。
   • 等しければ Draw を出力。

計算量

• 時間計算量: \(O(N)\)
  • 宝石のリストを \(1\) 回走査するだけなので、宝石の数 \(N\) に比例した時間で計算が終わります。
• 空間計算量: \(O(N)\)
  • 入力された宝石の価値をリストに保持する場合、 \(N\) に比例したメモリを使用します。

実装のポイント

• 高速な入力: \(N\) が \(2 \times 10^5\) と比較的大きいため、Pythonでは input() を繰り返すよりも sys.stdin.read().split() などで一括して入力を読み込む方が高速です。

• 条件分岐: 「\(K\) を超えてしまう場合は取らない」というルールを正確に if takahashi_sum + val <= k: という条件式で表現します。

  ソースコード

import sys

def solve():
    # 入力を一括で読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N と K を取得
    n = int(input_data[0])
    k = int(input_data[1])
    
    # 宝石の価値のリストを取得
    a = map(int, input_data[2:])
    
    takahashi_sum = 0
    aoki_sum = 0
    
    # ルールに従って宝石を分配する
    for val in a:
        if takahashi_sum + val <= k:
            # 高橋君が取った合計が K 以下なら高橋君が取る
            takahashi_sum += val
        else:
            # そうでなければ青木君が取る
            aoki_sum += val
            
    # 結果を判定して出力
    if takahashi_sum > aoki_sum:
        print("Takahashi")
    elif aoki_sum > takahashi_sum:
        print("Aoki")
    else:
        print("Draw")

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-thinking によって生成されました。