취미로 코딩하기

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

이번에 볼 문제는 백준 1206번 문제인 사람의 수이다.
문제는 아래 링크를 확인하자.

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

어떤 평균점수가 주어져도 10000명의 사람이 있다면 모든 평균 점수가 나오게끔 사람들이 투표할 수 있음을 관찰하자. 따라서, 1부터 10000까지 사람의 수로 가능한 수치를 하나하나 확인해나가는 완전탐색 풀이로 문제를 충분히 해결할 수 있다.

이 문제의 경우 버림을 통해 소수의 값을 계산함에 유의하자. Long Division(장제법; 초등학생들이 나눗셈의 몫과 나머지 구하던 그 방법)을 직접 구현하면 문제가 요구하는 값을 오차 없이 계산할 수 있다.

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

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

int N;
int A[50];
string s;

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> s;
		if (s.length() == 6) continue;
		A[i] = (s.front() - '0') * 1000 + stoi(s.substr(2, 3));
	}
	for (int k = 1; k < 10001; k++) {
		bool chk = 1;
		for (int i = 0; i < N; i++) {
			int L = 0, R = k * 10;
			while (L <= R) {
				int mid = (L + R) / 2;
				int val = 0;
				for (int _ = 0; _ < 4; _++) {
					val = val * 10 + mid / k;
					mid %= k;
					mid *= 10;
				}
				if (val < A[i]) L = (L + R) / 2 + 1;
				else if (val > A[i]) R = (L + R) / 2 - 1;
				else goto BREAK1;
			}
			chk = 0;
			goto BREAK2;
			BREAK1:
			1;
		}
		BREAK2:
		if (chk) {
			cout << k;
			return 0;
		}
	}
}

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

이번에 볼 문제는 백준 32065번 문제인 Short Function이다.
문제는 아래 링크를 확인하자.

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

주어진 식이 값을 곱해나가는 규칙이 마치 sparse table(희소 테이블)의 값을 채워나가는 과정과 유사해보이지 않는가?

위 관찰을 이용하면, 각 A[i]의 값은 결국 주어진 배열이 끝없이 반복되는 수열의 i번째 항부터 시작되는 길이 \(2^K\)의 배열에 적힌 수의 곱이 됨을 알 수 있다. 대충 \(2^K\)을 \(N\)으로 나눈 몫만큼 배열 전체의 곱을 곱하고, 나머지만큼 배열의 구간곱을 구해 둘을 곱하는 것으로 원하는 값을 계산하자.

그런데 이 값을 그냥 계산하기에는 \(2^K\)의 값이 너무 커서 계산이 어렵다. 구하고자 하는 값이 소수 998244353으로 나눈 나머지이므로, 배열 전체를 998244352회 곱한 값이 1이 됨을 이용해 이 과정을 가능하게 만들자. 즉, \(2^K\)을 \(N\)으로 나눈 몫 대신 이 값을 998244352로 나눈 나머지를 이용해도 문제의 답이 같게 나옴을 이용하자. 이는 998244353이 소수이고 배열을 구성하는 각 원소가 998244353의 배수가 아니므로 가능하다.

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

#include <iostream>
using namespace std;
typedef __int128 lll;

int tmp;
lll MOD = 998244353, NMOD, ansconst, qrylen;
lll N, K, total = 1, A[100001];
lll totalcnt;

