kojingharangの日記

SRM 659 Div1 250 ApplesAndOrangesEasy

23:19 |

• GarthがN個のりんごかオレンジをある順序で食べた。そのうちいくつかのリンゴに関しては食べた番目が与えられる。
• 連続する K 個の中で K/2 以下のりんごしか食べてない場合、りんごの最大個数を求めよ。
• 2≦K≦N≦2000

• dp? いや最後の K 個のパターンをキーにするにしては K が大きすぎる
• 左から置けるとこに貪欲に置いてだめな理由もなさそうだ
• おけるところをどうやって覚えておくか...
• 直近 K 個の和を計算しておいて、それを配ってmaxを取っておいたものが K/2 より小さければ置けそうだ
• めっちゃはまる
• 終了間際 あれこれN^3だだめだ

• (あとで)

• 冷静に考えると置けるかの判定は K 個の sum を見て良くて、置いた時の sum の更新も K 回、全体で O(N^2) にすればよかったのだ
• 置けるかチェック O(1) 更新 O(N^2) にしてしまっていた。
• それか BIT を使って置けるかの判定にO(NlogN)、更新にO(logN)でもいい。
• うむー全然だめだ。

• accepted in practice

class ApplesAndOrangesEasy {
	public:
	int maximumApples(int N, int K, vector <int> info) {
		VI w(N), sum(N); // sum of [i-K+1, i]
		REP(i, info.size()) w[info[i]-1]=1;
		REP(i, N) RANGE(j, max(0, i-K+1), i+1) sum[i]+=w[j];
		ll ans=info.size();
		REP(i, N) if(!w[i]) {
			bool ok=true;
			RANGE(j, i, min(N, i+K)) if(sum[j]>=K/2) ok=false;
			if(!ok) continue;
			ans++;
			RANGE(j, i, min(N, i+K)) sum[j]++;
		}
		return ans;
	}
};

ツイートする