AtCoder ABC #457 (Polaris.AI プログラミングコンテスト 2026) : G - Catch All Apples

これはすんなり。
https://atcoder.jp/contests/abc457/tasks/abc457_g

問題

数直線上にリンゴがN個落ちてくる。
i番目のリンゴは時刻T[i]に座標X[i]に落ちてくるので、その時にロボットがその座標にいるとリンゴをキャッチできる。

各ロボットは初期状態で任意の場所に置くことができ、時速1で数直線上を移動できる。
全てのリンゴをキャッチするのに必要なロボットは最小で何台か。

解法

１台のロボットで最大何個のリンゴをキャッチできるか、という問題は既出である。
TopCoder SRM 623 Div1 Medium CatchTheBeat - kmjp's blog

この考え方を応答しよう。
リンゴを座標変換し、２次元座標上(T[i]-X[i],T[i]+X[i])でプロットする。
ロボットは、X座標やY座標を増加する方向にしか動けない場合、全部の座標を経由するのに必要なロボットの最小数を求めよう。

ロボットのいるY座標の一覧をmultisetで持ち、X座標順に走査しよう。
既存のロボットでリンゴをキャッチできるなら最寄りのロボットのY座標を動かし、キャッチできないならロボットを追加していけばよい。

int N;
int T[303030],X[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	vector<pair<int,int>> V;
	cin>>N;
	FOR(i,N) {
		cin>>T[i]>>X[i];
		V.push_back({T[i]+X[i],T[i]-X[i]});
	}
	sort(ALL(V));
	multiset<int> M;
	
	FORR2(a,b,V) {
		auto it=M.lower_bound(b+1);
		if(it!=M.begin()) M.erase(--it);
		M.insert(b);
	}
	cout<<M.size()<<endl;
	
}

まとめ

SRMの記憶が強すぎて、最初１台のロボットで最大何個リンゴをキャッチできるか数えてしまった。