백준 15261 Donut Drone (CERC 2017 D)

문제 설명(링크):

https://www.acmicpc.net/problem/15261

15261번: Donut Drone

문제 요약

도넛처럼 생긴 격자판에서 각각의 높이가 있는데, 한 칸에서 시작할 때 다음으로 갈 칸은 왼쪽 위, 왼쪽, 왼쪽 아래 중 높이가 가장 높은 곳이다.(세 값은 항상 다르다) 두 가지 쿼리를 처리해야 하는데, 하나는 어떤 칸의 높이가 변화하는 것이고, 하나는 특정 위치에서 $K$번 이동시키는 것이다.

 

풀이

일단 1열 i행에서 시작해 한바퀴를 돌아 다시 1열로 온 상황을 생각해 보자. 그러면, 다시 돌아왔을때의 행 번호을 $p_i$라 하자. 만약 $p_i$를 알고, update가 없다면 문제를 풀 수 있다. 일단 1열까지 이동하는 것은 일일히 시뮬레이션하고, $K$가 $C$보다 작으면 시뮬레이션한다. $K$가 $C$보다 크다면, 1열 $i$행에서 $C$번 이동하면 1열 $p_i$행으로 온다는 사실을 이용해 빠르게 시뮬레이션할 수 있다. $p$에서 발생하는 사이클($p_{a_1}=a_2, p_{a_2}=a_3, \cdots , p_{a_k}=a_1$과 같은 반복)을 찾을 때까지 반복하면 된다. 이때 시간복잡도는 $O(R+C)$이다.(사이클 크기가 최대 $R$, 시뮬레이션은 최대 $2C$번 해야 함)

 

