취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 30050번 문제인 트리와 쿼리 \(10^9\)이다.
문제는 아래 링크를 확인하자.

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

1번 연산이 있어도 없어도 (루트 노드를 제외한) 모든 노드의 깊이는 초기상태보다 깊어지지 않음을 관찰하자. 한편 입력으로 주어지는 수는 \(10^9\) 이하이므로 많아야 30회 부모 노드 방향으로 이동하면 루트에 도달함을 관찰하면, 주어지는 두 점 사이에는 노드가 많아야 60개정도밖에 없다는 것을 알아낼 수 있다. 한편 쿼리가 10만개밖에 없음을 같이 생각하면, 두 점 사이의 경로에 포함되는 모든 노드를 선형적으로 방문해도 문제를 충분히 해결할 수 있음을  수 있다.

1번 연산으로 주어지는 각 노드의 새로운 루트를 map 등의 자료구조로 관리해 LCA를 찾아 문제를 해결하자. 1번 연산이 주어진 적이 없다면 그 노드의 부모는 노드번호를 2로 나눈 몫으로 구할 수 있다.

부모노드로 거슬러올라가는 과정에서 노드번호가 항상 감소한다는 점을 이용하면, 두 노드의 번호가 같아질 때까지 번호가 더 큰 노드를 부모 방향으로 거슬러올라가게 하는 것을 반복하는 것으로 두 노드 사이를 잇는 경로를 찾아낼 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;

int Q;
map<int, int> mp;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> Q;
	while (Q--) {
		int q, x, y; cin >> q >> x >> y;
		if (q == 1) {
			if (mp.count(y)) mp[y] = x;
			else mp.insert(make_pair(y, x));
		}
		else {
			ll ans = x + y;
			while (x != y) {
				if (x > y) {
					if (mp.count(x)) x = mp[x];
					else x /= 2;
					ans += x;
				}
				else {
					if (mp.count(y)) y = mp[y];
					else y /= 2;
					ans += y;
				}
			}
			cout << ans - x << '\n';
		}
	}
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 21278번 문제인 호석이 두 마리 치킨이다.
문제는 아래 링크를 확인하자.

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

주어진 \(N\)의 범위가 매우 작아, Floyd-Warshall 등의 알고리즘을 이용해 모든 건물 사이의 최단거리를 미리 계산할 수 있음을 관찰하자.

모든 건물 사이의 최단거리를 알 수 있다면, 남는 것은 치킨집을 열 두 장소 고르는 모든 경우(\(O(N^2)\)가지)에 대하여 모든 각 지점에서 "두 장소까지의 거리 중 최솟값"을 직접 더해보는 것(\(O(N)\))을 반복해 문제를 해결하자. 이 방법의 시간복잡도는 \(O(N^3)\)으로, \(N\)이 충분히 작아 이 방법으로도 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <cstring>
using namespace std;

int N, K;
int dist[101][101];
int ansA, ansB, ansD = 2000000007;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	memset(dist, 0x3f, sizeof(dist));
	cin >> N >> K;
	for (int i = 1; i <= N; i++) dist[i][i] = 0;
	while (K--) {
		int x, y; cin >> x >> y;
		dist[x][y] = dist[y][x] = 1;
	}

	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int j = i + 1; j <= N; j++) {
			int val = 0;
			for (int k = 1; k <= N; k++) {
				val += min(dist[k][i], dist[k][j]);
			}
			if (val < ansD) ansD = val, ansA = i, ansB = j;
		}
	}

	cout << ansA << ' ' << ansB << ' ' << ansD * 2;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2632번 문제인 피자판매이다.
문제는 아래 링크를 확인하자.

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

\(N\)조각으로 나뉘어진 피자에서 판매할 수 있는 모양은 \(O(N^2)\)가지뿐임을 관찰하자. 따라서 각 피자에서 얻을 수 있는 모든 경우에 제한시간 내에 충분히 접근해 볼 수 있다. 이해가 되지 않는다면, 구간 \([L,R]\)의 개수를 생각해보자. 그리고 각 구간을 시계방향으로 \(L\)번 조각부터 \(R\)번 조각까지의 모임과 대응시켜보자. (단, 피자 전체를 한 조각으로 생각하는 경우에 유의하자. 또한 피자를 판매하지 않는 경우도 구현에 따라 고려해야 함에 유의하자.)

