AtCoder が提供しているABC（AtCoder Beginner Contest）351 のC問題をC++とPythonで解いてみました。ABC351は、2024年4月27日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Merge the balls（Difficulty : 228）
問題はリンク先をご覧ください。
問題で示されている操作を実装するだけです。AtCoder Problems による Difficulty は 228 でした。
解答案
列には、$2^{A_i}$ ではなくて、$A_i$ を格納することにします。3番目の操作で、ボールの大きさが倍になるため、代わりに $A_i + 1$ を格納します。
計算量ですが、コンテナへの追加は、いま格納されているボールの個数を超えません（2個が1個になるため）。このため $i$ 回目の操作の結果、格納されているボールは $i$ 個より多くはなりません。したがって、操作の計算量は $O(N)$ となります。
C++ プログラム例（ABC351C）
C++ の vector コンテナを使います。問題で示されている3つの操作をそのまま実装しました。以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
int n;
cin >> n;
vector<ll> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<ll> result;
for (int i = 0; i < n; ++i) {
result.push_back(a[i]);
while (1) {
int s = result.size();
if (s == 1) {
break;
}
if (result[s - 1] != result[s - 2]) {
break;
}
ll t = result[s - 1] + 1;
result.pop_back();
result.pop_back();
result.push_back(t);
}
}
cout << result.size() << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC351C）
Python 版も基本的な考え方は同じです。リストを使います。以下となります。
"""AtCoder Beginner Contest 351 C"""
n = int(input())
a = list(map(int, input().split()))
result = []
for i in range(n):
result.append(a[i])
while True:
if len(result) == 1:
break
if result[-1] != result[-2]:
break
t = result.pop() + 1
result.pop()
result.append(t)
print(len(result))こちらも「AC」と判定されました。
最後に
操作の実装自体は難しくありませんでした。一方、計算量については、考察する必要がありました。
引き続き ABC の問題を紹介していきます。
