概要

\(N\) 枚のカードが並べられており、隣り合う番号のカード同士で条件に従って攻撃力を比較し、一方がもう一方を吸収する（取り除く）操作を順に行います。すべての操作が終わった後に残っているカードの枚数を求める問題です。

考察

この問題で最も重要なのは、「処理の対象となるのは番号が \(i\) と \(i+1\) のカードであり、テーブル上で物理的に隣接しているカードではない」という点です。 カードが取り除かれたからといって、残りのカードが左に詰められるわけではなく、カードの番号は最初から最後まで変わりません。そのため、各ステップでは単純に「カード \(i\) とカード \(i+1\) が両方とも残っているか」を確認するだけで済みます。

もし、「カードが取り除かれたら配列からその要素を削除する（左に詰める）」という素朴な実装をしてしまうと、要素を詰める操作に \(O(N)\) の時間がかかるため、全体で \(O(N^2)\) の時間計算量になり、最大 \(N=10^6\) の制約では実行時間超過（TLE）になってしまいます。

これを解決するために、「そのカードが現在テーブルに残っているか」を管理するフラグ（目印）の配列を用意します。これにより、配列から要素を物理的に削除することなく、各ステップの処理を \(O(1)\) で行うことができます。

アルゴリズム

1. 各カードの攻撃力を配列 \(A\) で管理します。
2. 各カードがテーブルに残っているかを表す真偽値の配列 alive を用意し、初期値はすべて True とします。
3. \(i = 1, 2, \ldots, N-1\) の順に以下の処理を行います（プログラム上では \(0\) 番目から始まるインデックスに注意します）。
   • alive[i] と alive[i+1] がともに True であるかを確認します。
   • 両方 True であれば、攻撃力 \(A_i\) と \(A_{i+1}\) を比較します。
     • \(A_i > A_{i+1}\) の場合：\(A_i\) に \(\lfloor A_{i+1} / 2 \rfloor\) を加算し、alive[i+1] を False に更新します。
     • \(A_i < A_{i+1}\) の場合：\(A_{i+1}\) に \(\lfloor A_i / 2 \rfloor\) を加算し、alive[i] を False に更新します。
     • 攻撃力が等しい場合は何もしません。
4. 最後に alive 配列の中にある True の個数を数え、それを出力します。

計算量

• 時間計算量: \(O(N)\)
  • 配列を1回ループして隣り合う要素を確認・更新するだけなので、全体の計算量は \(O(N)\) となります。\(N=10^6\) でも制限時間内に余裕で間に合います。
• 空間計算量: \(O(N)\)
  • 攻撃力を保存する配列 \(A\) と、生存フラグを保存する配列 alive を持つため、\(O(N)\) のメモリを使用します。

実装のポイント

• 切り捨て除算: 攻撃力の更新における \(\lfloor Y / 2 \rfloor\) は、Pythonでは // 演算子を使うことで簡単に小数点以下切り捨ての整数除算ができます。

• 高速な入出力: \(N\) が最大 \(10^6\) と大きいため、Pythonでは sys.stdin.read().split() を使って入力を一括で読み込むと、実行速度が上がり安全です。

• 0-indexed: 問題文ではカードの番号が \(1\) から \(N\) となっていますが、実際のプログラミング言語（Pythonなど）では配列のインデックスが \(0\) から始まるため、\(i = 0\) から \(N-2\) までのループとして実装します。

  ソースコード

import sys

def main():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    A = [int(x) for x in data[1:]]
    
    alive = [True] * N
    for i in range(N - 1):
        if alive[i] and alive[i + 1]:
            if A[i] > A[i + 1]:
                A[i] += A[i + 1] // 2
                alive[i + 1] = False
            elif A[i] < A[i + 1]:
                A[i + 1] += A[i] // 2
                alive[i] = False

    print(sum(alive))

if __name__ == '__main__':
    main()

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