概要

高橋君がルール通りに宝石を取ったときの合計点 \(t\) と、残り（青木君）の合計点 \(a\) を計算し、\(t\) と \(a\) を比較して勝敗を判定します。

考察

この問題のポイントは、「ゲーム」と書かれていても 高橋君の行動が完全に固定されている ことです。
各宝石 \(A_i\) が来た瞬間に、

• それまでの取得合計が \(t\) のとき、\(t + A_i \le K\) なら必ず取る
• そうでなければ取らない

と決まっているため、分岐や戦略は存在しません。つまり、必要なのは 前から順に1回シミュレーションするだけ です。

また、青木君は「高橋君が取らなかった宝石を全部もらう」ので、青木君の合計は - 全体の総和 \(S = \sum A_i\) - 高橋君の合計 \(t\) を使って \(a = S - t\) と一発で求まります。

素朴に「高橋君が取る/取らないの組合せ」を全探索したり、ナップサックDPのように考えると \(N \le 2\times 10^5\) では到底間に合いません（そもそも選択の自由がないため不要です）。

例： - \(K=10,\ A=[6,5,4]\) - 6 は \(0+6\le 10\) なので取る → \(t=6\) - 5 は \(6+5>10\) なので取らない → \(t=6\) - 4 は \(6+4\le 10\) なので取る → \(t=10\) - 総和 \(S=15\) なので青木君 \(a=15-10=5\)、高橋君の勝ち

アルゴリズム

1. \(t=0\)（高橋君の取得合計）, \(S=0\)（全体の総和）で初期化する。
2. 配列を先頭から順に見ていく。各 \(x=A_i\) について：
   • \(S \leftarrow S + x\)
   • もし \(t + x \le K\) なら \(t \leftarrow t + x\)（高橋君が取る）
3. 青木君の合計は \(a = S - t\)。
4. \(t\) と \(a\) を比較して
   • \(t>a\) なら Takahashi
   • \(t<a\) なら Aoki
   • 等しければ Draw を出力する。

計算量

• 時間計算量: \(O(N)\)（1回の走査のみ）
• 空間計算量: \(O(1)\)（入力配列を除けば定数。実装では配列を持つので \(O(N)\)）

実装のポイント

• \(K \le 10^{15}\)、総和も大きくなり得るため、64bit整数が必要です（Python の int なら安全）。

• 入力が最大 \(2\times 10^5\) なので、Pythonでは sys.stdin.readline を使うと安定します。

• 青木君の点数は「取らなかったものを足す」より「総和から引く」ほうが簡潔でミスが減ります。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    t = 0
    total = 0
    for x in A:
        total += x
        if t + x <= K:
            t += x
    a = total - t
    if t > a:
        print("Takahashi")
    elif t < a:
        print("Aoki")
    else:
        print("Draw")

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。