問題B『DDPC特別ビュッフェⅡ』 : DDPC(DISCO presents ディスカバリーチャンネルプログラミングコンテスト)2016 本選

冷静に考えればそこまで難しくはないのですが、
朝だと頭が働かず、本番中には解けませんでした。

概要

$N$ 種類の料理があり、i番目の料理は時刻 $T_i$ までしか食べられない。
また、それぞれの料理にはスコア $A_i$ が決まっており、一度食べたらなくなる。
それぞれの時刻( $t\geq 1$ )では $t\leq T_i$ の料理をひとつ選んで食べることができる。

うまく食べる料理を選ぶとき、スコアの合計を $X$ 以上にするのに必要な時間の最小値を出力せよ。
どうやっても $X$ 以上のスコアにできなければ、 $-1$ を出力せよ。

制約

$1\leq N\leq 10^5$
$1\leq T_i\leq 10^5$
$1\leq A_i\leq 10^5$
$1\leq X\leq 10^9$

解説

美味しい料理から食べていけばよさそうだが、制限時間の緩い( $T_i$ の大きい)料理は後回しにしたい。
どれくらい後回しにできるか、とか考えるといろいろと面倒(←何回もバグりました)。

しかし後ろから考えると、すっきり解けることが分かる。
つまり、時刻 $z$ までに食べ終えるかを判定して、 $1\leq z<\max_i T_i+1$ の範囲で $z$ について二分探索すればOK。

まず、料理を $T_i$ でバケットソートしておく。
時刻 $t$ ( $t=1,2,\ldots,z-1$ )において食べるべき料理は、
$T_i\geq t$ を満たす料理のうち $A_i$ が最も大きいもの。
よって、優先度付きキューを用意して、各時刻で、 $T_i=t$ の料理をpushし、スコアの和にpopして足せば、
時刻 $z$ までに食べ終えるときのスコアの最大値が分かる。

一回の判定で $O(N)$ 回push、popするので $O(N\log N)$ 。
二分探索もあわせて、全体では計算量は $O(N(\log N)^2)$ 。

ソースコード

using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
	static int F() { return int.Parse(Console.ReadLine()); }
	static int[] G() { return Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); }
	static void Main()
	{
		var I = G();
		var N = I[0]; var X = I[1];
		var T = G();
		var A = G();
		var MT = T.Max();
		var a = new List<int>[MT + 1];
		for (var i = 0; i <= MT; i++) a[i] = new List<int>();
		for (var i = 0; i < N; i++) a[T[i]].Add(A[i]);
		// a[i] = 時刻iに食べられる料理たち
		var ans = FirstBinary(1, MT + 1, z =>
		{
			var s = 0L;
			var foods = new PriorityQueue<int>((x, y) => y.CompareTo(x));
			Action<IEnumerable<int>> union = set => { foreach (var item in set) foods.Enqueue(item); };
			for (var t = z + 1; t <= MT; t++) union(a[t]);
			for (var t = z; t >= 1; t--)
			{
				union(a[t]);
				if (foods.Count > 0) s += foods.Dequeue();
			}
			return s >= X;
		});
		Console.WriteLine(ans <= MT ? ans : -1);
	}
	static int FirstBinary(int min, int max, Predicate<int> pred)
	{
		while (min < max)
		{
			var mid = (min + max) >> 1;
			if (pred(mid)) max = mid;
			else min = mid + 1;
		}
		return min;
	}
}