lll seg[262145];
lll init(int L, int R, int sI) {
	if (L < R) return seg[sI] = init(L, (L + R) / 2, sI * 2) * init((L + R) / 2 + 1, R, sI * 2 + 1) % MOD;
	return seg[sI] = A[L];
}
lll qry(int L, int R, int qL, int qR, int sI) {
	if (R < qL || qR < L) return 1;
	if (qL <= L && R <= qR) return seg[sI];
	return qry(L, (L + R) / 2, qL, qR, sI * 2) * qry((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1) % MOD;
}

lll bexp(lll X, lll KK) {
	lll ret = 1;
	while (KK) {
		if (KK & 1) ret = ret * X % MOD;
		KK >>= 1, X = X * X % MOD;
	}
	return ret;
}

lll func(lll x, lll M) { // 2^x의 mod M을 계산
	lll ret = 1, val = 2;
	while (x) {
		if (x & 1) ret = ret * val % M;
		val = val * val % M;
		x >>= 1;
	}
	return ret;
}

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

	cin >> tmp; N = tmp;
	cin >> tmp; K = tmp;
	NMOD = N * (MOD - 1);
	for (int i = 1; i <= N; i++) {
		cin >> tmp, A[i] = tmp;
		total = total * A[i] % MOD;
	}
	totalcnt = func(K, NMOD) / N;
	ansconst = bexp(total, totalcnt);
	qrylen = func(K, N);

	if (!qrylen) {
		for (int i = 1; i <= N; i++) cout << (int)ansconst << ' ';
		return 0;
	}
	
	init(1, N, 1);
	for (int i = 1; i <= N; i++) {
		int L = i, R = i + qrylen - 1;
		if (R <= N) cout << (int)(ansconst * qry(1, N, L, R, 1) % MOD) << ' ';
		else cout << (int)(ansconst * (qry(1, N, L, N, 1) * qry(1, N, 1, R - N, 1) % MOD) % MOD) << ' ';
	}
}

랜덤 마라톤 · 코스 12 H번

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

이번에 볼 문제는 백준 24539번 문제인 암호 해독이다.
문제는 아래 링크를 확인하자.

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

만약 주어지는 모든 구간의 오른쪽 끝이 서로 다르다면 구간들을 오른쪽 끝 오름차순으로 순회하면서 구간 xor이 조건을 만족하도록 값을 하나씩 할당하는 것으로 문제를 해결할 수 있을 것이다. 오른쪽 끝이 같은 경우를 효율적으로 제거해 문제를 해결하자.

구체적으로, 오른쪽 끝이 같은 여러 구간이 있을 경우, 그 중 (길이가 다른) 두 구간은 짧은 구간과 (긴 구간 - 짧은 구간)의 xor 정보로 대체하는 것으로 모든 구간의 오른쪽 끝이 같은 경우를 없애자. 물론 길이가 같은 두 구간의 경우 서로 값이 같아야 함을 확인해야 한다.

단, 위 과정을 아무 생각 없이 구현하면 구간 쪼개기를 \(O(N^2\))번 하게 되어 문제가 생긴다. 오른쪽 끝 내림차순으로 보면서, 같은 오른쪽 끝을 가진 구간들을 왼쪽 끝 순으로 정렬해 인접한 두 구간에 대해서만 계산해 구간 쪼개기를 진행하면 총 \(O(N)\)회만 쪼개게 되어 문제를 안정적으로 해결할 수 있다.

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, M;
vector<pair<int, int>> vec[200001];
int A[200001];

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

	cin >> N >> M;
	while (M--) {
		int x, y, k; cin >> x >> y >> k;
		vec[y].emplace_back(make_pair(x, k));
	}

	for (int R = N; R > 0; R--) {
		auto &v = vec[R];
		if (v.empty()) continue;
		int vsize = v.size();
		sort(v.begin(), v.end());
		for (int i = 0; i + 1 < vsize; i++) {
			if (v[i].first == v[i + 1].first) {
				if (v[i].second == v[i + 1].second) continue;
				cout << -1;
				return 0;
			}
			vec[v[i + 1].first - 1].emplace_back(make_pair(v[i].first, v[i].second ^ v[i + 1].second));
		}
	}

	for (int i = 1; i <= N; i++) {
		if (!vec[i].empty()) A[i] = A[vec[i].back().first - 1] ^ A[i - 1] ^ vec[i].back().second;
		cout << A[i] << ' ';
		A[i] ^= A[i - 1];
	}
}

랜덤 마라톤 · 코스 12 G번

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

이번에 볼 문제는 백준 13733번 문제인 Square Deal이다.
문제는 아래 링크를 확인하자.

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

주어진 세 직사각형을 겹치지 않게 이어붙여 정사각형을 구성할 수 있는지 묻는 문제이다.

정사각형을 세 직사각형으로 자르는 방법은 문제에서 그림으로 주어진 두 방법밖에 없음을 관찰하면, 주어진 문제는 두 직사각형을 합쳐 다른 직사각형을 얻는 과정을 두 번 (가능한 대로) 반복해 정사각형을 얻을 수 있는지 확인하는 것으로 해결할 수 있다.

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

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

