BOJ - Black Box

• https://www.acmicpc.net/problem/30853
• 난독화된 코드를 리버싱해서 요세푸스를 푸는 문제이다.

Idea

• 주어진 코드를 따라가면서 해독해보자. 마지막의 swap을 제외하면 알고리즘은 다음과 같다.

  • 배열 $A$가 주어진다. 포인터를 위치 0에 두고, 빈 리스트 $B$를 선언한다.
  • 다음 과정을 배열의 크기가 2 이상인 동안 반복한다.
    1. 포인터가 가르키는 값을 $v$라 할 때, 그 값을 배열에서 제거한다.
    2. 배열을 원형 배열로 생각하고, 포인터를 앞으로 $v$칸 옮긴다.
    3. $v$를 배열 $B$에 append한다.
  • $B$를 리턴한다.

• 요세푸스 문제와 상당히 유사하다는 것을 알 수 있다. 차이점이 있다면, $(N, K)$-요세푸스 문제에서는 앞으로 가는 칸이 $K$칸으로 고정되어 있지만, 이 문제에선 각 step마다 앞으로 몇 칸 갈 지가 동적으로 변화한다.

• 역추적은 간단하게 할 수 있는데, 값이 제거된 순서를 알기 때문에 세그이탐으로 각각의 위치를 특정해줄 수 있다.

Takeaway

• 원형 문제는 배열을 두 배 늘려놓고 처리하면 편하다.

• Walking on segtree

  • right_ge(x, k): $sum([x \dots i]) \ge k$인 최소 $i$를 리턴하는 함수
  • kth-element를 이용해서 구현할 수 있다.
    • right_ge(x, k) = kth(query(0, x-1) + k)

• kth-element는 아래처럼 쉽게 짤 수 있다.

int kth(int k, int idx=1){
	if(tree[idx]<k) return -1;
	if(idx>=sz) return idx-sz;	
	
	if(tree[idx<<1] >= k) return kth(k, idx<<1);
	else return kth(k-tree[idx<<1], idx<<1|1);
}

• 추가로, 일반적인 세그워크는 다음과 같이 짤 수 있다.

Node operator+() ...

// l부터 누적했을 때 f가 처음으로 false가 되는 최소 i 
template <class F>
int max_right(int l, F f){ 
	Node cur = ep();
	return go(l, f, cur);
}

// [s, e] 구간을 탐색한다.
template <class F>
int first_fail(int l, F& f, Node& cur, int idx=1, int s=0, int e=SZ-1){
	if(e < l) return -1; // [s, e] 구간이 의미없을 때
	
	if(l <= s){ // 완전히 포함되는 구간일 때
		Node nxt = cur + tree[idx];
		if(f(nxt)){ // 구간을 포함해도 true라면
			cur = nxt;
			return -1;
		}
		else if(s==e){ // 구간을 포함해도 false인데 크기 1짜리 구간이라면
			return s;
		}
	}
	
	// 완전히 포함되지 않으면 반으로 가름
	int mid = s+e>>1;
	int left = first_fail(l, f, cur, idx<<1, s, mid);
	if(left != -1) return left;
	return first_fail(l, f, cur, idx<<1|1, mid+1, e);
}

• 위 코드가 실제로 방문하는 구간은 오름차순으로 정렬되어 있기 때문에 이분 탐색이 가능하게 된다.
• 세그먼트 트리의 성질에 따라 시간복잡도가 $O(\log(N))$으로 바운드된다.