UCPC 2018 후기

<남남서와 찌끄레기들> 팀으로 참가해, 12문제 중 10문제를 풀고 전체 4등의 결과를 얻었다. 팀 연습을 안 해봤어서 걱정했는데 좋은 결과가 나와서 다행이었다.

대회 준비에 부족한 부분이 있긴 했지만 내가 준비해도 저런 문제가 안 생겼을 거라고는 장담 못 할 것 같다... 주최 분들이 정말 수고하신게 보였다.

내가 푼 문제는 E, K, I였다. 각각 내 풀이를 써본다.

E

배열을 one-based로 사용해 min-heap을 만든다. ($i$번째 노드의 부모가 $\lfloor i/2 \rfloor$가 되는 식으로)
이 때, $1$부터 $N$까지의 수를 어떤 특정 순서로 힙에 삽입해서,
모든 작업이 끝났을 때 $p$번째 위치에 $k$가 적혀 있도록 하는 방법을 아무거나 하나 출력하는 문제이다.

처음에는 방법의 수를 세는 것으로 잘못 읽고는 엄청 어려운 문제라고 생각하고 넘겼는데,
사람들이 많이 풀길래... 현수에게 설명해주면서 보니까 방법을 아무거나 하나 출력하는 문제였고, 그러면 어렵지 않아 보였다.
초반 스퍼트가 끝나가는 타이밍이기도 했고, 급한 마음에 두 번 실수를 거친 끝에 맞았다.

$p$번째 위치 밑($p$번째 위치의 subtree)에는 모두 $k$보다 큰 수가 있어야 하며,
$p$번째 위치 위($p$번째 위치의 조상들)에는 모두 $k$보다 작은 수가 있어야 한다.
양쪽 다 갯수가 맞으면(그만큼 채울 수 있다면) 그런 숫자들로 적당히 채우면 된다.

#include <bits/stdc++.h>
using namespace std;

int n, k, p;

int sz(int x){
	if(x > n) return 0;
	return 1+sz(x*2)+sz(x*2+1);
}

int ans[200010];
bool used[200010];

int large;

void dfs(int x){
	if(x*2 <= n){
		ans[x*2] = ++large;
		used[large] = 1;
		dfs(x*2);
	}
	if(x*2+1 <= n){
		ans[x*2+1] = ++large;
		used[large] = 1;
		dfs(x*2+1);
	}
}

int main()
{
	scanf("%d%d%d", &n, &k, &p);

	if(n-k < sz(p)-1){ puts("-1"); return 0; }

	vector<int> ancestor;
	for(int i=p/2; i; i/=2) ancestor.push_back(i);
	if(k-1 < int(ancestor.size())){ puts("-1"); return 0; }

	reverse(ancestor.begin(), ancestor.end());
	int t = 0;
	for(int a:ancestor) ans[a] = ++t, used[t] = 1;

	large = k;
	dfs(p);
	ans[p] = k; used[k] = 1;
	
	int pt = 1;
	for(int i=1; i<=n; ++i){
		if(!ans[i]){
			while(used[pt]) ++pt;
			ans[i] = pt++;
		}
		printf("%d\n", ans[i]);
	}
	
	return 0;
}

K

자연수 $n$과 $m$, 그리고 자연수 수열 $A_i$가 주어졌을 때, 다음 식을 만족하는 자연수 수열 $B_i$를 구하는 문제이다.

$$1+\frac{2^m-1}{n}=\frac{(A_1+B_1)(A_2+B_2)\dots (A_m+B_m)}{B_1 B_2 \dots B_m}$$

너무 하드한 수학문제 같은 인상이라, 처음에는 별로 안 잡으려고 했다.
11분만에 풀어 퍼스트 솔브를 가져간 더민당 팀도 수학을 잘 하는 분이 계시다고 들어서 그런가보다 했었다.
그런데 생각보다 푸는 팀들이 나오고, 내가 맡던 문제들을 다 팀원들한테 준 상태였기 때문에, 이 문제에 대해서 좀 더 고민을 했었다.

먼저 신경쓰인 건, 우변이 $m$개의 값으로 되어 있는데, 좌변에 $2^m-1$이 있는 것이다.
우변을 정리하면 $\left(1+A_i/B_i\right)$들의 곱이기 때문에, 이 항이 하나하나 붙어나가면서 좌변의 값도 만들어나갈 수 있지 않을까 싶었다.

