概要

カードの番号に基づいて順番に戦わせ、強い方が弱い方を吸収していくゲームをシミュレートし、最後に残るカードの枚数を求めます。

考察

この問題では、カードが一列に並んでおり、番号順に隣接するカード同士が戦うことになります。ただし、戦うたびにカードが消えるため、実際に「隣接している」状態が変わるわけではありません。重要なのは、番号が \(i\) と \(i+1\) であるカード同士が対象であり、それが物理的に隣接していなくても関係ないということです。

例えば、\(i=1\) の処理でカード1とカード2が戦ってカード2が消えたとしても、次に \(i=2\) の処理ではカード2とカード3が対象なので、カード2がいない場合はスキップします。

素朴な方法では毎回カードの位置を調べたり、リストを詰めたりすると、最悪の場合で \(O(N^2)\) の計算量になり、\(N\) が最大 \(10^6\) なので間に合いません。

この問題のポイントは、「カードの番号は変わらない」「戦う順番が固定されている」という点です。つまり、各カードが今どこにいるのか、または存在するのかを高速に管理できれば良いのです。

そこで、各カードの現在の攻撃力と、存在しているかどうか（位置情報）を別々に管理することで、シミュレーションを効率的に行えます。

アルゴリズム

1. 各カードの初期攻撃力を保持する配列 current_atk を用意します。
2. 各カードがまだ存在しているかどうかを示す配列 pos を用意します。pos[i] にはカード \(i\) が存在していればそのインデックス、消えていれば \(-1\) を入れます。
3. \(i = 0\) から \(N-2\) まで順番に処理します：
   • カード \(i\) とカード \(i+1\) のどちらかがすでに消えていたらスキップ。
   • 両者が存在していれば攻撃力を比較：
     • 同じならスキップ。
     • 違うなら、強い方が弱い方を吸収し、吸収した側の攻撃力を更新、吸収された方は pos を \(-1\) にする。
4. 最後に pos を見て、\(-1\) でないものの個数を数えれば、それが答えです。

この方法により、各ステップで定数時間で判定できるため、全体で \(O(N)\) で処理可能です。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• カードの番号と実際の位置を分けて管理することが重要です。

• 吸収後の新しい攻撃力の計算は、\(\text{atk} + \left\lfloor \frac{\text{相手のatk}}{2} \right\rfloor\) です。

• リストではなく配列で位置と攻撃力を管理することで、アクセスを高速化できます。

  ソースコード

import sys
from collections import deque

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    A = list(map(int, data[1:]))

    # リストをデックに変換して効率的に操作を行う
    cards = deque()
    for i in range(N):
        cards.append([A[i], i])  # [攻撃力, インデックス]
    
    # 処理の順序: i = 1 to N-1 => インデックス0 to N-2
    # 各処理は番号iとi+1のカードに対して行う
    
    # 位置情報を管理する配列: pos[i] = カードiが現在cards中の何番目にいるか(-1なら除去済み)
    pos = list(range(N))
    
    # 各カードの現在の攻撃力を保持する配列
    current_atk = A[:]
    
    # 各iについて処理を行う
    for i in range(N-1):
        idx1 = pos[i]
        idx2 = pos[i+1]
        
        if idx1 == -1 or idx2 == -1:
            continue
            
        atk1 = current_atk[i]
        atk2 = current_atk[i+1]
        
        if atk1 == atk2:
            continue
        elif atk1 > atk2:
            # カードiがカードi+1を吸収
            current_atk[i] += atk2 // 2
            pos[i+1] = -1
        else:
            # カードi+1がカードiを吸収
            current_atk[i+1] += atk1 // 2
            pos[i] = -1

    # 残っているカードの数をカウント
    count = sum(1 for p in pos if p != -1)
    print(count)

if __name__ == "__main__":
    main()

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