概要

ベルトコンベアで流れてくる宝石を、高橋君が「合計が \(K\) 以下なら必ず取る」というルールで取得し、残りを青木君が受け取ったとき、どちらの合計が大きいかを判定する問題です。

考察

まず、高橋君の行動ルールを正確に理解しましょう。

• 宝石は順番に1つずつ流れてくる。
• 高橋君は「今までに取った宝石の合計 + 今の宝石の価値」が \(K\) 以下なら必ず取る。
• \(K\) を超えてしまう場合は取らない。
• 青木君は、高橋君が取らなかった宝石をすべて受け取る。

つまり、高橋君の行動は完全に決定的（選択の余地なし）であるため、シミュレーションするだけで答えが求まります。

具体例: \(N = 4\), \(K = 5\), \(A = [3, 4, 2, 1]\) の場合

最終結果: 高橋 \(5\)、青木 \(5\) → Draw

この問題は特別なアルゴリズムやデータ構造を必要とせず、宝石を先頭から順に見ていくシンプルなシミュレーションで解けます。\(N\) が最大 \(2 \times 10^5\) なので、\(O(N)\) の1回のループで十分間に合います。

アルゴリズム

1. 高橋君の合計 takahashi と青木君の合計 aoki を \(0\) で初期化する。
2. 宝石を流れてくる順番（\(A_1, A_2, \ldots, A_N\)）に見ていく。
   • takahashi + a <= K なら、高橋君が取る → takahashi += a
   • そうでなければ、青木君が受け取る → aoki += a
3. 最後に takahashi と aoki を比較し、大きい方を出力する。等しければ Draw。

計算量

• 時間計算量: \(O(N)\) — 宝石を1つずつ順番に処理するだけ
• 空間計算量: \(O(N)\) — 入力の配列を保持する分（ストリーム処理にすれば \(O(1)\) も可能）

実装のポイント

• \(K\) の最大値が \(10^{15}\)、\(A_i\) の最大値が \(10^9\)、\(N\) が最大 \(2 \times 10^5\) なので、合計値は最大で約 \(2 \times 10^{14}\) 程度になります。C++ などでは long long を使う必要がありますが、Python では整数のオーバーフローを気にする必要はありません。

• 高橋君の判断は「現在の合計に今の宝石を加えても \(K\) 以下か」であり、各宝石を見るたびに判断する点に注意してください。最適化や並べ替えは一切行いません。

  ソースコード

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

takahashi = 0
aoki = 0

for a in A:
    if takahashi + a <= K:
        takahashi += a
    else:
        aoki += a

if takahashi > aoki:
    print("Takahashi")
elif takahashi < aoki:
    print("Aoki")
else:
    print("Draw")

この解説は claude4.6opus-thinking によって生成されました。