2020年6月22日 日記

2020年 6月 22日

まえがき

健康管理

何した

具体的に

今日解いた問題

ABC123 D-Cake 123

• [大きい方から何番目,優先度付きキュー]
  

結構頑張った。難しい。
まず、x,y,zがそれぞれ10³を最大取るので、x * y * z通りの美味しさを全て列挙するのは無理無理無理無理カタツムリ(10⁹列挙したら時間が無理で死ぬ)

なんか、ABC155 D- Pairsの解法で二分探索を使った解説をしていたと思うんですが、その時の臭いを感じたので二分探索かな〜？とも思ったんだけど、浮かばなかった。

で、なんとなく半分全列挙みたいな言葉が浮かんで、それは関係ないんだけど、とりあえず,Aから1個、Bから1個ずつとるx * y通りの組み合わせなら10⁶個の組み合わせ（が最大）なので全部並べてソートも出来るな。ってことが分かった

で、当然ながら、美味しさが一番大きいものは、 Aから最大、Bから最大、Cから最大。

ここまでかんがえてもまだまだ。

AとBから1個ずつ取ったx * y 通りの美味しさの組み合わせの配列（？？）(AB配列って言っとく)を昇順にソートしてやると、各Ciを使ったときに美味しさが一番大きい条件って,Ci+ABの一番大きいやつ。

これを z　個優先度付きキューにブチこんでやって、ってやれば解けた。（すごい)

int main()
{
    ll x, y, z, k; 
    cin >> x >> y >> z >> k;
    vector<ll> a(x), b(y), c(z);
    rep(i,x) cin >> a[i];
    rep(i,y) cin >> b[i];
    rep(i,z) cin >> c[i];
 
    // aとbの組なら全列挙出来る
    vector<ll> ab(0);
    rep(i,x){
        rep(j,y){
            ab.push_back(a[i]+b[j]);
        }
    }
    sort(ab.begin(),ab.end());
    int n = ab.size();
 
    // abにaとbの和が昇順に入っているがそこからどうしたらいいんだ
    // 各Ciにおける最大値を優先度付きキューにぶちこむ
    priority_queue<pair<ll,int>> pque;
    rep(i,z){
        pque.push({ab[n-1]+c[i], n-1});
    }
 
    while(k--){
        auto X = pque.top();
        pque.pop();
        ll sum, ind_ab;
        sum = X.first;
        ind_ab = X.second;
        cout << sum << endl;
        sum -= ab[ind_ab];
        if(ind_ab!=0){
            ind_ab--;
            sum += ab[ind_ab];
            pque.push({sum, ind_ab});
        }
    }
}

ちょっとだけお絵描きしようかな。

とりあえず、C0,C1,C2,...,Cz-1に対して一番大きいのはAB[n-1]にCi( 0 <= i <= z-1)を足したものだな〜なイメージから行ける（俺は天才だからソレで行ける)

あとがき

以下は毎回記事に貼っているテンプレート

基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます - 瑞々しぃにぼしの自己紹介(自己紹介の記事です)