TopCoder SRM 581, Division 1, Level 1 ( Division 2, Level 2 ) : SurveillanceSystem

概要

'-' と 'X' からなる長さ N の文字列が与えられる。
この文字列上に、次の条件を満たすように長さ L の区間を幾つかプロットする。

• i 番目の区間の中に 'X' は丁度 reports[i] 個ある
• 全く同じ区間を覆うようには配置できない

このとき、i 番目の文字が次のようになる文字列を生成せよ。

• 場所 i が一つ以上の区間に覆われる -> '+'
• 場所 i が区間に覆われない -> '-'
• どちらともいえない -> '?'

なお、全ての区間を矛盾無く置けることが保証されている。

解法

まず、、任意の i, j について、reports[ i ] ≠ reports[ j ] ならば同じ区間を覆うことはできません。
従って、区間に含まれる 'X' の数ごとにまとめて処理をすると重複を防ぐことができます。

では、'X' を n 個含む区間群のみを処理する場合について考えます。
あるインデックスについて、その場所を被覆する置き方の数 ＞（置き方の総数 - 置く区間の数 = 候補のうち置けない区間の数）　を満たすとき、その場所は '+' になります。
この条件も満たさないとき、「候補にはなっているが置かれるかどうか分からない場所」なので '?' です。

n を全通り試すと、各場所について答えとなる候補の文字が求まります。
「確実に覆われない」より「覆われる場合がある」方が強く、「覆われる場合がある」より「確実に覆われる」方が強いと考えると、その優先度は '-' < '?' < '+' となります。
この場合、初期値として max() の単位元である '-' を埋めておけば例外処理が必要無くなります。

コード

typedef vector<int> VI;
typedef vector<VI> VVI;

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

#define PB( n ) push_back( n )

#define fst first
#define snd second

map<char,int> priority;

struct comp_priority : binary_function<char,char,bool>
{
	bool operator ()( const char a, const char b ) const
	{
		return priority[a] < priority[b];
	}
};

class SurveillanceSystem
{
public:
	string getContainerInfo( string containers, vector <int> reports, int L )
	{
		priority[ '-' ] = 0;
		priority[ '?' ] = 1;
		priority[ '+' ] = 2;

		const int N = containers.size();
		sort( ALL( reports ) );

		VVI leftmost( N + 1 );
		REP( i, 0, N - L + 1 )
		{
			string sub = containers.substr( i, L );
			leftmost[ count( ALL( sub ), 'X' ) ].PB( i );
		}

		string res( N, '-' );
		REP( i, 0, L + 1 )
		{
			int num;
			{
				pair< ITER(VI()), ITER(VI()) > poss = equal_range( ALL( reports ), i );
				num = distance( poss.fst, poss.snd );
			}

			if ( num == 0 )
			{
				continue;
			}

			VI counts( N );
			REP( j, 0, leftmost[i].size() )
			{
				REP( k, leftmost[i][j], leftmost[i][j] + L )
				{
					counts[k]++;
				}
			}

			REP( j, 0, N )
			{
				if ( counts[j] == 0 )
				{
					continue;
				}
				char c = counts[j] > leftmost[i].size() - num ? '+' : '?';
				res[j] = max( res[j], c, comp_priority() );
			}
		}

		return res;
	}
};