読者です 読者をやめる 読者になる 読者になる

torus711 のアレ

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

TopCoder SRM 611, Division 2, Level 1 : InterestingNumber

問題概要

 数字からなる文字列 x が与えられる。この文字列が、次の condition を共に満たすかどうか判定せよ。

  • 任意の数字 D について、二つの D によって挟まれている数字の数は D が表す値に等しい( D 同士の距離は D + 1 )
  • 任意の数字は、文字列中に一度も出現しないか、丁度 2 回出現するかのいずれかである

解法

 二つの condition は独立に判定することができます。それぞれ

  • インデックスのペア ( i, j ) を全て試し、x[i] と x[j] が等しければその距離を調べ、valid かどうか判定する
  • 全ての数字の出現回数を数え上げ、0 でも 2 でもないものがあるか調べる

とすれば判定できます。両方のテストをパスすれば valid です。

コード

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

#define snd second

class InterestingNumber
{
public:
	string isInteresting( string x )
	{
		return pairing( x ) && counting( x ) ? "Interesting" : "Not interesting";
	}

	bool pairing( const string &s )
	{
		const int L = s.size();

		REP( i, 0, L )
		{
			REP( j, i + 1, L )
			{
				if ( s[i] == s[j] && j - i - 1 != s[i] - '0' )
				{
					return false;
				}
			}
		}
		return true;
	}

	bool counting( const string &s )
	{
		map<char,int> counts;
		FOR( c, s )
		{
			counts[c]++;
		}
		return all_of( ALL( counts ), []( const pair<char,int> &p ){ return p.snd == 0 || p.snd == 2; } );
	}
};