裏紙

ほぼ競プロ、たまに日記

CF 732 E - Sockets

問題

Problem - E - Codeforces

問題概要

n台のコンピュータがあり、それぞれi番目のコンピュータは電力p_iを必要とする。今、会場にはm個のコンセントがあり、j番目のコンセントは電力s_jを供給できる。そして、p_i = s_jを満たすときに限って、i番目のコンピュータとj番目のコンセントを接続することが出来る。

これだと電源につなげるコンピュータが少なすぎるので、アダプタという器具を使ってコンセントから供給される電力を調整することを考える。1つのコンセントにたいしてアダプタは直列に何個でもつなぐことが可能であり、今供給される電力がxであるコンセントにアダプタを1つ繋ぐと、供給される電力は \lceil \frac{x}{2} \rceilになる(例えば、最初が10なら、アダプタを繋ぐごとに10→5→3→2→1→1→...となっていく)。

さて、アダプタを使って同時にc台のコンピュータに電力を供給したい。このような方法が複数ある時にはアダプタの個数uが最小になるようにしたい。

cu、更にi番目のコンセントに繋ぐアダプタの個数a_ii番目のコンピュータをどのコンセントに繋ぐべきかを表す番号b_iを示せ。繋ぐ場所がないコンピュータは0を出力せよ。

  •  1 \le n,m \le 200000
  •  1 \le p_i , s_i \le 10^9

イデア

まず、コンピュータの方もコンセントの方も電力の昇順でソートしておく(出力のために、インデックスも保存しておく必要がある)。

さて、コンピュータを昇順に見ていく。それと同時に、そのコンピュータに適切なコンセントの番号sidxも保存しておく。今、sidx番のコンセントが既に使われている、もしくはそのソケットの電力がコンピュータよりも低い時にはsidxを増加させる。もしコンセントの電力が今注目しているコンピュータの電力にマッチするならそのコンセントとコンピュータの接続を決定する。そして、このループが1回終わるごとに、コンセントにアダプタを付ける(つまり、s_i = \lceil \frac{s_i}{2} \rceilと値を変更する)ことをする。これを全てのコンセントにこれ以上アダプタを付ける意味がなくなるまで繰り返せば、自然と求めたい条件に合致している組み合わせを選び出すことが出来る。

では「全てのコンセントにこれ以上アダプタを付ける意味がなくなる」状況はどんな状況なのかと考えてみると、最終的にはどんなコンセントも大量のアダプタを繋ぐと電力は1に収束していくのでそうなってしまった時になる。つまり、コンセントの中で最大の電力のものをAとすればO(logA)回繰り返せばよいということが分かる。1回のループにかかる計算量はO(n+m)であるから、全体でO((n+m)logA)となり、間に合う。

実装(C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

typedef pair<int,int> pi;

int main()
{
    int n,m;
    scanf(" %d %d", &n, &m);

    vector<pi> p(n), s(m);
    rep(i,n)
    {
        scanf(" %d", &p[i].fi);
        p[i].se=i;
    }
    rep(i,m)
    {
        scanf(" %d", &s[i].fi);
        s[i].se=i;
    }

    sort(all(p));
    sort(all(s));

    // a:i番目のコンセントにいくつアダプタを繋ぐか
    // b:i番目のコンピュータは何番のコンピュータに繋ぐか
    vector<int> a(m),b(n,-1);
    vector<bool> used(m,false);

    rep(adapter,31)
    {
        int sidx=0;
        rep(i,n)
        {
            int b_idx=p[i].se;
            if(b[b_idx]!=-1) continue;

            while(sidx<m && (s[sidx].fi<p[i].fi || used[sidx])) ++sidx;

            if(sidx<m && !used[sidx] && s[sidx].fi==p[i].fi)
            {
                used[sidx]=true;
                int a_idx=s[sidx].se;

                a[a_idx]=adapter;
                b[b_idx]=a_idx;
            }
        }

        rep(i,m) s[i].fi=(s[i].fi+1)/2;
    }

    int c=0,u=0;
    rep(i,m) u+=a[i];
    rep(i,n) if(b[i]!=-1) ++c;

    printf("%d %d\n", c,u);
    rep(i,m)
    {
        if(i) printf(" ");
        printf("%d", a[i]);
    }
    printf("\n");
    rep(i,n)
    {
        if(i) printf(" ");
        printf("%d", b[i]+1);
    }
    printf("\n");
    return 0;
}