Joeの精進記録

旧:競プロ練習記録

G - Sword profit

University Codesprint 5で唯一解けなかった問題。ツイッターを見る限りFよりもずいぶん簡単という評価だったのでコンテスト中に解けるようになりたい www.hackerrank.com

 i番目の店で n本の剣を買う費用は a_i n + \frac{1}{2}b_i n(n + 1)円で、それを j番目の店ですべて売ると、 (q_i - (j - i)d - r_j) n円の利益がでます。同じ種類の剣は複数の店で分割して売る必要がないことはちょっと考察すればわかると思います。

それぞれの iに関して n \ge 0 j > iを変化させて利益を最大化するという問題です。

利益を最大化するには

  1. 1本あたりの売上を最大化し
  2. それを利益が最大になる本数分買う

という戦略をとればいいです。1は jd_i + r_jが最小となる j > iを見つければよく、これにはConvexHullTrickというアルゴリズムを使います。 これは \min_{1 \le i \le n} a_ix + b_iを最小化する i O(\log n)で求めるアルゴリズムです。詳細は以下のブログで解説されています。

satanic0258.hatenablog.com

ここまでわかっても実装上のひっかけが多く、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の日記を参考にしました。