TopCoder, SRM 625, Division 2, Level 2 : IncrementingSequence

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=12107&rd=15858

問題概要

　 項からなる数列 と正整数 が与えられる。この数列に対し、 を に置き換える操作を任意回できる。 をサイズ の順列にすることができるか否か求めよ。
　なお、サイズ の順列とは、項数が であって、] の整数が丁度一回ずつ出現する列である。

解法

　 のそれぞれについて、小さい方からそれを作れるか否か判定していく、と考えます。このとき、 を生成できるのは、 の内最も小さい値だけです。従って、 ならば は作れません。
　　は作れたとして、次に の場合について考えます。このとき、 未満の の要素はもうそのままでは使えないので、全て を足されなければなりません。その後で、 なる の要素が残っていなければ、 を作ることはできません。
　これを一般化すると、整数 を作りたいとき、以下のように処理すれば、 を作れるか否か判定できます。

1. なる の要素に対し、不等式を満たさなくなるまで を足す
2. なる の要素が存在すれば、その要素で を作るとしてそれを取り除く。存在しないならば は作れない

　この処理を実装するとき、最小ヒープを使うと楽に書くことができます（下のコードを参照してください）。

コード

using VI = vector<int>;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()

class IncrementingSequence
{
public:
	string canItBeDone( int k, vector <int> A )
	{
		priority_queue< int, VI, greater<int> > que( ALL( A ) );

		REP( t, 1, A.size() + 1 )
		{
			while ( que.top() < t )
			{
				const int c = que.top();
				que.pop();
				que.push( c + k );
			}

			if ( t < que.top() )
			{
				return "IMPOSSIBLE";
			}

			que.pop();
		}

		return "POSSIBLE";
	}
};