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以上となるような日は連続した区間になっているので、この問題はさらに次のように言い換えられる。
この問題は貪欲に解くことが可能で、割り当てる数を前から順番に見ていって、「その数を含む区間のうち右端が最小のもの」をその数に対して割り当てていけばよい。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; }