問題概要
n 個の '0' と m 個の '1' を、以下の二つの condition を共に満たすような並べ方で並べよ。そのような並べ方が存在しないとき、-1 で示せ。
- '0' 同士は隣接しない
- 連続する 3 個の文字が '1' となることは無い
解法
まず、一つ目の条件から、二つの '0' の間に 1 個以上の '1' を挟む必要があります。また、'1' の配置は、'0' の間に 1 〜 2 個ずつ配置するか、一番外側に 1 〜 2 個くっつけるかしかできません。これらの制約から、並べ方が存在しないケースは次のいずれかの条件を満たすときです。
- m < n - 1 を満たす
- ( n - 1 ) * 2 + 4 < m を満たす
いずれの条件も満たさないとき、適切に並べることで目標を達成することができます。
並べる際には、"010101010" のような列に対し、余った '1' を挿入可能な位置に挿入すると考えると分かりやすいと思います。配置の戦略としては、
- '0' に挟むだけでは並べきれない '1' があれば、先頭に( 2 個までの範囲で)置く
- (置くべき '0' があれば)1 個置く
- '0' が残っている間、次のように繰り返す
- 残りの '0' より '1' の方が多いならば 2 個、そうでないなら 1 個の '1' を置く
- 1 個の '0' を置く
- 最後に、'1' が余っているならばそれを末尾に付ける
コード
#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) int main() { cin.tie( 0 ); ios::sync_with_stdio( false ); int n0, n1; cin >> n0 >> n1; if ( n1 < n0 - 1 || ( n0 - 1 ) * 2 + 4 < n1 ) { cout << -1 << endl; return 0; } for ( int iteration = 0; iteration < 2 && ( n0 - 1 ) * 2 + 2 < n1; iteration++ ) { cout << 1; n1--; } if ( 0 < n0 ) { cout << 0; n0--; } while ( 0 < n0 ) { if ( n0 < n1 ) { cout << 1; n1--; } cout << 10; n1--; n0--; } while ( 0 < n1 ) { cout << 1; n1--; } cout << endl; return 0; }