SRM657 Div2 Hard "ApplesAndOrangesHard"
考えたこと
Div1 Easyの難しい版。Nがとんでもなく大きくなっている。
・・・が、確定リンゴの数は50以下と大したことない。
大半は確定リンゴではない買うも買わないも自由な日となる。
確定リンゴがない場合、最近のK日分のリンゴの買い方をコピペするのがベスト。
なので、自由な日は上記のベストな買い方を適用することによって、一気に消化できる。
考えなければいけないのは確定リンゴのある日だけでよい。
以下の図を見て欲しい。
確定リンゴの日が2日続いており、1個目の確定リンゴは最近のK日の買い方にぴったり当てはまるので、何のこともなく進めることができる。
2個目の確定リンゴは最近のK日の買い方をそのまま続けるわけにはいかない。この場合、K日の中の確定リンゴでなく、かつ最後に買ったリンゴを買わなかったことにして進めていけばよい。
ソースコード
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; } };