BOJ 28036 - Rotate and Shift

BOJ 28036 - Rotate and Shift

내 풀이

$[A_i, A_{i+1}-1]$ 에 속한 인덱스 $i$는 $L=A_{i+1}-A_i$라 할 때, $i-A_i$ 초부터 이동을 시작하고 한 번 이동할 때 $L$ 만큼 오른쪽으로 간다.

그리고 그 다음 이동은 $i-A_i+L$ 초이다.

이러한 성질을 이용해 풀 수 있다.

즉, $T$ 초 후의 위치는 $\left\lceil \dfrac{ T-(i-A_i) }{L} \right\rceil \cdot L ~ \% ~ N$이다.

void solve() {  
   int n, k, t;  
   cin >> n >> k >> t;  
   vi rot(k);  
   fv(rot);  
  
   rot.pb(n);  
   vi ans(n, -1);  
   for (int i = 0; i < k; i++) {  
      int l = rot[i], r = rot[i + 1] - 1;  
      int move = rot[i + 1] - rot[i];  
      for (int j = l; j <= r; j++) {  
         int T = t;  
         T -= j - l;  
         ans[md(n, j + ((T - 1) / move + 1) * move)] = j;  
  
      }  
   }  
   for (int i: ans) cout << i << ' ';  
}

다른 풀이

$1$초마다 $K$개가 오른쪽으로 쉬프트된다고 생각하지 말고, 모든 소들이 $-1$ 쉬프트 된다고 생각하자.

그럼 $[A_i, A_{i+1}-1]$ 의 소들은 계속 왼쪽으로 가며 젤 왼쪽의 소는 $A_i \to A_{i+1}-1$ 로 한 이동마다 변경된다.

따라서 $T$를 이 구간의 길이로 나머지연산하여 최종 소의 위치를 결정하고 $T$ 왼쪽으로 밀었으므로 정답엔 $T$번 오른쪽으로 밀어서 출력한다.

void solve() {  
   int n, k, t;  
   cin >> n >> k >> t;  
   vi rot(k);  
   fv(rot);  
  
   rot.pb(n);  
   vi ans(n, -1);  
   for (int i = 0; i < k; i++) {  
      int l = rot[i], r = rot[i + 1] - 1;  
      int L = r - l + 1;  
      for (int j = l; j <= r; j++) {  
         int nxt = j - t % L;  
         if (nxt < l) nxt += L;  
         ans[nxt] = j;  
      }  
   }  
   vi copy(n);  
   for(int i = 0 ; i < n ; i++) copy[md(n, i + t)] = ans[i];  
   for (int i: copy) cout << i << ' ';  
}