mayoko’s diary

プロコンとかいろいろ。

SRM 659 div2 hard:ApplesAndOrangesHard

SRM の div2 hard は考察が少し難しいか解法自明でめんどくさい問題, という感じがします。今回は解法自明ですが実装が難しかったです。

解法

りんごの位置は貪欲に決まります。すなわち, 「直前の K 個を見て, K/2 個に達してなかったらりんごを置いて行く」という戦略が有効です。

ですが, この戦略を単純に実装すると O(N) かかり間に合いません。

よく考えると, りんごが置かれると決まっている周辺ではりんごの配置にばらつきがありますが, それ以外の地域では周期 K で決まったりんごの配置がなされます。これに注目して上手いこと実装します。

int K, ret;
deque<int> D;
set<int> S;

void calc(int cur) {
    if (D.size() && D[0] == cur-K) D.pop_front();
    D.push_back(cur);
    ret++;
    if (D.size() > K/2) {
        ret--;
        for (int x = D.size()-1; x >= 0; x--) {
            if (S.count(D[x]) == 0) {
                D.erase(D.begin()+x);
                break;
            }
        }
    }
}

class ApplesAndOrangesHard {
public:
    int maximumApples(int N, int K, vector <int> info) {
        ::K = K;
        D.clear(); S.clear();
        ret = 0;
        for (int el : info) S.insert(el-1);
        S.insert(N);
        int cur = 0;
        for (int el : S) {
            if (el-cur > 2*K+1) {
                for (int t = 0; t < K; t++) calc(cur++);
                int num = (el-cur-1)/K;
                ret += D.size()*num;
                cur += num*K;
                for (int& el : D) el += num*K;
            }
            for (; cur <= el && cur < N; cur++) calc(cur);
        }
        return ret;
    }
};