kmjp's blog

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

AtCoder AGC #007 : D - Shik and Game

何か月も前に解いた問題はだいぶ解法忘れるなぁ。
http://agc007.contest.atcoder.jp/tasks/agc007_d

問題


一直線上でゲームを行う。
初期状態でプレイヤーは位置0におり、最終的にゴール位置Eに移動したい。
プレイヤーは速度1以下で直線上を移動できる。

途中、N箇所の位置X[i]にクマiがいる。
一旦クマがいる座標に到達すると、クマはそのT秒後に同じ位置にコインを生成する。
生成されたコインは、同じ座標に到達することで瞬時に取得できる。
各クマの生成したコインを1枚ずつ獲得し、ゴール位置に到達するのにかかる最短時間を求めよ。

解法

尺取り法+RMQで解く。
1~i個目のクマのコインを取り切り、i個目のクマの位置にいる状態にする時間A(i)を順次求めよう。
まず一旦i番のクマの位置に到達し、その後クマのコインを取得するには、時間Tの猶予がある。
よって、手前距離がT/2以内の場所のクマは、その間にコインを回収に行ける。
逆にそうでないクマは、i番のクマに最初に到達するために先にコインを回収しておかなければならない。
後者のクマのうち番号の最大値をxとする。
その場合、A(i) = A(x) + (X(i)-X(x)) + Tである。
また、xより手前のコインを取得する前に、先にi番に到達しておいてもよい。
その場合、y番までコインを取得した状態でi番まで到達すると、A(i) = A(y) + (X[i]-X[y])+2*(X[i]-X[y+1])

よってまとめるとA(i) = min(A(x) + (X(i)-X(x)) + T, min_y(A(y) + (X[i]-X[y])+2*(X[i]-X[y+1]))
前者はA(x)-X[x+1]、後者はA(y)-(X[y]+2*X[y+1])の最小値を取るRMQをそれぞれ構築しておくと、高速にminがとれる。

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=1LL<<60;
	V comp(V l,V r){ return min(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};

SegTree_1<ll,1<<20> st1,st3;

int N,E,T;
ll X[202020];
ll R[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>E>>T;
	
	
	x=0;
	X[N+1]=E;
	for(i=1;i<=N;i++) cin>>X[i];
	
	st1.update(0,0);
	st3.update(0,-2*X[1]);
	for(i=1;i<=N;i++) {
		while(2*(X[i]-X[x+1])>T) x++;
		
		R[i]=min(3*X[i]+st3.getval(0,x), X[i]+T+st1.getval(x,i));
		st1.update(i,R[i]-X[i]);
		st3.update(i,R[i]-(X[i]+2*X[i+1]));
	}
	
	cout<<R[N]+E-X[N]<<endl;
}

まとめ

1200ptを本番通すのは珍しい。