概要

高橋君と青木君が宝石を順番に分配し、最終的な合計価値の大小で勝敗を決める問題です。高橋君は合計が\(K\)以下になる限り宝石を取り続け、青木君は高橋君が取らなかった宝石をすべて取ります。

考察

この問題は、宝石が流れてくる順番に高橋君の行動が決まるという単純なルールです。高橋君は現在の合計値が\(K\)以下である限り宝石を取り続け、\(K\)を超える場合はその宝石を取らないため、青木君が取ることになります。重要な点は、高橋君の行動が貪欲法で決定されることです。つまり、各ステップで最適な選択（合計が\(K\)以下なら取る）を繰り返すだけで、最終的な両者の合計値を計算できます。

アルゴリズム

1. 高橋君の合計値takahashi_sumと青木君の合計値aoki_sumを0で初期化します。
2. 宝石を順番に処理します：
   • 現在の高橋君の合計値に次の宝石の価値を足しても\(K\)以下なら、高橋君がその宝石を取ります（takahashi_sumに加算）。
   • そうでなければ、高橋君はその宝石を取らず、青木君が取ります（aoki_sumに加算）。
3. すべての宝石を処理した後、両者の合計値を比較します：
   • takahashi_sum > aoki_sumなら高橋君の勝利
   • takahashi_sum < aoki_sumなら青木君の勝利
   • 等しければ引き分け

計算量

• 時間計算量: \(O(N)\)
  • \(N\)個の宝石を1回ずつ処理するため
• 空間計算量: \(O(N)\)
  • 宝石の価値を格納する配列の分だけ必要

実装のポイント

• 入力の読み取りでは、一度にすべてのデータを読み込むことで効率的に処理できます。

• 各宝石に対して条件分岐を行い、高橋君が取るかどうかを判断します。

• 合計値の比較は単純な大小比較で行います。

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:2+n]))
    
    takahashi_sum = 0
    aoki_sum = 0
    
    for a in A:
        if takahashi_sum + a <= K:
            takahashi_sum += a
        else:
            aoki_sum += a
            
    if takahashi_sum > aoki_sum:
        print("Takahashi")
    elif takahashi_sum < aoki_sum:
        print("Aoki")
    else:
        print("Draw")

if __name__ == "__main__":
    main()

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