SRM520 Div1 Easy SRMCodingPhase

2015/08/08 (Sat) SRM 全探索

問題

問題文

方針

$luck$ をどの問題に何分割り振るかを全探索する． さらに各場合において，$3$ 問それぞれを解く/解かないの $2^3$ 通りの場合分けを全探索する． 時間内に収まるなら，そのとき得られる点数で答えを更新する． $O(luck^3 2^3)$ となってとても遅そうだけど，制約が緩いので間に合う．

実際は $luck$ の割り振り方は， 解く問題の組み合わせと順番を決めたら得点の高いものから全力で投入するのが最適なので，もっと効率良く解ける．

実装

class SRMCodingPhase {
public:
    int countScore(vector <int> p, vector <int> q, int luck) {
        int ans = 0;
        rep(ii,luck+1)rep(jj,luck+1)rep(kk,luck+1){
            if(ii+jj+kk > luck) continue;
            vi time = { q[0]-(int)ii, q[1]-(int)jj, q[2]-(int)kk };
            rep(i,3) time[i] = max(1,time[i]);
            vi score = { p[0]-2*time[0], p[1]-4*time[1], p[2]-8*time[2] };
            rep(mask,8){
                int t = 0, s = 0;
                rep(i,3){
                    if(mask>>i&1){
                        t += time[i];
                        s += score[i];
                    }
                }
                if(t <= 75) ans = max(ans,s);
            }
        }
        return ans;
    }
};