mayoko’s diary

プロコンとかいろいろ。

SRM 487 div1 easy: BunnyComputer

なんか早解き出来ない…

解法

問題の条件を考えると, 例えば k = 2 の時は, 0, 3, 6, 9, ... 番目の preference に関連性があり, 1, 4, 7, 10, ... 番目の preference に関連性があり, 2, 5, 8, 11, ... 番目の preference に関連性があります。関連性があるってかなり適当な表現ですが, まず (0, 1) みたいにペアをとってもその 2 つを同じウサギがつかう時間帯には出来ませんよね。そういう意味でグループ分けしているのと, あと (0, 3) というペアを決めて, さらに (3, 6) というペアを作ってそれぞれの時間をウサギが使う時間帯にする, というのは, 3 が overlap しているので出来ません。そういう意味で, (0, 6) にも関連性があると言えます。そんな感じです。

上で述べたように, 同じグループでも, すべての時間帯をウサギが使えるように出来るわけではありません。では, その中でどのように時間帯を使うのが有利かというと,
・グループの数が偶数の場合, (0, 3), (6, 9), ... とかすればすべての時間帯を使える
・グループの数が奇数の場合, 0, 6, 12, ... といった グループの偶数番目の時間帯以外すべての時間帯を使えるようなペアの選び方が存在するので, 偶数番目の時間帯の最小値以外をすべて使う

とするのが良いです。

class BunnyComputer {
public:
    int getMaximum(vector <int> preference, int k) {
        int n = preference.size(), ret = 0;
        k++;
        for (int i = 0; i < k; i++) {
            vector<int> v;
            int cur = i, sum = 0;
            while (cur < n) {
                v.push_back(preference[cur]);
                sum += preference[cur];
                cur += k;
            }
            int size = v.size();
            if (size%2 == 0) ret += sum;
            else {
                int mini = sum;
                for (int i = 0; i < size; i+=2) {
                    mini = min(mini, v[i]);
                }
                ret += sum-mini;
            }
        }
        return ret;
    }
};