AtCoder が提供しているABC（AtCoder Beginner Contest）323 のD問題をC++で解いてみました。ABC323は、2023年10月7日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Merge Slimes（Difficulty : 852）
問題はリンク先をご覧ください。
小さいサイズのスライムから処理していきます。連想配列を使いました。AtCoder Problems による Difficulty は、852 でした。※2023年10月15日 Difficulty を追記しました。
解答案
サイズ $X$ のスライム2匹を合成すると、サイズ $2X$ のスライム1匹が出現します。最終的にすべてのサイズのスライムは、1匹か0匹かどちらかになります。2匹以上の場合は合成できるからです。
スライムの数は半分になっていきます。最初の $N$ 種類のスライムについて、ある1種類の個数は最大 $C_i = 10^9 = 2^{30}$ ですから、多くても30世代しか合成できません。直感的ですが、そのままシミュレートすれば時間は間に合うことが分かります。
値はとびとびとなるため、連想配列を使います。C++のmapは幸いなことに小さい方から、キーと値を取得することができます。
C++ プログラム例（ABC323D）
上記で考察したように map を使って、合成をシミュレートしていきます。map のキーをスライムのサイズ、値をスライムの個数とします。キーと値の型は、32ビット整数に収まらないため、64ビット整数にしています。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
int main()
{
int n;
cin >> n;
map<ull, ull> slime;
for (int i = 0; i < n; ++i) {
ull s, c;
cin >> s >> c;
slime[s] = c;
}
ull result = 0;
for (auto e : slime) {
ull st = e.first;
ull ct = e.second;
if (ct >= 2) {
slime[st * 2] += ct / 2;
}
result += ct % 2;
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python の ordered map について
Python には、標準で順序付きの map（連想配列）がありません。記事として取り上げることを見送ります。
最後に
この問題は、バーチャルコンテストではありますが、15分ほどで解けました。MAP の使い方にも慣れてきました。
引き続き ABC の問題を紹介していきます。
