CPSCO2019 Session1: F - Fruits in Season

https://atcoder.jp/contests/cpsco2019-s1/tasks/cpsco2019_s1_f

問題概要

N個の果物があり、これを1日目からN日目まで毎日ひとつずつ食べていく。i番目の果物はj日目に食べるとAi-abs(j-ti)×Biの満足度が得られる。またある順番で果物を食べたとき、全体の満足度は各日に得られた満足度の最小値となる。自由に食べる順番を決められるとき、全体の満足度の最大値を求めよ。

N <= 2×104

解法

二分探索の見た目をしてるのでそうすると、二分探索の中身では「ある満足度xが与えられる。すべての果物の満足度がx以上になるように果物を各日に割り当てることは可能か?」という問題を解くことになる。そして満足度の式から各果物がx以上となるような日は連続した区間になっているので、この問題はさらに次のように言い換えられる。

  • 区間[l, r]がN個与えられる。それぞれの区間に対してl<=i<=rなる整数iをひとつだけ割り当てるとき、整数1~Nを重複なくすべての区間に割り当てることは可能か?

この問題は貪欲に解くことが可能で、割り当てる数を前から順番に見ていって、「その数を含む区間のうち右端が最小のもの」をその数に対して割り当てていけばよい。priority queueとかで実装すると楽。途中でできなくなったらNG。

感想

にぶたんの中身でだいぶ迷ってしまった 区間やりくり系の問題なんかいろいろバリエーションがある気がしてあまり整理できていない

あと本番では式の形を見た瞬間にアッCHTだわからない!!となって一瞬で布団に入って普通に寝てしまった(最悪)

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;
 
void main() {
    auto N = readln.chomp.to!int;
    auto A = N.iota.map!(_ => readln.split.map!(to!long).array).array;

    bool check(long x) {
        auto S = new Tuple!(long, long)[](N);
        foreach (i; 0..N) {
            long t = A[i][0];
            long a = A[i][1];
            long b = A[i][2];
            if (a < x) return false;
            long l = (-a + t*b + x) / b + ((-a + t*b + x) % b != 0);
            long r = (a + t*b - x) / b;
            S[i] = tuple(l, r);
        }
        S.sort!();
        auto pq = new BinaryHeap!(Array!(long), "a > b");
        int p = 0;
        foreach (i; 0..N) {
            while (p < N && S[p][0] <= i + 1) pq.insert(S[p][1]), p++;
            if (pq.empty || pq.front < i + 1) return false;
            pq.removeFront;
        }
        return true;
    }

    long hi = 10L^^18;
    long lo = -10L^^18;

    while (hi - lo > 1) {
        long mid = (hi + lo) / 2;
        (check(mid) ? lo : hi) = mid;
    }

    lo.writeln;
}