Codeforces Round #654 (Div. 2) E - Asterism

E1 Easy Version 問題へのリンク

E2 Hard Version 問題へのリンク

問題概要

Yuzuはキャンディー個を持っています。人の敵がいて、敵は個キャンディーを持っています。Yuzuは長さの順列の順番に従って敵と闘います。

戦闘では、Yuzuが敵以上のキャンディーを持っているとき勝利し、キャンディーを個得ます。負けた場合ゲームオーバーです。

すべての戦闘に勝利できる順列はいくつあるでしょうか？という問題を考えることができますが、これでは面白くないです。

をキャンディーの初期値がのときのすべての先頭に勝利できる順列の総数と定義します。

以下の素数が与えられるので、がで割り切れないをすべて列挙してください。

制約

• E1

  • 
  • は素数
  • 

• E2

  • 
  • は素数
  • 

解説

E1

制約が小さいので、を考えます。すべてのの候補に対してかけてもよいことになります。数列を昇順ソートして、先頭から候補数を尺取り法で決めていくことができ、それをかけていけばが求まります。これが素数で割り切れるとき、前から決めた候補数にの倍数があることになります。

E2

まず、となる最小のを求めます。これはE1と二分探索を使えばでできます。

ここで、候補数にが出てくるかどうかは、単調性があります（解いたときは未証明だったが、実験していると割と自明だと思いました）。この単調性に気づけると、先ほど求めたになる最小の以上未満で二分探索をして、が出てくるかどうかをで確認すればよいです。

実験はでやってみました。

証明は公式editorialに書いてあったので確認の意味も込めて書いておこうと思います。

を個以下のキャンディーを持っている敵の数と定義し、 とおくと

• 
• 一度でもが以上の値をとると、は必ずで割り切れる。なぜなら、であり、は一つ進むごとに最大でずつしか下がらないので、どこかにが存在するからである。
• が成り立つ
• 以上より、がで割り切れるならば、もで割り切れる、つまり単調性があることが示された。

実装

• E1

int main() {

    ll N, p;
    cin >> N >> p;
    vector<ll> a(N);
    rep(i, N)cin >> a[i];
    sort(all(a));

    vector<ll> ans;
    for(ll xx = 1; xx <= a[N-1]; xx++){
        ll x = xx;
        bool ok = true;
        int l = 0;
        int r = 0;
        rep(l,N){
            while(r < N && a[r] <= x){
                r++;
            }
            if((r - l) <= 0)ok = false;
            if((r - l) % p == 0)ok = false;
            x++;
        }
        if(ok)ans.push_back(xx);
    }

    cout << ans.size() << endl;
    for(auto &val: ans){
        cout << val << " ";
    }
    cout << endl;
}

• E2

int main() {

    ll N, p;
    cin >> N >> p;
    map<ll,ll> mp;
    vector<ll> a(N);
    rep(i, N){
        cin >> a[i];
        mp[a[i]]++;
    }
    sort(all(a));
    ll ok = INFLL;
    ll ng = 0;
    auto check = [&](ll X){
        int r = 0;
        for(int l = 0; l < N; l++){
            while(r < N && a[r] <= X){
                r++;
            }
            if((r - l) <= 0)return false;
            X++;
        }
        return true;
    };
    while(abs(ng - ok) > 1){
        ll mid = (ok + ng) >> 1;
        if(check(mid))ok = mid;
        else ng = mid;
    }
    ll ok2 = ok-1;
    ll ng2 = INFLL;
    auto check2 = [&](ll X){
        int r = 0;
        rep(l,N){
            while(r < N && a[r] <= X){
                r++;
            }
            if((r - l) % p == 0)return false;
            X++;
        }
        return true;
    };
    while(ng2 - ok2 > 1){
        ll mid = (ng2 + ok2) >> 1;
        if(check2(mid))ok2 = mid;
        else ng2 = mid;
    }
    cout << ok2 - ok + 1 << endl;
    for(ll ans = ok; ans <=ok2; ans++){
        cout << ans << " ";
    }
    cout << endl;
}