이제 p를 update해야 한다. 하나의 관찰이 필요하다. 우선, x행 1열에서 시작해서 다시 1열로 돌아오는 과정에서 지나가는 칸들에 $x$를 기록해 두자. 이 과정을 모든 x에 대해 반복하면 각 칸에 적힌 숫자는 하나의 구간(원호에서의 구간으로, $l>r$일때 $[l, r]=\{ l, l+1,\cdots, R, 1, 2, \cdots r \}$을 이룬다는 것을 알 수 있다. 또한, 한 칸의 값이 바뀌면 그 칸 아래로 두개, 위로 두개의 칸에 적힌 구간이 변한다는 것을 관찰할 수 있다. 그러면 그 5개의 칸에 대해 그 칸에서 출발해서 갈 수 있는 칸들도 전부 바뀐다. 따라서 그 5개의 칸에 대해서 그 칸에서 시작해서 1열로 도달할 때까지 거쳐가는 칸들을 갱신해 주면, 많아야 $5M$개의 칸들의 구간만을 새로 갱신해야 한다. 따라서 매 업데이트마다 이를 실행해주고, 구간들을 통해 $p_i$도 새로 만들 수 있다.

 

소스코드

#include <bits/stdc++.h>
#include <cassert>

using namespace std;
typedef long long ll;

#define MAX 2050
#define ln '\n'
#define bb ' '

ll N, M;

ll X, Y;

struct range {
	ll l;
	ll r;
	range() :l(0), r(0) {}
	range(ll l, ll r) :l(l), r(r) {}
};

range operator+(const range r1, const range r2) {
	if (r1.l == 0) return r2;
	if (r2.l == 0) return r1;
	range ret;
	if (r1.r + 1 == r2.l || (r1.r == N || r2.l == 1)) ret = range(r1.l, r2.r);
	else ret = range(r2.l, r1.r);
	if (ret.r + 1 == ret.l) ret.l = 1, ret.r = N;
	return ret;
}

range r[MAX][MAX];
ll mp[MAX][MAX];
ll dir[MAX][MAX]; //-1, 0, 1
ll p[MAX]; //permutation

ll f(ll x, ll y) {
	return (x - 1) * M + y - 1;
}

ll pv(ll x) {
	x--;
	if (!x) x += M;
	return x;
}

void set_dir(ll x, ll y) {
	ll a, b, c;
	a = mp[(x - 1) > 0 ? (x - 1) : N][y % M + 1];
	b = mp[x][y % M + 1];
	c = mp[x % N + 1][y % M + 1];
	if (max({ a, b, c }) == a) dir[x][y] = -1;
	if (max({ a, b, c }) == b) dir[x][y] = 0;
	if (max({ a, b, c }) == c) dir[x][y] = 1;
}

void recalc(ll x, ll y) {
	ll pp = pv(y);
	r[x][y] = range();
	if (dir[(x - 1) > 0 ? (x - 1) : N][pp] == 1) r[x][y] = r[x][y] + r[(x - 1) > 0 ? (x - 1) : N][pp];
	if (dir[x][pp] == 0) r[x][y] = r[x][y] + r[x][pp];
	if (dir[x % N + 1][pp] == -1) r[x][y] = r[x][y] + r[x % N + 1][pp];
}

void prop(ll x, ll y) {
	if (y == M + 1) return;
	ll ne = x % N + dir[x][y];
	if (ne <= 0) ne += N;
	recalc(ne, y + 1);
	prop(ne, y + 1);
}


void update(int R, int C, int V) {
	ll i, j;
	mp[R][C] = V;
	ll pvc = C - 1;
	if (pvc < 1) pvc = M;
	ll pvpv;
	pvpv = R - 1;
	if (pvpv <= 0) pvpv = N;
	set_dir(pvpv, pvc);
	set_dir(R, pvc);
	set_dir(R % N + 1, pvc);

	ll ppp = R - 3;
	ll nc;
	nc = C;
	if (nc == 1) nc += M;
	if (ppp <= 0) ppp += N;

	for (i = 0; i < 7; i++) {
		recalc(ppp, nc);
		ppp = ppp % N + 1;
	}

	ppp = R - 3;
	if (ppp <= 0) ppp += N;

	for (i = 0; i < 7; i++) {
		prop(ppp, nc);
		ppp = ppp % N + 1;
	}

	for (i = 1; i <= N; i++) {
		if (!(r[i][M + 1].l)) continue;
		for (j = r[i][M + 1].l; j != r[i][M + 1].r; j = j % N + 1) {
			p[j] = i;
		}
		p[r[i][M + 1].r] = i;
	}
	return;
}

ll qcnt;

void simulate(int K) {
	qcnt++;
	while (Y != 1) {
		X = X % N + dir[X][Y];
		if (X <= 0) X += N;
		Y = Y % M + 1;
		K--;
		if (!K) break;
		if (Y == 1) break;
	}
	if (!K) {
		cout << X << bb << Y << ln;
		return;
	}
	vector<ll> chk(N + 1, 0);
	ll i = 1;
	chk[X] = 1;
	while (K > (M * N)) {
		K -= M;
		i++;
		X = p[X];
		if (K <= 2 * N * M) break;
		if (chk[X] && (K > (2 * N * M))) {
			ll d = i - chk[X];
			K %= (d * M);
			break;
		}
		else chk[X] = i;
	}
	//assert(qcnt <= 3000);
	while (K >= M) {
		X = p[X];
		K -= M;
	}
	for (i = 0; i < K; i++) {
		X = X % N + dir[X][Y];
		if (X <= 0) X += N;
		Y = Y % M + 1;
	}
	cout << X << bb << Y << ln;
}

signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	X = Y = 1;
	cin >> N >> M;
	ll i, j;
	for (i = 1; i <= N; i++) r[i][1] = range(i, i);
	for (i = 1; i <= N; i++) {
		for (j = 1; j <= M; j++) {
			cin >> mp[i][j];
		}
	}
	for (i = 1; i <= N; i++) {
		for (j = 1; j <= M; j++) {
			set_dir(i, j);
		}
	}
	for (i = 1; i <= N; i++) prop(i, 1);
	for (i = 1; i <= N; i++) {
		if (!(r[i][M + 1].l)) continue;
		for (j = r[i][M + 1].l; j != r[i][M + 1].r; j = j % N + 1) {
			p[j] = i;
		}
		p[r[i][M + 1].r] = i;
	}
	ll Q;
	cin >> Q;
	while (Q--) {
		string s;
		cin >> s;
		if (s[0] == 'm') {
			ll a;
			cin >> a;
			simulate(a);
		}
		else {
			ll a, b, c;
			cin >> a >> b >> c;
			update(a, b, c);
		}
	}
}

총평

좀 난이도 있는 문제였다. 또 어떤 대회에서 이 문제를 봤는데, 대회장에서 풀이를 얻은(M과 N를 바꿔써서 풀지는 못했다) 가장 어려운 문제이다. D4~D3 정도가 적절한 것 같다.