WARush

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

SRM657 Div2 Hard "ApplesAndOrangesHard"

考えたこと

Div1 Easyの難しい版。Nがとんでもなく大きくなっている。
・・・が、確定リンゴの数は50以下と大したことない。
大半は確定リンゴではない買うも買わないも自由な日となる。

確定リンゴがない場合、最近のK日分のリンゴの買い方をコピペするのがベスト。
f:id:Ekaing:20150523125238j:plain

なので、自由な日は上記のベストな買い方を適用することによって、一気に消化できる。
考えなければいけないのは確定リンゴのある日だけでよい。

以下の図を見て欲しい。
f:id:Ekaing:20150523125749j:plain
確定リンゴの日が2日続いており、1個目の確定リンゴは最近のK日の買い方にぴったり当てはまるので、何のこともなく進めることができる。
f:id:Ekaing:20150523130023j:plain
2個目の確定リンゴは最近のK日の買い方をそのまま続けるわけにはいかない。この場合、K日の中の確定リンゴでなく、かつ最後に買ったリンゴを買わなかったことにして進めていけばよい。
f:id:Ekaing:20150523130212j:plain

ソースコード

bool A[100050];

class ApplesAndOrangesHard {
public:

    int maximumApples(int N, int K, vector <int> info) {

        for (int i = 0; i < K; i++) {
            A[i] = false;
        }

        sort(info.begin(), info.end());
        for (int i = 0; i < info.size(); i++) {
            info[i]--;
        }

        // 初期配置
        for (int i = 0; i < K / 2; i++) {
            A[i] = true;
        }

        // 番兵
        info.push_back(N);

        // 数え上げ
        int ans = 0;
        int pos = 0;
        for (int i = 0; i < info.size(); i++) {

            int nextA = info[i];

            // K単位で次の確定りんごへ
            int step = (nextA - pos) / K;
            ans += step * (K / 2);
            pos += step * K;

            // 1ずつ次の確定りんごへ
            for (; pos < nextA; pos++) {
                if (A[pos % K]) ans++;
            }

            // 確定りんごが無くなれば終わり
            if (i + 1 == info.size()) break;

            // 確定りんごをとりこむ
            if (A[pos % K]) {
                // すんなりいけば+1
                ans++;
            }
            else {
                // ダメなら最後のりんごを除去
                for (int chkp = pos - 1; ; chkp--) {
                    if (find(info.begin(), info.end(), chkp) != info.end())
                        continue
                    
                    if (!A[chkp % K])
                        continue

                    // 確定リンゴでない最後のリンゴを除去
                    A[chkp % K] = false;
                    A[pos % K] = true;
                    break;
                }
            }
            pos++;
        }

        return ans;
    }
};