kmjp's blog

競技プログラミング参加記です

AtCoder ARC #101 : F - Robots and Exits

ARC

このテクも覚えておこう。
https://beta.atcoder.jp/contests/arc101/tasks/arc101_d

問題

1次元の数直線上の異なる座標に、N体のロボットとM個の出口がある。
i番目のロボットの座標をX[i]、j番目のロボットの座標をY[j]とする。

全ロボットを一斉に+1の座標に動かす、または一斉に-1の座標に動かすという作業を繰り返すことを考える。
途中出口のある座標に到達したロボットは、その時点で取り除く。

ロボットの動かし順を任意に設定するとき、各ロボットの到達する出口の組み合わせは何通りか。

解法

最も座標の小さい出口より小さい座標にいるロボットや、逆に最も座標の小さい出口より小さい座標にいるロボットは、到達する出口は1通りなので無視してよい。
それ以外のロボットについて、X[i]より小さな座標の出口のうち最大の物をY[j]とする。
すると、ロボットは小さい方に(X[i]-Y[j])回余分に移動するか、大きい方に(Y[j+1]-X[i])だけ余分に移動した段階でY[j],Y[j+1]いずれかの出口に到達する。

そこで、L[i]=X[i]-Y[j]、R[i]=Y[j+1]-X[i]として、点(L[i],R[i])を２次元座標上にプロットしよう。するとL[i],R[i]＞0となる。
ロボットの移動のさせ方について、左右の移動量の最大値をそれぞれx,yとおくと、(x,y)はそれぞれ原点からx,yが増加する方向に1ずつ動かすことに相当する。
ロボットiのプロット位置(L[i],R[i])について、前述の(x,y)が、x,yの増加に伴いx=L[i]とy=R[j]どちらに先に到達するかが、ロボットが左右どちらの最寄りの出口に到達するかに相当することになる。

よって、あとは(L[i],R[i])を多数２次元座標上にプロットする場合、前述の(x,y)の移動においてX座標とY座標どちらが先にL[i]ないしR[i]に到達するかを数え上げる問題となる。

f(x,y)を以下のように定義する。

  • x=L[i],y=R[i]となるロボットがいない場合0
  • x=L[i],y=R[i]となるロボットがいる場合、先にX座標がxに到達するように移動したのち(x,y)に移動する移動方法の組み合わせ

後者について、f(x,y)は0≦x'＜x、0≦y'＜yに対し、f(x',y')の総和となる(各(x',y')を通過後、y'がyに到達するまで先に移動したのちx'を増加したと考えよう)
これはy座標を先に座標圧縮しておくと、xを昇順にf(x,y)求めていくことで、単一のBITでf(*,y)を更新する作業と置くことができ、O(NlogN)で解くことができる。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<ll,20> bt;

int N,M;
int X[101010],Y[101010];
vector<pair<int,int>> V;
vector<int> Ys;
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>X[i];
	FOR(i,M) cin>>Y[i];
	Ys.push_back(0);
	FOR(i,N) {
		if(X[i]<Y[0]) continue;
		if(X[i]>Y[M-1]) continue;
		x=lower_bound(Y,Y+M,X[i])-Y;
		V.push_back({X[i]-Y[x-1],-(Y[x]-X[i])});
		Ys.push_back(Y[x]-X[i]);
	}
	sort(ALL(V));
	V.erase(unique(ALL(V)),V.end());
	sort(ALL(Ys));
	Ys.erase(unique(ALL(Ys)),Ys.end());
	bt.add(0,1);
	FORR(v,V) {
		y=lower_bound(ALL(Ys),-v.second)-Ys.begin();
		bt.add(y,bt(y-1)%mo);
	}
	
	cout<<bt(Ys.size()+2)%mo<<endl;
}

まとめ

コードは短いが考察は結構しんどい。