【C#】ABC-144 – E – Gluttony

2019/10/28 23:41 図が間違っていたのを修正


ABC爆死したので解説記事書きます。悔しい…悔しい…

問題文引用


高橋君は早食い大会に出ることにしました。

この大会は N 人でのチーム戦であり、高橋君のチームは年齢順に 1から N までの番号がついた N 人のメンバーからなります。メンバー i の 消化コスト は Ai です。

大会では 1 から N までの番号がついた N 個の食べ物が用意されており、食べ物 i の 食べにくさ は Fi です。大会のルールは以下の通りです。

  • 1個の食べ物につき1人のチームメンバーを割り当てる。同じメンバーを複数の食べ物に割り当てることはできない。
  • あるメンバーについて、そのメンバーの消化コストが x、担当する食べ物の食べにくさがyのとき、その食べ物の完食には x*y 秒かかる。
  • N人のメンバーそれぞれが完食にかかる時間のうち最大値が、チーム全体の成績となる。

コンテストの前に、高橋君のチームは修行をすることにしました。

各メンバーは、自分の消化コストが0より小さくならない限り、1回修行するごとに自分の消化コストを1減らすことができます。ただし、修行には膨大な食費がかかるため、N人合計でK回までしか修行することができません。

各メンバーの修行回数と担当する食べ物を適切に選んだとき、チーム全体の成績は最小でいくらになるでしょうか。


制約

入力はすべて整数
1≤N≤2×10^5
0≤K≤10^18
1≤Ai≤10^6(1≤i≤N)
1≤Fi≤10^6(1≤i≤N)

引用元:https://atcoder.jp/contests/abc144/tasks/abc144_e

解説


メンバーの消化コストを格納した配列をMember,食べ物の食べにくさを格納した配列をFoodsとします。

まずは「K=0についての最適解を考える」事から始めます。

K=0についての最適解を考える


K=0のとき、最適解は”昇順ソートしたMember[i]*降順ソートしたFoods[i]”となります。

Member(昇順)*Foods(降順)が最適となる

K > 0についての最適解を導く


ここで、Kの制約に着目すると愚直に求めること(つまりkをインクリメントしてシュミレーションで求めること)が不可能だと分かります。

おまけ:(何を勘違いしたかシュミレーション解をコンテスト中に提出してしまった。もちろんTLE。)

そこで、「すべてのMemberに対して、完食にかかる時間をX(これが答え)以下にできるか」という問題について考えます。

ここで「(1)すべての値をx以下にするために何回操作(修行)が必要なのかを求め(2)可能かどうかを求める関数」を作成します。

 
Member[i] * Foods[i] で出てくる値のすべてをX以下にしたい。

X = 4とした時の計算。6回の修行が必要だと計算できます。

この計算方法を用いることで、「(1)すべての数をX以下としたときに、何回の操作(修行)が必要なのか」を求められます。

状況を整理するため、この関係を数式に起こすとこうなります。ここでは、必要とされる手数をneedと置いています。また、“X以下としたい”のXをtargetとして置いています。

式変形をするだけ、それが難しい。

この式を用いて必要な手数の合計、「ex」を導き出します。(二つ上の画像の “7cost!” ってやつ)

そして、(2)可能かどうかを求めるのですが、これは「ex <= k」を満たすかどうかで判断できます。

これらより、「(1)すべての値をx以下にするために何回操作(修行)が必要なのかを求め(2)可能かどうかを求める関数」はこうなります。

※exに間違って負の数を加算しないよう気をつけましょう

二分探索を用いる


残り必要な作業は “X(target)の決定”です。

これは二分探索を用いることで解決できます。

X(target)を二分探索することで、計算量を抑えながら答えを導くことができます。

二分探索Tips:

– left は常に条件を満たさない

– right は常に条件を満たす

– right – left = 1 になるまで範囲を狭める (最後は right が条件を満たす最小)

まとめ


今回の問題の流れをまとめるとこんな感じです。

  1. 入力を受け取る
  2. Memberを昇順ソート、Foodsを降順ソート
  3. 操作可能かどうかを求める関数を作る
  4. 二分探索でX(target)を設定しながら関数を使う
  5. 条件に合うX(target)を出力する

ACコード


提出

Submission #8181961 - AtCoder Beginner Contest 144 AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
 atcoder.jp
Atria
  • Atria
  • 大学生個人開発者| AtCoder(茶) / C# / VBA /その他趣味いっぱい