AtCoder ABC 379 C - Sowing Stones

コンテスト中に解けなかった問題を、自分的にわかりやすいコーディングで書き直したメモです。

トライアル＆エラーで問題切り分けて、やっと何故通せなかったかわかった。

これ300点問題にするなら、サンプルにソートされていないパターン入れておいてくれぃ(;´･ω･)

Main.cpp

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
struct cell
{
	ll index;
	ll count;
};

// 石が移動可能な空マスが足りているかチェックする
bool CanComplete( const vector<cell> & vecCells, ll N )
{
	ll r = N;			// 検証済みの終端
	ll emptyCount = 0;	// 検証中の空マスの数

	// 終端（右）からチェック
	for( auto itr = vecCells.rbegin(); itr != vecCells.rend(); ++itr)
	{
		// 終端からここまでの空マスを数える
		emptyCount += r - itr->index;
		// 今のマスで余った石の移動先の空マスが足りているか確認
		if( itr->count - emptyCount > 1 )
		{
			return false;	// 不可能
		}
		// 今のマスに1個残しておけば残りは移動して空白のマスを埋められる
		emptyCount -= (itr->count)-1;
		r = itr->index - 1;
	}

	return true;	// 可能
}


int main( void )
{
	// 入力
	ll N, M;
	cin >> N >> M;

	// 石の合計数
	ll stoneCount = 0;
	// マスのindex値をスコアとみなした場合の初期状態のスコア
	ll scoreInit = 0;
	// すべてのマスに石が１個ずつ入っていた場合のスコア
	//   遷移が可能な場合は、この差分が答え
	ll scoreComplete = ( 1 + N ) * N / 2;

	vector<cell> vecCells(M+1);	//
	for( ll i = 1; i <= M; ++i)
	{
		cin >> vecCells[i].index;
	}
	for( ll i = 1; i <= M; ++i)
	{
		cin >> vecCells[i].count;
		stoneCount += vecCells[i].count;
		scoreInit += vecCells[i].count * vecCells[i].index;
	}

	// 石の合計数とマスの数が合わなかったらそもそも不可能なのでここで終了
	if( stoneCount != N )
	{
		cout << "-1" << endl;
		return 0;
	}

	// 入力がソートされていないらしいので（#^ω^） index の昇順にしておく
	 sort( vecCells.begin(), vecCells.end(),
	 			[]( const cell & a, const cell & b){ return a.index < b.index; });

	// 始点のマスに石がなかったらそもそも不可能なのでここで終了
	if( vecCells[1].index != 1)
	{
		cout << "-1" << endl;
		return 0;
	}

	// 右に移動するだけで完了状態に遷移できるかチェック
	ll result;
	if( CanComplete( vecCells, N ))
	{
		// 遷移が可能な場合はこれで求められる
		result = scoreComplete - scoreInit;
	}
	else
	{
		result = -1;
	}
	cout << result << endl;

	return 0;
}