概要

\(N\) 枚のカードを左から順に番号 \(i\) と \(i+1\) のペアで比較し、攻撃力が異なれば強い方が弱い方を吸収する処理を \(i = 1, 2, \ldots, N-1\) の順に行い、最終的にテーブルに残るカードの枚数を求める問題です。

考察

問題の整理

この問題では、処理の順番が \(i = 1, 2, \ldots, N-1\) と固定されている点が重要です。つまり、まずカード \(1\) とカード \(2\) を比較し、次にカード \(2\) とカード \(3\) を比較し…と、番号の小さいペアから順に処理します。

各ステップ \(i\) では： - カード \(i\) またはカード \(i+1\) のどちらかが既に取り除かれていれば何もしない - 両方残っていて攻撃力が等しければ何もしない - 両方残っていて攻撃力が異なれば、強い方が弱い方を吸収する

具体例で理解する

例えば \(N = 4\), \(A = [3, 5, 2, 5]\) の場合：

1. \(i=1\): カード1（攻撃力3）とカード2（攻撃力5）を比較。\(5 > 3\) なのでカード2がカード1を吸収。カード1は除去、カード2の攻撃力は \(5 + \lfloor 3/2 \rfloor = 5 + 1 = 6\) に更新。
2. \(i=2\): カード2（攻撃力6）とカード3（攻撃力2）を比較。\(6 > 2\) なのでカード2がカード3を吸収。カード3は除去、カード2の攻撃力は \(6 + \lfloor 2/2 \rfloor = 6 + 1 = 7\) に更新。
3. \(i=3\): カード3（攻撃力2）は既に除去済み → 何もしない。

最終的にカード2（攻撃力7）とカード4（攻撃力5）が残り、答えは 2 です。

アプローチの妥当性

処理は \(i = 1\) から \(N-1\) まで1回ずつしか行わないため、ループ回数は \(N-1\) 回で固定です。各ステップは \(O(1)\) で処理できるので、素朴にシミュレーションするだけで十分高速です。特別なデータ構造やアルゴリズムは不要です。

アルゴリズム

1. 各カードがテーブルに残っているかを管理する配列 alive を用意し、全て True で初期化する。
2. \(i = 0, 1, \ldots, N-2\)（0-indexed）の順にループを回す。
   • alive[i] と alive[i+1] が両方 True でなければスキップ。
   • \(A[i] = A[i+1]\) ならスキップ。
   • \(A[i] > A[i+1]\) なら、\(A[i]\) を \(A[i] + \lfloor A[i+1] / 2 \rfloor\) に更新し、alive[i+1] = False とする。
   • \(A[i] < A[i+1]\) なら、\(A[i+1]\) を \(A[i+1] + \lfloor A[i] / 2 \rfloor\) に更新し、alive[i] = False とする。
3. alive 配列中の True の個数を出力する。

計算量

• 時間計算量: \(O(N)\) — ループは \(N-1\) 回で各ステップ \(O(1)\)
• 空間計算量: \(O(N)\) — 攻撃力配列と alive 配列

実装のポイント

• 入力の高速化: \(N\) が最大 \(10^6\) と大きいため、sys.stdin.buffer.read() でまとめて読み込むことで入力を高速化しています。

• 整数除算: Python の // 演算子は負でない整数に対して床関数と同じ動作をするため、\(\lfloor Y / 2 \rfloor\) をそのまま A[i] // 2 で計算できます。

• 0-indexed と 1-indexed: 問題文は 1-indexed ですが、実装では 0-indexed で配列を扱っています。ループ範囲 range(N-1) が問題文の \(i = 1, \ldots, N-1\) に対応します。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    A = [int(input_data[i + 1]) for i in range(N)]
    
    # alive[i] = True if card i is still on the table
    alive = [True] * N
    
    for i in range(N - 1):
        # Process pair (i, i+1)
        if not alive[i] or not alive[i + 1]:
            continue
        
        if A[i] == A[i + 1]:
            continue
        
        if A[i] > A[i + 1]:
            # Card i absorbs card i+1
            A[i] = A[i] + A[i + 1] // 2
            alive[i + 1] = False
        else:
            # Card i+1 absorbs card i
            A[i + 1] = A[i + 1] + A[i] // 2
            alive[i] = False
    
    print(sum(alive))

main()

---

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