https://yukicoder.me/problems/no/568
解説放送
未定
前提知識
解説
https://yukicoder.me/submissions/203734
まず、どこから取り組んでいいか分からないので「何か全探索できそうな所が無いか考えてみよう」
全探索できそうな範囲として、SAの範囲があり、今回はこれを全探索していく方針が想定解。
重要な事実が「SAを順に考えていくと、SBは広義単調減少するということ」
SA=iである時、最適なSBがjであるとする。
この時、SA=i+1の時に最適なSBは必ずj以下となる。
これはSAが増えることで全完する数が増えるかそのままであり、もし減るならばSBを減らして全完人数を増やす必要があるからである。
単調性を持つ2つの値を動かしながら処理するアルゴリズムといえば『尺取法』
方針としては、SAを[0,100000]まで全探索して、SBは最初100001とする。
各SAについて、全完数2~5の人数が初めてM以上となるSBをSBをデクリメントしながら探索する。
初めてM以上となる部分が全完数3~5の人数が最小であることは明らか。
あとは、人数管理が問題となるが、
- 配列a,bを用意して、SA,SBに対応する添字を高速に取得できるようにしておく
- 人数を予めカウントしておき、全完数が変更されるのに従ってカウントを増減させる
ことでO(1)で行うことができる
#define INF INT_MAX/2 int N, M; int X[101010], A[101010], B[101010]; int cnt[10]; //--------------------------------------------------------------------------------------------------- vector<int> a[101010], b[101010]; void _main() { cin >> N >> M; rep(i, 0, N) cin >> X[i] >> A[i] >> B[i]; rep(i, 0, N) { a[A[i]].push_back(i); b[B[i]].push_back(i); } rep(i, 0, N) X[i]++; rep(i, 0, N) cnt[X[i]]++; int ans = INF; int SB = 100001; rep(SA, 0, 100002) { while (cnt[2] + cnt[3] + cnt[4] + cnt[5] < M) { SB--; if (SB < 0) break; fore(i, b[SB]) { cnt[X[i]]--; X[i]++; cnt[X[i]]++; } } if (cnt[2] + cnt[3] + cnt[4] + cnt[5] < M) break; ans = min(ans, cnt[3] + cnt[4] + cnt[5]); fore(i, a[SA]) { cnt[X[i]]--; X[i]--; cnt[X[i]]++; } } cout << ans << endl; }