はまやんはまやんはまやん

hamayanhamayan's blog

じゃんじゃん 落とす 委員会 [yukicoder No.568]

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;
}