問題概要
数字からなる文字列 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; } ); } };