주어진 조건에 따라 한 피자에서 얻을 수 있는 피자 조각의 넓이는 100만 이하이므로, 합이 손님이 원하는 피자의 크기가 되게끔 두 피자에서 피자를 고르는 경우를 모두 찾아 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int N, M, K;
int A[2001], B[2001];
int X[2000001], Y[2000001];
ll ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> K >> N >> M;
	for (int i = 1; i <= N; i++) cin >> A[i];
	for (int i = 1; i <= N; i++) A[i + N] = A[i];
	for (int i = 1; i <= N * 2; i++) A[i] += A[i - 1];
	for (int L = 0; L < N; L++) {
		for (int k = 1; k < N; k++) {
			X[A[L + k] - A[L]]++;
		}
	}
	X[0]++, X[A[N]]++;

	for (int i = 1; i <= M; i++) cin >> B[i];
	for (int i = 1; i <= M; i++) B[i + M] = B[i];
	for (int i = 1; i <= M * 2; i++) B[i] += B[i - 1];
	for (int L = 0; L < M; L++) {
		for (int k = 1; k < M; k++) {
			Y[B[L + k] - B[L]]++;
		}
	}
	Y[0]++, Y[B[M]]++;

	for (int i = 0; i <= K; i++) {
		ans += (ll)X[i] * Y[K - i];
	}

	cout << ans;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 26654번 문제인 원점이다.
문제는 아래 링크를 확인하자.

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

정다각형의 각 꼭짓점 또한 원 하나의 원주(원의 둘레) 위에 전부 올릴 수 있음을 생각하면 문제를 쉽게 접근할 수 있다.

정다각형의 외접원의 반지름보다 반지름이 큰 원은 정다각형의 모든 꼭짓점을 포함할 수 있다. 그렇지 않을 경우 원은 정다각형의 외접원의 원주의 절반 이상을 덮을 수 없으므로 많아야 \(N/2\)개의 꼭짓점만을 포함할 수 있다.

정다각형의 외접원의 반지름을 먼저 계산하고(사인 법칙 등 구할 방법은 많으니 편한 방법을 선택하자), 위의 관찰을 이용해 몇 개의 꼭짓점을 포함할 수 있는지 이분탐색을 이용해 구해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <cmath>
using namespace std;
typedef long double ld;

const ld PI = acosl(-1);
int N, A, B;
ld R1, R2, theta;
ld X, Y;

void solve() {
	cin >> N >> A >> B;
	theta = PI * 2 / N;
	R1 = sqrtl((ld)A * 2 / (N * sinl(theta)));
	R2 = sqrtl((ld)B / PI);

	if (R1 <= R2) {
		cout << N << '\n';
		return;
	}

	X = cosl(theta), Y = sinl(theta);
	if (hypotl(1 - X, Y) * R1 > R2 * 2) {
		cout << 1 << '\n';
		return;
	}
	int L = 1, R = N / 2;
	while (L < R) {
		int mid = (L + R) / 2 + 1;
		X = cosl(theta * mid), Y = sinl(theta * mid);
		if (hypotl(1 - X, Y) * R1 > R2 * 2) {
			R = mid - 1;
		}
		else L = mid;
	}
	cout << L + 1 << '\n';
}

int T;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> T;
	while (T--) solve();
}

BOJ Random Defense #17

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1635번 문제인 1 또는 -1이다.
문제는 아래 링크를 확인하자.

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

주어지는 수열\(a_1 \cdots a_N\)은 다음과 같은 두 가지 성질이 있다.

(1) \(a_1 + \cdots + a_N\)은 짝수이다.

(2) 1에서 계산한 값이 0이 아니라면, \(a_1 + \cdots + a_k = a_{k+1} + \cdots + a_N\)을 만족시키는 \(1\le k<N \)인 정수 \(k\)가 존재한다. (증명은 값이 contiguous하게 변한다는 점을 이용해 IVT(중간값 정리)와 유사하게 가능하다.)

2의 식의 우변을 좌변으로 넘기면 각 항에 1 또는 -1을 곱해 총합이 0이 되게 계수를 설정하는 방법을 하나 항상 얻을 수 있다. 또한 이 때 나올 수 있는 \(b_i\)의 가짓수는 \(k\)의 가짓수와 같으므로 총 \(N-1\)가지임을 알 수 있다.

