AtCoder Beginner Contest 144 E - GluttonyのEditorialを読んで

問題はこちらから。

最適な方法は直感的にわかるのだが、その後二分探索で解を探すというところまで頭が回らなかった。二分探索に気付けるかどうか。

そして自分は直感的というか自明としてしまったが、Editorialに今回の食事の割当について自明な割当がなぜ最適な割当になっているのか説明してあったのでそれを引用する。

ある 2 人 X, Y の，修行前の消化コスト $A_x$ , $A_y$ および担当する食べ物の食べにくさ $F_x$ , $F_y$ において， $A_x$ < $A_y$ かつ $F_x$ < $F_y$ が成り立つとします．このとき，修行後のコストを $A'_x$ , $A'_y$ とおくと

$A'_x$ < $A'_y$ のとき，両名の担当する食べ物のみを入れ替えることで、

$A'_x \geq A'_y$ のとき，両名の担当する食べ物と修行後のコストを入れ替えることで、

修行の総数も成績も，何も損することなく両名の担当を $swap$ できます．これを繰り返すと有限回で行き詰まり，その結果できた選び方は先述の条件を満たします．

提出したコードは以下。

// Editorial
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;

int main() {
  int n;
  cin >> n;
  long long k;
  cin >> k;
  vector<int> a(n);
  vector<int> f(n);
  for(int i=0;i<n;i++) cin >> a[i];
  for(int i=0;i<n;i++) cin >> f[i];
  sort(a.begin(), a.end());
  sort(f.rbegin(), f.rend());
  long long start = 0;
  long long end = pow(10, 12);
  while(start != end) {
    long long h = (start + end) / 2;
    long long tmp = 0;
    for(int i=0;i<n;i++) {
      long long t = h / f[i];
      tmp += max(0LL, a[i] - t);
    }
    if(tmp <= k) end = h;
    else start = h + 1;
  }
  cout << start << endl;
}

horoyoisawaのゴミ箱

いろいろ書きます

AtCoder Beginner Contest 144 E - GluttonyのEditorialを読んで