int A, B, C, D, E, F;
bool chk;
void func(int W, int X, int Y, int Z) {
	if (W == Y && X + Z == Y) chk = 1;
	if (W == Z && X + Y == Z) chk = 1;
	if (X == Y && W + Z == Y) chk = 1;
	if (X == Z && W + Y == Z) chk = 1;
}

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

	cin >> A >> B >> C >> D >> E >> F;
	if (A == C) func(A, B + D, E, F);
	if (A == D) func(A, B + C, E, F);
	if (B == C) func(B, A + D, E, F);
	if (B == D) func(B, A + C, E, F);
	swap(A, C); swap(C, E);
	swap(B, D); swap(D, F);
	if (A == C) func(A, B + D, E, F);
	if (A == D) func(A, B + C, E, F);
	if (B == C) func(B, A + D, E, F);
	if (B == D) func(B, A + C, E, F);
	swap(A, C); swap(C, E);
	swap(B, D); swap(D, F);
	if (A == C) func(A, B + D, E, F);
	if (A == D) func(A, B + C, E, F);
	if (B == C) func(B, A + D, E, F);
	if (B == D) func(B, A + C, E, F);

	if (chk) cout << "YES";
	else cout << "NO";
}

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

이번에 볼 문제는 백준 17797번 문제인 Dome Construction이다.
문제는 아래 링크를 확인하자.

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

주어진 좌표들과 원점 사이의 거리들 중 \(k\)번째로 가까운 점을 포함하는 dome은 다른 그보다 더 가까운(또는 같은 거리인) \(k-1\)개의 점 또한 포함함을 관찰하자. 따라서 \(k\)번째로 가까운 점의 거리를 구하는 것으로 문제를 해결할 수 있다.

피타고라스 정리와 정렬을 이용해 문제를 간단하게 해결하자.

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

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

int N, K;
ld x, y, z;
ld A[100000];

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

	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> x >> y >> z;
		A[i] = x * x + y * y + z * z;
	}
	sort(A, A + N);
	cout << fixed;
	cout.precision(10);
	cout << sqrtl(A[K - 1]);
}

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

이번에 볼 문제는 백준 1999번 문제인 최대최소이다.
문제는 아래 링크를 확인하자.

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

어떤 직사각형 영역에 특정 수가 포함되어있는지 여부를 구할 수 있는 방법은 무엇이 있을까? 여기에서는 해당 수가 포함되어 있는 칸에는 1, 그렇지 않은 칸에는 0을 채운 후 2D Prefix Sum을 준비해두는 방법을 생각해보자. 이 때, 직사각형 영역의 수의 합이 0이라면 특정 수가 없는 것이고 그렇지 않다면 특정 수가 있는 것이다.

0부터 250까지의 각각의 수에 대하여 위와 같은 2D prefix sum table을 준비해두고, 각 영역에 대하여 251가지 수에 대해 해당 수가 존재하는지 확인해 문제가 요구하는 값을 구하자. 그 중 최댓값과 최솟값을 구해 출력하는 것으로 문제를 해결할 수 있다.

여담으로, 이 문제는 답을 구해야 하는 영역의 크기가 고정되어 있다는 점을 이용하면 더욱 빠른 풀이를 얻을 수 있다. 그 방법은 deque range minimum(maximum) trick을 행방향과 열방향으로 한번씩 적용하는 것이다. 이 방식의 시간복잡도는 \(O(N^2)\)이다.

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

#include <iostream>
using namespace std;

int N, K, Q;
int A[251][251][251];

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

	cin >> N >> K >> Q;
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			int x; cin >> x;
			A[x][r][c] = 1;
		}
	}

	for (int k = 0; k < 251; k++) {
		for (int r = 1; r <= N; r++) {
			for (int c = 1; c <= N; c++) {
				A[k][r][c] += A[k][r - 1][c] + A[k][r][c - 1] - A[k][r - 1][c - 1];
			}
		}
	}
	while (Q--) {
		int r, c; cin >> r >> c;
		int mn = 1000000007, mx = -1;
		for (int k = 0; k < 251; k++) {
			if (A[k][r + K - 1][c + K - 1] - A[k][r - 1][c + K - 1] - A[k][r + K - 1][c - 1] + A[k][r - 1][c - 1]) {
				mn = min(mn, k), mx = max(mx, k);
			}
		}
		cout << mx - mn << '\n';
	}
}