コンテンツにスキップ

DOJ Beginner Contest 11 F - Laboratory

サイト
DOJ
コンテスト
DOJ Beginner Contest 11
問題
F - Laboratory

NN 種類の微生物があり、ii 番の微生物の xx 日目の個体数は Ai+BixA_i + B_i x です。BiB_i を成長係数とよびます。

xx 日目に、何種類かの微生物を選びます。ただし、選んだ微生物を次の 2 通りで並べたとき、番号の並びが一致しなければなりません。

  • 成長係数の小さい順
  • xx 日目の個体数の少ない順

どちらも、値が同じなら番号の小さい順に並べます。KK 種類以上選べる最も早い日 x≥0x \ge 0 を求める問題です。存在しなければ -1 を出力します。

1≤K≤N≤1051 \le K \le N \le 10^5、1≤Ai,Bi≤1091 \le A_i, B_i \le 10^9 です。

固定した日に選べる最大の種類数

Section titled “固定した日に選べる最大の種類数”

微生物を (Bi,i)(B_i, i) の昇順に並べておきます。選んだ微生物の並びがこの順で、(Ai+Bix,i)(A_i + B_i x, i) も昇順になっていれば条件を満たします。

つまり、(Bi,i)(B_i, i) の順に並べた列で、(Ai+Bix,i)(A_i + B_i x, i) の最長狭義増加部分列(LIS)の長さが、xx 日目に選べる最大の種類数です。LIS の長さは O(Nlog⁡N)O(N \log N) で求まります。

xx 日目に選べる組は、x+1x + 1 日目にも選べます。

(Bp,p)<(Bq,q)(B_p, p) < (B_q, q) の 2 つが xx 日目に条件を満たしているとします。1 日たつと、個体数の差 (Aq+Bqx)−(Ap+Bpx)(A_q + B_q x) - (A_p + B_p x) は Bq−Bp≥0B_q - B_p \ge 0 だけ増えます。Bp<BqB_p < B_q なら差が増えるので順序は保たれ、Bp=BqB_p = B_q なら差が変わらないので順序も変わりません。

よって、選べる最大の種類数は xx について広義単調増加です。KK 種類以上選べる最小の xx を二分探索で求めます。

問題文にあるとおり、答えが存在すれば 10910^9 以下です。x=109+1x = 10^9 + 1 で KK 種類選べなければ -1 を出力し、選べれば [0,109+1][0, 10^9 + 1] で二分探索します。

全体で O(Nlog⁡Nlog⁡max⁡)O(N \log N \log \max) です。

Python
from operator import itemgetter
from bisect import bisect_left
for _ in range(int(input())):
N, K = map(int, input().split())
ABi = [tuple(map(int, input().split())) + (i,) for i in range(N)]
ABi.sort(key=itemgetter(1))
def q(x):
dp = [(2 * 10**18, 10**18)] * (N + 1)
for a, b, i in ABi:
dp[bisect_left(dp, (a + b * x, i))] = (a + b * x, i)
for i in range(N + 1):
if dp[i][0] >= 2 * 10**18:
return i
assert False
ok = 10**9 + 1
ng = -1
if q(ok) < K:
print(-1)
continue
while ok > ng + 1:
mid = (ok + ng) // 2
if q(mid) >= K:
ok = mid
else:
ng = mid
print(ok)

sort は安定なので、BiB_i だけをキーにしても、BiB_i が等しいものは番号順に並びます。q(x) は (Ai+Bix,i)(A_i + B_i x, i) の LIS の長さを返します。dp[k] は長さ k+1k + 1 の増加部分列の末尾の最小値で、番兵の値が残っていない個数が LIS の長さです。