DOJ Beginner Contest 13 C - Measures
- サイト
- DOJ
- コンテスト
- DOJ Beginner Contest 13
- 問題
- C - Measures
ある標準錘の重さを 個の都市で量った記録があります。 番目の都市の ポンドは グレインで、その都市は標準錘を ポンド( ポンド未満は切り捨て)と記録しました。標準錘の実際の重さは、グレインで表すと正の整数です。残った記録がすべて正しくありうるように、除く記録の最小個数を求める問題です(、、)。
標準錘の重さを グレインとすると、記録 が正しいのは 、つまり
のときです。さらに なので、記録 が正しくなる は半開区間 です。 のときはこの区間は空で、その記録は必ず除くことになります。
を固定すると、残せる記録は を含む区間の個数です。よって、 個の区間が最も多く重なっている点での重なりの数を とすると、答えは です。
区間の端点は 程度まで大きくなるので、端点を座標圧縮してからいもす法で各点の重なりの数を求めます。重なりの数が変わるのは区間の左端だけなので、左端と右端の座標だけ見れば十分です。計算量は です。
の条件を区間の左端に入れておくのが大事です。左端を のままにして、座標 での重なりの数を最大値の候補から除くだけだと、 の記録の区間 が数えられなくなります。例えば 、 では、 なら記録が正しいので答えは ですが、座標 を除くと になってしまいます。
Python
import bisect
N = int(input())lr = []comp = []for i in range(N): u, a = map(int, input().split()) l = max(u * a, 1) lr.append((l, u * (a + 1))) comp.append(l) comp.append(u * (a + 1))comp = sorted(set(comp))imos = [0] * len(comp)for l, r in lr: imos[bisect.bisect_left(comp, l)] += 1 imos[bisect.bisect_left(comp, r)] -= 1for i in range(1, len(imos)): imos[i] += imos[i - 1]print(N - max(imos))comp が座標圧縮した端点の座標で、imos[i] は累積和をとったあと、点 comp[i] を含む区間の個数になります。空の区間は、同じ位置に と が入るので打ち消し合います。