解法
E:(最小化すべき関数)=(summation from i = 1 to n){i * (n + 1 - i) * a[i] * b[i]}
— こるとん (@kyort0n) 2019年5月14日
なので、i*(n+1-i)*a[i]が大きいものから順に小さいb[i]をぶつける
E A[i]は(i+1)*(n-i)回ずつ使われるので、A[i]にかけておく。そのソートと、Bの大きい順ソートを掛けたものが答え。
— titia (@titia_til) 2019年5月14日
Fは、何日までお店を使うか考えると、各タイプについて最後に開いた日を使えば最善なので、二分探索＋シミュレーションかと思ったんだけど、シミュレーション部分が書けず終了。
感想
- 具体的に書いてみると、a1 x b1 などそれぞれの出現回数が分かる
- 「Aは固定」とされているが、出現回数をかけてしまえばソートしてBとぶつければいいのがポイント
積の和を最小にする
- 今回のように
- A = [a1, a2, a3]
- B = [b1, b2, b3]
- A, Bの各要素をうまくマッチングさせて、積の和 (a? x b? + a? x b? + a? x b?)を最小にするには
- Aを昇順ソート
- Bを降順ソート
- してかければいいというのは、基礎なのだろう
