概要

番号が隣り合うカードのペア \((i, i+1)\) を \(i=1\) から順に 各1回だけ 処理し、吸収でカードが消える・攻撃力が増える操作をそのままシミュレーションして、最後に残る枚数を数える問題です。

考察

重要なのは、「処理対象は“物理的に隣接しているカード”ではなく、番号が \(i\) と \(i+1\) のカード」という点です。
つまり、カードが途中で取り除かれても、次に比較する相手が「残っている中で隣」へスライドしたりはしません。

このため、各 \(i\) について見るべきなのは常に「カード \(i\) とカード \(i+1\) が生きているか」「生きているなら最新の攻撃力はいくつか」だけです。
処理は \(i=1,2,\dots,N-1\) で一方向に一度ずつなので、

• カード \(i\) の攻撃力が変わる可能性があるのは、直前の処理 \((i-1,i)\)（で \(i\) が吸収した/された）と、今の処理 \((i,i+1)\) のみ
• したがって、配列を左から1回なめるだけで十分

という構造になっています。

素朴に「残っているカード同士の隣接関係が変わる」と誤解すると、リンクリストや Union-Find 的に“次の生存カード”を探す実装を考えてしまいがちですが、この問題では不要です（むしろ実装が複雑になりやすいです）。
必要なのは「生存フラグ」と「攻撃力配列」の更新だけです。

アルゴリズム

以下をそのままシミュレーションします。

1. 配列 A[i] にカード \(i\) の現在攻撃力を持つ（吸収で更新する）。
2. 配列 alive[i]（生存フラグ）を用意し、初期値は全て生存。
3. \(i=1\) から \(N-1\) まで順に（実装では 0-index なので i=0..N-2）処理する：
   • alive[i] または alive[i+1] が 0（死亡）なら何もしない
   • 両方生存なら攻撃力を比較
     • 等しい：何もしない
     • \(A[i] > A[i+1]\)：カード \(i\) が吸収
       alive[i+1]=0、A[i] = A[i] + floor(A[i+1]/2)
     • \(A[i] < A[i+1]\)：カード \(i+1\) が吸収
       alive[i]=0、A[i+1] = A[i+1] + floor(A[i]/2)
4. 最後に alive の 1 の個数を数えて出力する。

具体例

\(A=[10, 6, 20]\) のとき： - \(i=1\)（カード1と2）：\(10>6\) なので 1 が 2 を吸収
カード2消滅、カード1の攻撃力は \(10+\lfloor 6/2\rfloor=13\) - \(i=2\)（カード2と3）：カード2はすでに消えているので何もしない
最終的に残るのはカード1と3の2枚です。

計算量

• 時間計算量: \(O(N)\)（各ペアを1回ずつ見るだけ）
• 空間計算量: \(O(N)\)（攻撃力配列と生存フラグ）

実装のポイント

• \(N \le 10^6\) なので、Python では入出力がボトルネックになりやすいです。コードでは sys.stdin.buffer.read() と自前パーサで高速に整数を読み取っています。

• 生存フラグは bytearray にしてメモリを節約しつつ、最後は alive.count(1) で枚数を数えています。

• 吸収後の攻撃力更新は必ず + (相手 // 2)（床関数）です。攻撃力は更新され、以降の比較に使われる点に注意します。

  ソースコード

import sys

data = sys.stdin.buffer.read()
L = len(data)
p = 0

def readint():
    global p
    while p < L and data[p] <= 32:
        p += 1
    num = 0
    while p < L and data[p] > 32:
        num = num * 10 + (data[p] - 48)
        p += 1
    return num

N = readint()
A = [0] * N
for i in range(N):
    A[i] = readint()

alive = bytearray(b"\x01") * N

for i in range(N - 1):
    if alive[i] and alive[i + 1]:
        ai = A[i]
        aj = A[i + 1]
        if ai > aj:
            alive[i + 1] = 0
            A[i] = ai + (aj // 2)
        elif ai < aj:
            alive[i] = 0
            A[i + 1] = aj + (ai // 2)

sys.stdout.write(str(alive.count(1)) + "\n")

この解説は gpt-5.2-high によって生成されました。