概要

高橋君と青木君がベルトコンベアから流れる宝石を分配するゲームの結果を判定する問題です。

考察

この問題では、高橋君は自分がこれまで取った宝石の価値の合計が \(K\) 以下である限り、新しい宝石は必ず取り続けます。\(K\) を超えるとそこで取りやめとなり、それ以降の宝石はすべて青木君が受け取ります。

重要な観察は、「高橋君が宝石を取るかどうか」が逐次的に決まっていくことであり、かつそれが合計値が \(K\) を超えるかどうかという単純な条件で決まるということです。

この貪欲的な振る舞いにより、シミュレーションは一回のループで完了します。つまり、各宝石に対して「高橋君が取るか、青木君が取るか」を順番に決定していけばよいので、ソートや再帰など複雑な処理は必要ありません。

素朴なアプローチで誤解を生むことは少ないですが、もし仮に「全部試す」などの方法を取ると、\(N\) が最大 \(2 \times 10^5\) なので、間に合いません（TLE）。しかし、この問題では貪欲法で最適な行動が定まっているため、シンプルなシミュレーションで十分です。

アルゴリズム

1. 入力から宝石の数 \(N\) と上限値 \(K\)、そして各宝石の価値 \(A_i\) を受け取る。
2. 高橋君の取得した宝石の合計 takahashi_sum と、青木君の合計 aoki_sum を初期化する（ともに0）。
3. 各宝石 \(A_i\) に対して以下を行う：
   • もし takahashi_sum + A_i <= K なら、高橋君がその宝石を取る（takahashi_sum に加算）。
   • そうでない場合、青木君がその宝石を取る（aoki_sum に加算）。
4. 最後に両者の合計を比較し、どちらが多いか、または引き分けかを判定して出力する。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\) （入力を除く）

実装のポイント

• 入力を受け取る際に map(int, input().split()) を使うと効率的です。
• 条件分岐は「高橋君が取れるか？」だけを見ればよいので、if 文一つで処理できます。
• 最後の比較は等号も忘れずに確認しましょう（引き分けの場合に対応）。

## ソースコード

```python
N, K = map(int, input().split())
A = list(map(int, input().split()))

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 aoki_sum > takahashi_sum:
    print("Aoki")
else:
    print("Draw")

この解説は qwen3-coder-480b によって生成されました。