AtCoder Beginner Contest 240 D - Strange Balls【Python】
https://atcoder.jp/contests/abc240/tasks/abc240_d
AtCoder ProblemsでDifficulty: 570、Solve Probability: 53%でした。
解けませんでした。コンテスト中に1時間10分ほど時間が残っており、スタックについても知っていたので解きたかった問題でした。
from collections import deque d = deque() ans = 0 for i in range(N): x = A[i] if len(d) == 0: d.append((x, 1)) ans += 1 else: a, b = d[-1] if a != x: d.append((x, 1)) ans += 1 else: if a != b+1: b += 1 d[-1] = (a, b) ans += 1 else: d.pop() ans -= b print(ans)