1에서 계산한 값이 0인 경우 \(b_i\)의 값을 모두 1로 두어 조건을 만족시킬 수 있음을 추가로 관찰하면, 총 \(N\)가지의 \(b_i\)를 이용해 주어진 모든 식을 0으로 항상 만들 수 있음을 확인할 수 있다.

위 내용을 구현해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N, M;
int A[102];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	while (M--) {
		int total = 0;
		for (int i = 1; i <= N; i++) {
			cin >> A[i];
			total += A[i];
		}
		if (!total) {
			for (int i = 1; i <= N; i++) {
				cout << 1 << ' ';
			}
			cout << '\n';
		}
		else {
			int psum = 0;
			for (int i = 1; i <= N; i++) {
				psum += A[i];
				if (psum * 2 == total) {
					for (int k = 1; k <= i; k++) {
						cout << 1 << ' ';
					}
					for (int k = i + 1; k <= N; k++) {
						cout << -1 << ' ';
					}
					cout << '\n';
					break;
				}
			}
		}
	}
}

BOJ Random Defense #20

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 23000번 문제인 L Shaped Plots이다.
문제는 아래 링크를 확인하자.

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

문제에서 찾아야하는 L모양은 (1) 어떠한 교차점이 있으며, (2) 그 교차점에서 2 이상의 \(k\)에 대해 수직으로 \(k\)칸 및 \(2k\)칸이 뻗은 모양으로 생각할 수 있다. 이와 같이 생각하면 해당 모양은 각 칸에서 수직으로 뻗어나갈 두 방향을 고르는 방법 네 가지와 어느 방향으로 더 많은 칸을 연결할지의 두 가지의 곱 8가지 경우를 살피는 것으로 모든 경우의 수를 고려할 수 있음을 알 수 있다.

다만, 모든 L모양 상태에 직접 접근하기에는 경우의 수가 너무 많아질 수 있으므로, 각 칸에 대하여 상하좌우방향으로 이을 수 있는 칸의 개수의 최댓값을 미리 전처리해두자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;

int R, C;
int A[1002][1002];
int sR[1002][1002];
int sL[1002][1002];
int sU[1002][1002];
int sD[1002][1002];

void solve() {
    memset(sR, 0, sizeof(sR));
    memset(sL, 0, sizeof(sL));
    memset(sU, 0, sizeof(sU));
    memset(sD, 0, sizeof(sD));
    ll ans = 0;
    cin >> R >> C;
    for (int r = 1; r <= R; r++) {
        for (int c = 1; c <= C; c++) {
            cin >> A[r][c];
        }
    }

    for (int r = 1; r <= R; r++) {
        for (int c = C; c > 0; c--) {
            if (A[r][c]) sR[r][c] = sR[r][c + 1] + 1;
        }
    }
    for (int r = 1; r <= R; r++) {
        for (int c = 1; c <= C; c++) {
            if (A[r][c]) sL[r][c] = sL[r][c - 1] + 1;
        }
    }
    for (int c = 1; c <= C; c++) {
        for (int r = R; r > 0; r--) {
            if (A[r][c]) sD[r][c] = sD[r + 1][c] + 1;
        }
    }
    for (int c = 1; c <= C; c++) {
        for (int r = 1; r <= R; r++) {
            if (A[r][c]) sU[r][c] = sU[r - 1][c] + 1;
        }
    }

    for (int r = 1; r <= R; r++) {
        for (int c = 1; c <= C; c++) {
            ans += max(min(sU[r][c] / 2, sR[r][c]) - 1, 0);
            ans += max(min(sU[r][c], sR[r][c] / 2) - 1, 0);
            ans += max(min(sR[r][c] / 2, sD[r][c]) - 1, 0);
            ans += max(min(sR[r][c], sD[r][c] / 2) - 1, 0);
            ans += max(min(sD[r][c] / 2, sL[r][c]) - 1, 0);
            ans += max(min(sD[r][c], sL[r][c] / 2) - 1, 0);
            ans += max(min(sL[r][c] / 2, sU[r][c]) - 1, 0);
            ans += max(min(sL[r][c], sU[r][c] / 2) - 1, 0);
        }
    }

    cout << ans << '\n';
}

int T;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> T;
    for (int t = 1; t <= T; t++) {
        cout << "Case #" << t << ": ";
        solve();
    }
}

BOJ Random Defense #11