$$\begin{cases}\displaystyle 1+\frac{2^1-1}{n}=\left(1+\frac{A_1}{B_1}\right)? \\ \displaystyle 1+\frac{2^2-1}{n}=\left(1+\frac{A_1}{B_1}\right)\left(1+\frac{A_2}{B_2}\right)? \\ \vdots \\ \displaystyle 1+\frac{2^m-1}{n}=\left(1+\frac{A_1}{B_1}\right)\left(1+\frac{A_2}{B_2}\right)\left(1+\frac{A_3}{B_3}\right) \cdots \left(1+\frac{A_m}{B_m}\right)?\end{cases}$$

그럼 원하는 대로 되기 위해서는 이렇게 되어야 할 것이다...

$$\frac{\displaystyle 1+\frac{2^i-1}{n}}{\displaystyle 1+\frac{2^{i-1}-1}{n}} = 1+\frac{A_i}{B_i}?$$

그런데 이게 좀처럼 예쁘게 풀리지 않았다. $A_i=2^k$ 꼴일 때만 적당한 $B_i$가 존재하게 된다. 그런데 예제를 보면 그렇지 않더라도 멀쩡히 풀고 있었다.

그래서 새로운 시도를 해 봤다. 좌변을 약간 다르게 바꿔보니까...

$$\frac{\displaystyle 1+\frac{2^i-1}{n}}{\displaystyle 1+\frac{2^{i-1}-1}{n/2}} = 1+\frac{A_i}{B_i}$$

만약 이런 식으로 된다면... $n$을 점차 키워나가며 (만들어나가며) 풀 수 있어 보인다.

$$ \frac{n+2^i-1}{n+2^i-2}=1+\frac{A_i}{B_i} \\ \therefore B_i = (n+2^i-2)A_i $$

식이 엄청 간단하게 나왔다. $B_i = (n+2^i-2)A_i $라면 문제의 조건도 만족한다.

그런데.. $n$이 항상 짝수인 것도 아니고. 홀수면 어떻게 되지?
예제 입력 2를 보았다. $n=10$, $m=3$이며,

$$1+\frac{2^1-1}{3} = \left(1+\frac{1}{3}\right) \\ 1+\frac{2^2-1}{5} = \left(1+\frac{1}{3}\right)\left(1+\frac{1}{5}\right) \\ 1+\frac{2^3-1}{10} = \left(1+\frac{1}{3}\right)\left(1+\frac{1}{5}\right)\left(1+\frac{1}{16}\right)$$

좌변에서 $n$이 5에서 10으로 갈 때는 $n+2^3-2=16$이므로 $\left(1+\frac{1}{16}\right)$을 곱해주는 부분이 우리 생각과 꼭 들어맞는 부분인데, 3에서 5로 가는 부분이... 뭔가 신기하다. 뭐지??

뭔가 그럴듯하게 계산을 해보니

$$\frac{\displaystyle 1+\frac{2^m-1}{2n-1}}{\displaystyle 1+\frac{2^{m-1}-1}{n}} = \frac{n}{2n-1} \frac{\displaystyle 2n-1+2^m-1}{\displaystyle n+2^{m-1}-1} = \frac{n}{2n-1} \frac{\displaystyle 2\left(n+2^{m-1}-1 \right)}{n+2^{m-1}-1}=\frac{2n}{2n-1}=1+\frac{1}{2n-1}$$

!!!!!
이렇게 간단하게 정리되는 것이다.
따라서 $n$이 홀수가 될 때는 $B_i = nA_i$를 잡으면 된다.

즉... $n$이 짝수일 때는 $(n/2) \rightarrow n$으로 온 것으로 생각해 $B_i$를 하나 잡아주면, 항이 하나 줄면서 $n$이 절반이 되고,
$n$이 홀수일 때는 $(n+1)/2 \rightarrow n$으로 온 것으로 생각해 $B_i$를 하나 잡아주면, 항이 하나 줄면서 $n$이 거의 절반이 되므로
대충 해결할 수 있...어 보이고,

$m \leq 50$이므로, $m$이 충분히 크다면야 $n$이 무조건 1로 가겠지만, $m$이 너무 작으면 $n$이 1로 가기 전에 쓸 수 있는 $1+\frac{A_i}{B_i}$ 항이 하나 줄지 않나? 싶을 수 있는데,
$m=1$일 때는 그 때의 $n$에 대해서 $B_i=nA_i$를 잡아주면 무조건 $1+\frac{1}{n}=1+\frac{2^1-1}{n}$이 되므로 그 때만 이렇게 처리해주면 된다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll a[51];
ll b[51];

