SRM569 Div1 Medium "TheJediTest"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12265
訳
遠い昔、そして遠く離れた星にあるジェダイ養成学校で、入学試験が行われた。このテストはN階建てのジェダイ聖堂で行われた。i階には、最初、student[i]人の子供が集まった。1人のジェダイは多くとも同じ階のK人の子供を監督する事ができた。だからもしある階にK+1~2Kの子供がいたら、その階に2人のジェダイが、2K+1~3Kの子供がいたら3人のジェダイが必須となる。
この試験の監督に必要なジェダイの人数を最小化するために、子供達の再配置を行う事になった。しかし、混乱を避けるため、各子供は多くとも1階までの移動のみ許可された。具体的には、各子供は、始め集まった階に留まるか、1階下に移動するか、1階上に移動するかである。一番下の階からさらに下の階に移動する事や、一番上の階からさらに上の階への移動はできないことに留意せよ。
再配置を行った後の、最小のジェダイの数を返せ。
制約
1 <= N <= 20
1 <= 各階の生徒数 <= 10^8
1 <= K <= 10^8
考えた事
当時何回やっても最後のSampleが合わなくて断念したけど、再チャレンジ。
1階上、1階下へ移動させる事ができるので、着目している階と隣り合う階の3つの階で考えていく。
例えば、下から上に走査していくとし、階0, 1, 2を考えると、階0の生徒は取り残す訳にはいかない。なので、階0の生徒を監督するに必須なジェダイの数を出し、まだ監督数に余裕があるようなら、階1,2の生徒を取り込んでいく。
というように貪欲にやっていけばACした。
ソースコード
class TheJediTest { public: int minimumSupervisors(vector <int> S, int K){ int N = S.size(); int res = 0; if( N <= 3 ){ // 3階建て以内なら合計してKで割るだけ int sum = 0; for( int i = 0; i < N; i++ ){ sum += S[i]; } res = sum / K + (sum % K ? 1 : 0); }else{ for( int i = 0; i < N - 2; i++ ){ if( i + 2 == N - 1 ){ // 最後の3階なら合計してKで割るだけ int sum = S[i] + S[i+1] + S[i+2]; res += sum / K + (sum % K ? 1 : 0); }else{ if( S[i] == 0 ) continue; int sum = S[i] + S[i+1] + S[i+2]; res += sum / K; int rem = sum % K; S[i+2] = min( S[i+2], rem ); rem -= S[i+2]; S[i+1] = min( S[i+1], rem ); rem -= S[i+1]; if( rem > 0 ){ res++; rem = K - rem; int dis = min( S[i+1], rem ); rem -= dis; S[i+1] -= dis; dis = min( S[i+2], rem ); S[i+2] -= dis; } } } } return res; } };