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); }