void f(ll n, int m){
	if(m == 1){
		b[m] = a[m] * n;
		return;
	}
	if(n % 2 == 1){
		b[m] = a[m] * n;
		f((n+1)/2, m-1);
	} else {
		b[m] = a[m] * (n + (1ll<<m) - 2);
		f(n/2, m-1);
	}
}

int main()
{
	ll n, m;
	cin >> n >> m;
	for(int i=1; i<=m; ++i) cin >> a[i];
	f(n, m);
	for(int i=1; i<=m; ++i) cout << b[i] << ' ';
	return 0;
}

I

어떤 규칙에 맞게 $N\times N$ 격자를 0 혹은 1로 채운다. 그 조건은...
$a_{ij} + a_{(i+1)j} + a_{i(j+1)} + a_{(i+1)(j+1)} \equiv c_{ij}\text{ mod 2}$ 를 만족해야 한다. $(1\leq i,j \leq N-1)$
즉 모든 2×2 격자에 대해서, 그 격자의 합 mod 2가 되어야 할 값이 정해져 있는 것이다.

여기에, 특정 위치는 반드시 1이라거나, 특정 위치는 반드시 0이라거나 하는 조건들이 여러 개 들어온다. 그것도 들어왔다가 사라졌다가 한다.
이 때 각 시점마다, 지금 들어와있는 조건을 만족하면서 격자를 채우는 방법이 있는가?를 답하는 문제이다.

일단 저 규칙에 대해 생각해보자.
$i=1\textrm{ or }j=1$인 격자들, 즉 ┌ 모양 테두리 부분의 격자들의 값이 정해지면 안쪽 모든 칸들의 값은 저절로 정해질 것이다.
주어진 규칙에 맞게 채워나가면 되니까.
mod 2의 규칙 때문에, 양변에 항을 더하면
$a_{(i+1)(j+1)} \equiv a_{ij} + a_{(i+1)j} + a_{i(j+1)} + c_{ij}\text{ mod 2}$ 로도 쓸 수 있다.
이 식으로 아직 모르는 값을 채워나갈 수 있는 것이다.

반대로 저 격자들의 값은 "자유 변수"의 느낌이다. 안쪽의 "종속 변수"의 값을 결정하는....
예를 들어 $a_{22} = a_{11} + a_{12} + a_{21} + c_{11}$ 이다.
$a_{33} = a_{11} + a_{31} + a_{13} + c_{22}$ 이다.

뭔가 많이 계산을 해보다 보면, 이런 규칙을 알 수 있다.

$$\large a_{ij} = a_{11} + a_{1j} + a_{i1} + \sum _{x<i \\ y<j} c_{xy} \quad \textrm{ for }i,\: j \geq 2$$

각각의 숫자가 어느 위치의 값들에 합해지는지를 보면 규칙을 증명할 수가 있다.
무슨 말이냐면, 예를 들어 $a_{15}$의 값("자유 변수")이 어느 칸들에 더해지는지 생각해보자.
자기 왼쪽 위의 세 칸을 합해 가져오는 규칙 때문에, $a_{25}$에 더해질 것이고,
그걸 가져온 $a_{35}$에도 더해질 것이고, ... 이렇게 $a_{i5}$에는 모두 더해지지만,
$a_{26}$의 경우에는 $a_{15}$와 $a_{25}$를 둘 다 가져오기 때문에 더해지지 않는다. 즉 $a_{15}$가 더해지는 칸들을 1로 나타내면 이런 모양이다.

$$\begin{array}{lr} \cdots & 0 & 1 & 0 & 0 & \cdots \\ \cdots & 0 & 1 & 0 & 0 & \cdots \\ \cdots & 0 & 1 & 0 & 0 & \cdots \\ \quad & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{array}$$

이런 식으로 각각의 변수들에 대해서 생각하면 위의 규칙 식을 증명할 수 있다.

그러면 우리가 각 시점에 풀어야 할 문제는, 다음과 같은 식이 여러 개 있을 때 모두 만족하도록 "자유 변수"를 정하는 방법이 있는지의 여부이다.

$$\begin{cases}\displaystyle a_{11} + a_{1j} + a_{i1} + \sum _{x<i \\ y<j} c_{xy} \equiv p \\ \displaystyle a_{i1}=p \\ \displaystyle a_{1j}=p \\ \displaystyle a_{11}=p \end{cases}$$

너무 복잡해 보이는데, 일단 첫 번째 식에서 $\sum _{x<i \\ y<j} c_{xy}$ 부분은 다른 조건이랑도 상관 없고, 처음에 입력받은 테이블에서 계산을 마치기만 하면 그 뒤로는 그냥 상수이기 때문에, 그냥 양변에 미리 더해주고 처음부터 $p$에 포함되는 것으로 생각해도 된다. 다시 정리하면

