torus711 のアレ

主に競技プログラミングの問題について書きます

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

問題概要

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

解法

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

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

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

コード

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";
	}
};