まず、最も上にある駒を動かす必要はありません。また、最も上にある駒の左右の駒は少なくとも最も上にある駒の一つ下の行まで持ってくる必要があります。

この考察を繰り返すと、上にある駒から順番に左右の駒を自身の一つ下の行まで持ってくる操作を繰り返すことでこの問題に正答できることが分かります。駒の場所は各操作によって変わりますが、優先度付きキューなどを用いてこのシミュレーションを実装することができます。

計算量は \(O(N \log N)\) で、公式解説よりは計算量が劣りますがこちらの解法の方が自然に思いつきやすいと思います。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> r(n);
		for (int &v : r) cin >> v;
		using pli = pair<long, int>;
		priority_queue<pli, vector<pli>, greater<pli>> pq; // {a[i], i} のペアを a[i] の昇順で持つ
		for (int i = 0; i < n; i++) pq.push({r[i], i});
		vector<int> a = r;
		while (!pq.empty()) {
			const auto [ai, i] = pq.top();
			pq.pop();
			if (a[i] != ai) continue; // 優先度付きキューに残っている古い情報が取り出された場合すぐに捨てる
			if (i != 0 && a[i - 1] > a[i] + 1) {
				a[i - 1] = a[i] + 1;
				pq.push({a[i - 1], i - 1});
			}
			if (i != n - 1 && a[i + 1] > a[i] + 1) {
				a[i + 1] = a[i] + 1;
				pq.push({a[i + 1], i + 1});
			}
		}
		long ans = 0;
		for (int i = 0; i < n; i++) ans += r[i] - a[i];
		cout << ans << '\n';
	}
}