大会のルールは以下の通りです。1個の食べ物につき1人のチームメンバーを割り当てる。同じメンバーを複数の食べ物に割り当てることはできない。N人のメンバーそれぞれが完食にかかる時間のうち最大値が、チーム全体の成績となる。コンテストの前に、高橋君のチームは修行をすることにしました。各メンバーは、自分の消化コストが0より小さくならない限り、1回修行するごとに自分の消化コストを1減らすことができます。修行には膨大な食費がかかるため、N人合計でK回までしか修行することができません。各メンバーの修行回数と担当する食べ物を適切に選んだとき、チーム全体の成績は最小でいくらになるでしょうか。入力はすべて整数1≤N≤2×10^50≤K≤10^181≤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]”となります。0についての最適解を導くここで、Kの制約に着目すると愚直に求めること(つまりkをインクリメントしてシュミレーションで求めること)が不可能だと分かります。おまけ:(何を勘違いしたかシュミレーション解をコンテスト中に提出してしまった。)そこで、「すべてのMemberに対して、完食にかかる時間をX(これが答え)以下にできるか」という問題について考えます。ここで「(1)すべての値をx以下にするために何回操作(修行)が必要なのかを求め、(2)可能かどうかを求める関数」を作成します。出てくる値のすべてをX以下にしたい。6回の修行が必要だと計算できます。この計算方法を用いることで、「(1)すべての数をX以下としたときに、何回の操作(修行)が必要なのか」を求められます。状況を整理するため、この関係を数式に起こすとこうなります。ここでは、必要とされる手数をneedと置いています。“X以下としたい”のXをtargetとして置いています。式変形をするだけ、それが難しい。この式を用いて必要な手数の合計、「ex」を導き出します。k」を満たすかどうかで判断できます。これらより、「(1)すべての値をx以下にするために何回操作(修行)が必要なのかを求め、(2)可能かどうかを求める関数」はこうなります。“X(target)の決定”です。これは二分探索を用いることで解決できます。X(target)を二分探索することで、計算量を抑えながら答えを導くことができます。2016まとめ今回の問題の流れをまとめるとこんな感じです。/その他趣味いっぱい。便利ツールを制作したりしています。