yukicoder : No.322 Geometry Dash

これ系の問題SRMで何度か苦戦した記憶が。
http://yukicoder.me/problems/884

問題

N個の難所をクリアするゲームを考える。
難所はスタート地点から1列に順に並んでいる。

各難所iはパラメータT[i],D[i]を持つ。
難所に到達する際D[i]回目までは時間T[i]/2を経過したのちスタート地点に戻される。
D[i]+1回目以降は、時間T[i]を掛けて通過できる。

難所の並び順を任意にできるとき、全難所を通過するまでにかかる最短時間を求めよ。

解法

このように何かしらの基準でソートする問題は、隣接する2要素についてどちらを前に持ってくるのが良いか考えると良い。

隣接する2つの難所(T[x],D[x])と(T[y],D[y])についてどちらが前に来た方が総時間が下がるか考える。
先にx番がある場合、最初D[x]回x番に到達して戻される間にT[x]*D[x]/2のコストがかかる。
次にy番にD[y]回到達する際にT[y]*D[y]/2の時間がかかるが、その際毎回x番を経由するので、加えてD[y]*T[x]の時間がかかる。
なので、あとはy番を通過するだけの状態になるまで(T[x]*D[x]+T[y]*D[y])/2 + D[y]*T[x]かかる。

xとyの順番を逆にした場合、括弧内の値は変わらず、D[y]*T[x]の部分がD[x]*T[y]となる。
よってD[y]*T[x]＜D[x]*T[y]ならば、x番が前に来る並びの方が総時間が下がる。
そこでこの式を比較関数に用いてソートすればよい。

int N;
int T[101000],D[101000];
int A[101000];

int cmp(int x,int y) {
	return D[y]*T[x]>D[x]*T[y];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>T[i];
	FOR(i,N) cin>>D[i];
	FOR(i,N) A[i]=i;
	sort(A,A+N,cmp);
	FOR(i,N) _P("%d%c",A[i]+1,(i==N-1)?'\n':' ');
	
}

まとめ

今回はかなり単純だったけど、もうちょっと複雑になると比較関数が思い浮かばないんだよなぁ。