$$\begin{cases}\displaystyle a_{11} + a_{1j} + a_{i1} \equiv p \\ \displaystyle a_{i1}=p \\ \displaystyle a_{1j}=p \\ \displaystyle a_{11}=p \end{cases}$$

각 행 첫 값인 자유 변수를 $A_i$, 각 열 첫 값인 자유 변수를 $B_j$, (1, 1)의 값을 $f$라고 썼을 때

$$\begin{cases}\displaystyle A_i + B_j + f \equiv p \\ \displaystyle A_i=p \\ \displaystyle B_j=p \\ \displaystyle f=p \end{cases}$$

이 문제를 풀려고 보니, 또 $f$가 방해이다.
$f=0$일 때와 $f=1$일 때 중 어느 한 쪽이라도 조건을 만족하게 값을 채울 수 있다면 그 시점의 답은 1일 것이므로,
그냥 같은 알고리즘을 두 번 수행하기로 하고 $f$에 대한 생각을 지울 수 있다.
혹시 $f$를 강제하는 마지막 조건이 들어온다면, 지금 고려하는 $f$와 다르다면 그 시간에는 무조건 불가능하다고 보면 된다.

이제 다음 문제를 풀면 된다.

$$\begin{cases}\displaystyle A_i + B_j \equiv p \\ \displaystyle A_i=p \\ \displaystyle B_j=p \end{cases}$$

$p$의 값에 따라서 이렇게도 쓸 수 있다.

$$\begin{cases}\displaystyle A_i \equiv B_j \\ \displaystyle A_i \not \equiv B_j \\ \displaystyle A_i=p \\ \displaystyle B_j=p \end{cases}$$

이제, 알고스팟의 EDITORWARS 문제(링크)로 유명한 알고리즘을 생각할 수 있다.
union & find(disjoint set 뭐시기라고도 부른다) 알고리즘에서 한 가지 정보를 더 추가하는데, "자신과 같은 집합이 되어서는 안 되는 아이"이다.
그리고 "A와 B는 같은 집합이다" 연산 외에, "A와 B는 다른 집합이다"라는 연산을 추가하는 것이다.
그럼 놀랍게도 각각의 연산에서 "그것은 모순입니다"가 나올 수도 있게 된다.

그 알고리즘을 쓰면, 위와 같은 조건이 여러 개 있을 때 $A_i$ 및 $B_j$들을 집합 관계로 묶어보고,
거기서 모순이 없다면 조건을 만족하는 채우기가 존재한다는 것으로 볼 수 있으므로 해결 가능하다.
$A_i = p$ 꼴의 조건은... 사실 그 절대적인 값은 혼자만 있을 때는 의미가 없고, $A_i=p$였는데 $B_j=p$라면 $A_i$와 $B_j$가 같은 집합으로 묶여야 한다는 것이 중요하다. 모든 값을 뒤집어도 앞의 두 조건의 참거짓은 변하지 않기 때문에, 서로 같은지 여부, 그 관계만이 중요하다. 때문에 "항상 1"을 나타내는 원소를 하나 더 추가해, 여기에 "같다" 혹은 "다르다" 연산을 적용해서 모순을 따지면 된다.

그런데.. 문제는 여기서 끝나지 않는다. 시간에 따라 들어오고 나가는 조건이 있기 때문이다.
이러고 보니 완전히 풀 수 없는 문제처럼 보였는데, 여기서 조금 더 생각을 발전시키면 할 수 있다.

일단, union & find에서 union을 했던 순서의 역순으로 되돌릴 수 있다는 아이디어가 필요하다.
parent 배열이 매번 갱신되는데, 덮어씌우는 것이 아니라 vector에 push_back을 하는 것이다.
그럼 현재값은 back()이고, 되돌릴 때는 pop_back()을 하면 된다.

두 번째 아이디어는...
시간축 방향으로 세그먼트 트리를 만들어보자.
그럼 각각의 쿼리가 $\log T$개의 노드에 들어갈 것이다.

그리고... 이 세그먼트 트리를 DFS해보자.
각각의 노드에 있는 쿼리를 모두 처리해보고, 모순이 있는지 확인하고...
DFS에서 돌아갈 때는 union & find 결과를 모두 되돌려보자.

