SRM479 Div2 Hard(1000) TheBoardingDivTwo
全通り試すだけ。後ろの乗客は、前の乗客が移動する時は移動できるけど、前の乗客が座る時は移動できない、ということに引っかかった。このために着席時間を75秒にするなら、制限時間も1秒増やす必要がある。
#include <vector> #include <algorithm> using namespace std; class TheBoardingDivTwo { public: int find( vector <int> pattern, int boardingTime ); }; int TheBoardingDivTwo::find( vector <int> pattern, int boardingTime ) { int n = (int)pattern.size(); int count = 0; vector<int> perm; for ( int i=1; i<=n; i++ ) perm.push_back( i ); do { bool f = true; for ( int i=0; i<n; i++ ) if ( pattern[i] != -1 && pattern[i] != perm[i] ) f = false; if ( ! f ) continue; vector<int> cell( 2*n+1, 0 ); for ( int i=1; i<=n; i++ ) cell[i] = perm[i-1]; vector<int> wait( n+1, 74+1 ); for ( int t=0; t<boardingTime+1; t++ ) { for ( int i=2*n; i>=1; i-- ) if ( cell[i] != 0 ) { if ( i < n + cell[i] && cell[i+1] == 0 ) cell[i+1] = cell[i], cell[i] = 0; if ( i == n + cell[i] ) if ( --wait[cell[i]] == 0 ) cell[i] = 0; } } f = true; for ( int i=1; i<=2*n; i++ ) if ( cell[i] != 0 ) f = false; if ( f ) count++; } while ( next_permutation( perm.begin(), perm.end() ) ); return count; }