University Codesprint 5で唯一解けなかった問題。ツイッターを見る限りFよりもずいぶん簡単という評価だったのでコンテスト中に解けるようになりたい www.hackerrank.com
番目の店で本の剣を買う費用は円で、それを番目の店ですべて売ると、円の利益がでます。同じ種類の剣は複数の店で分割して売る必要がないことはちょっと考察すればわかると思います。
それぞれのに関してとを変化させて利益を最大化するという問題です。
利益を最大化するには
- 1本あたりの売上を最大化し
- それを利益が最大になる本数分買う
という戦略をとればいいです。1はが最小となるを見つければよく、これにはConvexHullTrickというアルゴリズムを使います。 これはを最小化するをで求めるアルゴリズムです。詳細は以下のブログで解説されています。
ここまでわかっても実装上のひっかけが多く、doubleでやろうとすると精度的に足りなく、i64もオーバーフローするためi128を使う必要があります。また、二次関数の最大値を求めるのに、三分探索を使ってしまうと(使う人はほとんどいないと思いますが)TLEします。i128ですし100倍近くの定数倍がかかってそうですね、、
using i128 = __int128_t; i64 n, qs[303030], as[303030], bs[303030], rs[303030], ds[303030]; int main() { cin >> n; for (int i = 0; i < n; i++) { cin >> qs[i] >> as[i] >> bs[i] >> rs[i] >> ds[i]; } ConvexHullTrickDynamic cht; vi mins(n); // min_j{jx + rs[j]}, evaled at x for (i64 i = n - 1; i >= 0; i--) { cht.add(i, rs[i]); mins[i] = cht.get(ds[i]); } i64 ans = 0; for (i64 i = 0; i < n; i++) { i64 sales = max(0ll, qs[i] + i * ds[i] - mins[i]); auto prof = [&](i64 m) { return i128(sales) * m - (i128(as[i]) * m + i128(bs[i]) * m * (m + 1) / 2); }; ans += prof(max(0ll, (sales - as[i]) / bs[i])) % MOD; ans %= MOD; } cout << ans << endl; }
ライブラリとしてsatanic0258さんのコード、デバッグ時にUniversity CodeSprint 5 - ei1333の日記を参考にしました。