公式解説

aac003_c1 解説

初日の一部時間帯で、テストケースに誤りがありました。大変申し訳ございません。

各テストケースについて、どのように操作しても消す回数は変わらないことがわかると思います。実際に消す操作を以下の方法でシミュレーションできます。

1. $A_i = A_{i+1}$ を満たす $i$ をとる
2. $A_i$ と一致する $A$ の要素を削除する
3. 削除した地点に隣接していた2つの値が隣接している場合、それらも削除する
4. 3 により要素を削除した場合は、それらについても 3 を再度適用する

一見、再帰的な操作となっていて指数的な計算量になりそうですが、それぞれの要素が削除される回数は高々 1 回なので、$\mathcal O(N)$ 回に抑えられます。

双方向リストを使うことにより解くことができます。

双方向リストとは、自分の要素の次の要素と前の要素を所持するもので、イメージ的にはセロハンテープのつなぎ合わせのようなものです。
その性質により、あるテープについて注目しているときそのテープを $\mathcal O(1)$ で削除し、その前と後ろのテープを連結させることができます。
標準ライブラリに std::list として含まれていますので、これを使うと実装が楽になるかもしれません。

また、std::set を使った実装も存在し、std::set::erase が直後のイテレータを返却することを利用すると容易な実装が可能です。
この場合、計算量は $\mathcal O(N\log N)$ で、十分高速です。

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T;
	cin >> T;

	long long ans = 0;

	while (T--)
	{
		int N;
		cin >> N;

		vector<int> A(N);
		for (int i = 0; i < N; i++)
			cin >> A[i];

		list<pair<int, int>> lst;
		vector<list<pair<int, int>>::iterator> itrs(N);
		vector<bool> alive(N, true);

		unordered_map<int, vector<int>> pos;

		for (int i = 0; i < N; i++)
		{
			lst.emplace_back(A[i], i);
			itrs[i] = prev(lst.end());
			pos[A[i]].push_back(i);
		}

		unordered_set<int> removed_val;

		queue<int> q;
		for (int i = 0; i < N - 1; i++)
		{
			q.push(i);
		}

		while (!q.empty())
		{
			int i = q.front();
			q.pop();

			if (!alive[i])
				continue;

			auto it = itrs[i];
			if (it == lst.end())
				continue;

			auto nxt = next(it);
			if (nxt == lst.end())
				continue;

			if (!alive[nxt->second])
				continue;
			if (it->first != nxt->first)
				continue;

			int val = it->first;

			if (removed_val.count(val))
				continue;
			removed_val.insert(val);

			ans++;

			for (int idx : pos[val])
			{
				if (!alive[idx])
					continue;

				auto cur = itrs[idx];

				auto before = (cur == lst.begin() ? lst.end() : prev(cur));
				auto after = next(cur);

				alive[idx] = false;
				lst.erase(cur);

				if (before != lst.end())
				{
					q.push(before->second);
				}
			}
		}
	}

	cout << ans << "\n";
}
Copy