WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
    }
};