이제 문제가 풀렸다.

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pp;
void read(int& x){ scanf("%d",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define pb push_back
#define eb emplace_back
#define x first
#define y second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)

int n, m, T;
char ans[100010];

const int MAX_V = 2 * 3000 + 1;

vector<pair<pp,int>> event[262144];
vector<pp> par[MAX_V + 1];
vector<pp> dis[MAX_V + 1];
vector<int> hist[20];
int now;

struct solver {
	int my_f;

	void revert(){
		for(int x:hist[now]){
			while(par[x].back().y == now) par[x].pop_back();
			while(dis[x].size() && dis[x].back().y == now) dis[x].pop_back();
		}
		hist[now].clear();
		--now;
	}

	void join(int a, int b){
		if(a==b) return;
		par[a].eb(b, now);
		hist[now].pb(a);
	}

	void disjoin(int a, int b){
		dis[a].eb(b, now);
		dis[b].eb(a, now);
		hist[now].pb(a);
		hist[now].pb(b);
	}

	int R(int x){
		int p=par[x].back().x;
		if(p == x) return x;
		join(x, p=R(p));
		return p;
	}

	bool Same(int a, int b){
		a = R(a); b = R(b);
		int ea = dis[a].size() ? R(dis[a].back().x) : 0;
		int eb = dis[b].size() ? R(dis[b].back().x) : 0;
		if(ea == b) return 0;
		join(a, b);
		if(ea && !eb) swap(ea, eb);
		if(ea) join(ea, eb);
		if(eb) disjoin(b, eb);
		return 1;
	}

	bool Diff(int a, int b){
		a = R(a); b = R(b);
		if(a == b) return 0;
		int ea = dis[a].size() ? R(dis[a].back().x) : 0;
		int eb = dis[b].size() ? R(dis[b].back().x) : 0;
		if(ea) join(ea, b);
		if(eb) join(eb, a);
		disjoin(a, b);
		return 1;
	}

	void dfs(int mp, int tl, int tr){
		bool ok = 1;
		++now;
		for(auto ev : event[mp]){
			int x, y; tie(x, y) = ev.x;
			int p = ev.y;

			if(x == 1){
				if(y == 1){
					if(p != my_f){
						ok=0;
					}
				} else {
					if(p) ok = ok && Same(y+n, 2*n+1);
					else  ok = ok && Diff(y+n, 2*n+1);
				}
			} else {
				if(y == 1){
					if(p) ok = ok && Same(x, 2*n+1);
					else  ok = ok && Diff(x, 2*n+1);
				} else {
					p ^= my_f;
					if(p) ok = ok && Diff(x, y+n);
					else  ok = ok && Same(x, y+n);
				}
			}
			if(!ok) break;
		}

		if(ok){
			if(tl == tr) ans[tl]=1;
			else {
				int mid=(tl+tr)/2;
				dfs(mp*2, tl, mid); dfs(mp*2+1, mid+1, tr);
			}
		}

		revert();
	}

	void solve(){
		const int v = 2*n + 1;
		rrep(i, v){
			par[i].clear();
			par[i].eb(i, 0);
		}
		now = 0;

		dfs(1, 1, T);
	}
} sol[2];

void add(int s, int e, int x, int y, int p, int mp=1, int tl=1, int tr=T){
	if(s <= tl && tr <= e){
		event[mp].eb(pp{x, y}, p);
		return;
	}
	if(e<tl || tr<s) return;
	int mid=(tl+tr)/2;
	add(s,e,x,y,p, mp*2, tl, mid);
	add(s,e,x,y,p, mp*2+1, mid+1, tr);
}

int tbl[3010][3010];
char buf[3010];
void in(){
	read(n, m, T);
	for(int i=2; i<=n; ++i){
		scanf("%s", buf+2);
		for(int j=2; j<=n; ++j){
			tbl[i][j]=tbl[i][j-1]+tbl[i-1][j]-tbl[i-1][j-1] + (buf[j]=='1');
		}
	}
	rep(i, m){
		int s, e, x, y, p;
		read(s, e, x, y, p);
		p ^= (tbl[x][y] & 1);
		add(s, e, x, y, p);
	}
}

int main()
{
	in();
	sol[0].my_f = 0; sol[1].my_f = 1;
	sol[0].solve();
	sol[1].solve();
	rrep(i, T) putchar(48+ans[i]);
	return 0;
}

시간축 방향으로 세그트리를 만들어서, 작업을 되돌리면서 처리하는 아이디어는 처음 생각해봤고, 그것도 대회 중이었기 때문에, 구현에서 실수를 굉장히 많이 했다.

offline dynamic connectivity로 알려져 있는 아이디어라고 한다. 알려진 아이디어를 스스로 생각해냈다는 점이 많이 뿌듯했다.