DOJ Beginner Contest 11 F - Laboratory
- サイト
- DOJ
- コンテスト
- DOJ Beginner Contest 11
- 問題
- F - Laboratory
種類の微生物があり、 番の微生物の 日目の個体数は です。 を成長係数とよびます。
日目に、何種類かの微生物を選びます。ただし、選んだ微生物を次の 2 通りで並べたとき、番号の並びが一致しなければなりません。
- 成長係数の小さい順
- 日目の個体数の少ない順
どちらも、値が同じなら番号の小さい順に並べます。 種類以上選べる最も早い日 を求める問題です。存在しなければ -1 を出力します。
、 です。
固定した日に選べる最大の種類数
Section titled “固定した日に選べる最大の種類数”微生物を の昇順に並べておきます。選んだ微生物の並びがこの順で、 も昇順になっていれば条件を満たします。
つまり、 の順に並べた列で、 の最長狭義増加部分列(LIS)の長さが、 日目に選べる最大の種類数です。LIS の長さは で求まります。
日数についての単調性
Section titled “日数についての単調性”日目に選べる組は、 日目にも選べます。
の 2 つが 日目に条件を満たしているとします。1 日たつと、個体数の差 は だけ増えます。 なら差が増えるので順序は保たれ、 なら差が変わらないので順序も変わりません。
よって、選べる最大の種類数は について広義単調増加です。 種類以上選べる最小の を二分探索で求めます。
問題文にあるとおり、答えが存在すれば 以下です。 で 種類選べなければ -1 を出力し、選べれば で二分探索します。
全体で です。
Python
from operator import itemgetterfrom 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 は安定なので、 だけをキーにしても、 が等しいものは番号順に並びます。q(x) は の LIS の長さを返します。dp[k] は長さ の増加部分列の末尾の最小値で、番兵の値が残っていない個数が LIS の長さです。