Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

JOI 春合宿 2012-day4 Chinese

問題文 : 中華料理

解法 :
 委員 a が 料理 b を食べるとき, 理事長の前にある料理はb - a となる. このような料理たちを通る最小手順を, すべてのありうる開始地点について考える問題である.
 これを考えるにあたって, 折り返しはたかだか1 回で良いことに注意すると, 右回り -> 左回り と 左回り -> 右回り で場合分けをして答えを求めればよいことがわかる.
 料理 0 についての最小値が分かれば, その他の料理xは0 の時の最小値からx を引いたものとなるので, 0 について具体的に求める.
 右回りのとき, i 回回すこと目の前には料理i がくる. 料理i がチェックすべき料理だとすると, i - 1回だけ回してしまうと左にN - 1 回回さなければi 番目の料理をチェックできない.
 同様に, 左回りの時, i 回まわすと, 目の前には料理(N - i) % N がくる. 同様の議論により, i - 1 回だけ回してしまうと, 右にN - 1 回まわさなければ(N - i) % N 番目の料理をチェックできない.

 これを利用してテーブルを作れば, 全体でO(N) でこの問題が解ける.

コード :

#include <cstdio>
#include <climits>
#include <algorithm>

#define MAX_N (100000)

using namespace std;

int main()
{
	int N;
	int req[MAX_N];
	bool check[MAX_N];
	
	scanf("%d", &N);
	
	fill(check, check + N, false);
	for (int i = 1; i < N; i++){
		scanf("%d", req + i);
		--req[i];
		check[(req[i] - i + N) % N] = true;
	}
	
	//right-rotation -> left-rotation
	int counter[MAX_N * 2];
	int idx;
	
	fill(counter, counter + N * 2, -1);
	for (int i = 0; i < N; i++){
		if (check[i] == true){
			idx = (i - 1 + N) % N;
			counter[(i - 1 + N) % N] = N - 1;
			counter[(i - 1 + N) % N + N] = N - 1;
		}
	}
	
	for (int i = 0; i < N; i++){
		counter[idx] = max(counter[idx], counter[(idx + 1) % N] - 1);
		counter[idx + N] = max(counter[idx + N], counter[(idx + 1) % N + N] - 1);
		idx = (idx - 1 + N) % N;
	}
	
	int res[MAX_N];
	int mini = INT_MAX;
	fill(res, res + N, INT_MAX);
	
	for (int i = 2 * N - 1; i >= 0; i--){
		//printf("%d -> %d\n", i, counter[i]);
		mini = min(mini, i + counter[i]);
		if (i < N) res[i] = min(res[i], mini - i + min(i, N - i));
	}
	
	//left-rotation -> right-rotation
	fill(counter, counter + N * 2, -1);
	for (int i = 0; i < N; i++){
		if (check[(N - i) % N] == true){
			idx = (i - 1 + N) % N;
			counter[(i - 1 + N) % N] = N - 1;
			counter[(i - 1 + N) % N + N] = N - 1;
		}
	}
	
	for (int i = 0; i < N; i++){
		counter[idx] = max(counter[idx], counter[(idx + 1) % N] - 1);
		counter[idx + N] = max(counter[idx + N], counter[(idx + 1) % N + N] - 1);
		idx = (idx - 1 + N) % N;
	}
	
	mini = INT_MAX;
	for (int i = 2 * N - 1; i >= 0; i--){
		//printf("%d -> %d\n", i, counter[i]);
		mini = min(mini, i + counter[i]);
		if (i < N) res[(N - i) % N] = min(res[(N - i) % N], mini - i + min(i, N - i));
	}
	
	for (int i = 0; i < N; i++) printf("%d\n", res[i]);
	
	return (0);
}