SRM 609

250を247.03点,500を301.81点で通した. 撃墜に2回失敗して498.84点で228位. 500がいつもより簡単で,速さが求められる回だった.

250: MagicalStringDiv1

問題

’>‘と’<‘からなる文字列Sが与えられる. 任意の非負整数kに対して,k個の’>‘の後ろにk個の’<‘を連結した文字列をmagicalという. Sのmagicalな部分列のうち,最大の長さのものを求めよ.

解法

部分列の長さを固定すると,magicalなものが取れるかどうかは,貪欲に取れば判定できる. 長さ2 * kの部分列が取れる時は長さ2 * (k - 1)の部分列も取れるので, 長さ2から順に大きくしながら,取ることが可能かどうかを判定すれば最大のものが取れる.

コード

int getLongest(string s){
    int ans = 0;
    for(int k = 1; ; k++){
        int cnt = 0;
        for(int i = 0; i < s.size(); i++){
            if(cnt < k){
                if(s[i] == '>') cnt++;
            }else{
                if(s[i] != '>') cnt++;
            }
        }
        if(cnt >= 2 * k){
            ans = 2 * k;
        }else {
            break;
        }
    }
    return ans;
}

500: PackingBallsDiv1

問題

K色のボールがある.色iのボールはX[i]個ある. これらのボールをすべて取り除くことを考える.

操作は二種類ある.

  • 1からKの間の好きな数xと色を1つ選び,その色のボールをx個取り除く.(normal)
  • 1からKの間の好きな数xと色をx個選び,それらの色のボールを1個づつ取り除く.(vary)

すべて取り除くために必要な操作の最小回数を求めよ.

解法

取り除く個数や色を自由に選べるので, なるべく1回の操作で多くの個数を取り除くことを考える. とりあえずX[i]がK以上のときは,K個取り除けるので最初に取り除く.

残りのボールは各色K個以内なので,下図のようにK×Kの正方形に詰め込むことできる. このとき, normalな操作はある列を取り除くこと,varyな操作はある行を取り除くことに相当する.

色が個数の大きい順に並んでいるとする. 色1から色iまでnormalで取り除く場合,必要な残りのvaryの回数は色i+1のボールの個数に等しい. iを0からK - 1まですべて調べることで操作の最小回数が求まる.

コード

int minPacks(int K, int A, int B, int C, int D){
    vector<long long> X(K);
    X[0] = A;
    for(int i = 1; i < K; i++){
        X[i] = (X[i-1] * B + C) % D + 1;
    }
    long long init_cost = 0;
    for(int i = 0; i < K; i++){
        long long cnt = X[i] / K;
        init_cost += cnt;
        X[i] -= cnt * K;
    }
    sort(X.begin(), X.end(), greater<long long>());
    long long mini_cost = K;
    for(int i = 0; i < K; i++){
        mini_cost = min(mini_cost, i + X[i]);
    }
    return init_cost + mini_cost;
}
More Reading
Newer// IOPC2014