취미로 코딩하기

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

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

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

가장 쉽게 떠울릴 수 있는 접근으로, 모든 불이 꺼질 때까지 스위치를 작동시키는 것을 시도하고 그러한 때가 존재한다면 그 때까지의 스위치 작동 횟수를 답으로 삼는 것이 있다. 이 접근방법의 문제점은 모든 불을 끌 수 없는 경우 스위치를 끝없이 작동시키게 되어 문제를 해결할 수 없다는 것인데, 어떤 조건으로 불을 끌 수 없는 경우 반복을 중단시킬 수 있다면 이러한 문제를 해소할 수 있다. 모든 불이 꺼지는 경우가 없는 경우라는 것을 확신하기 위해 스위치를 몇 번 작동해봐야 할까?

위 질문의 답은 스위치의 특징을 관찰하면 쉽게 알아낼 수 있다. 구체적으로, 각 스위치는 짝수 번 작동시키면 작동시키지 않은 것과 같은 모습을 보임을 이용하면, 모든 스위치를 정확히 2바퀴 작동시키면 모든 불의 상태가 초기와 똑같아지고 그 이후로 나타나는 불의 상태는 앞서 나온 형태의 반복임을 알 수 있다.

위 관찰을 이용해 불을 켜고 끄는 시뮬레이션을 진행하는 코드를 작성하여 문제를 해결하자.

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

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

int N, M;
int cnt, sgn[1001];
vector<int> vec[1000];

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

	cin >> N >> M;
	int K; cin >> K; cnt = K;
	while (K--) {
		int x; cin >> x;
		sgn[x] = 1;
	}
	for (int i = 0; i < N; i++) {
		cin >> K;
		while (K--) {
			cin >> vec[i].emplace_back();
		}
	}

	for (int i = 0; i < 2000; i++) {
		for (auto &x : vec[i % N]) {
			if (sgn[x]) sgn[x] = 0, cnt--;
			else sgn[x] = 1, cnt++;
		}
		if (!cnt) {
			cout << i + 1;
			return 0;
		}
	}

	cout << -1;
}

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

이번에 볼 문제는 백준 23352번 문제인 방탈출이다.
문제는 아래 링크를 확인하자.

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

어떤 한 칸으로부터 다른 모든 칸까지의 최단경로를 구하는 것은 전체 그래프에 대하여 BFS를 한 번 시행하는 것으로 해낼 수 있다. 이 시간복잡도는 \(O(RC)\)이다.

모든 두 칸의 쌍에 대하여 두 칸을 잇는 최단경로의 길이는 위와 같은 탐색을 모든 칸에서 \(O(RC)\)회 시작해보는 것으로 접근 가능하므로, 가장 긴 최단경로의 길이를 갖는 경로 중 양 끝 칸의 수의 합이 가장 큰 경우는 \(O(R^2C^2)\)으로 구할 수 있다. \(R\)과 \(C\)의 값이 충분히 작으므로 이는 시간 내에 충분히 동작한다.

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

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

int R, C;
int board[52][52];
int dist[52][52];
int adist, ans;
int dr[4] = {0,0,1,-1};
int dc[4] = {1,-1,0,0};
queue<pair<int, int>> que;
void bfs(int sR, int sC) {
	memset(dist, 0, sizeof(dist));
	que.push(make_pair(sR, sC));
	dist[sR][sC] = 1;
	while (!que.empty()) {
		int r = que.front().first, c = que.front().second; que.pop();
		if (dist[r][c] > adist) adist = dist[r][c], ans = board[sR][sC] + board[r][c];
		else if (dist[r][c] == adist) ans = max(ans, board[sR][sC] + board[r][c]);
		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (!board[rr][cc] || dist[rr][cc]) continue;
			dist[rr][cc] = dist[r][c] + 1;
			que.push(make_pair(rr, cc));
		}
	}
}

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

	cin >> R >> C;
	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) {
			cin >> board[r][c];
		}
	}

	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) {
			if (board[r][c]) bfs(r, c);
		}
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 16203번 문제인 까다로운 수 찾기이다.
문제는 아래 링크를 확인하자.

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

0~9의 각 숫자로 시작하는 x(2 이상)자리 A-까다로운 수의 개수는 x-1자리 A-까다로운 수에서의 정보를 이용해 계산이 가능하다. 또한, A가 9가 아니라면 x자리 A-까다로운 수의 개수는 지수적으로 증가함을 관찰할 수 있다. 이를 이용하면 A가 9가 아닌 경우 간단한 사전순 dp와 그 역추적을 이용해 문제를 해결할 수 있다.

한편, A가 9라면 한자리 수를 제외한 경우 9로 시작해 9와 0이 번갈아 등장하는 형태의 수만이 정답이 됨을 알 수 있다. 해당 수들을 9부터 크기순으로 살피면 원하는 수는 "10배 후 0을 더하기"와 "10배 후 9를 더하기"를 번갈아가면서 반복하는 것으로 얻을 수 있음을 알 수 있다. 즉, 9 이상의 9-까다로운 수 중 위와 같은 반복을 짝수번 해야 한다면 이는 9에 "100배 후 9를 더하기"를 적절한 횟수 반복하는 것으로 답을 구할 수 있고, 홀수번 해야한다면 이는 90에 "100배 후 90을 더하기"를 적절한 횟수 반복하는 것으로 답을 구할 수 있음을 알 수 있다.

일차함수에 값을 \(k\)회 반복해 대입하는 것은 함수의 합성을 이용하여(binary exponentiation과 같은 방법으로) \(O(\lg k)\)에 해낼 수 있다. 이를 이용해 A=9인 경우의 문제를 해결하자.

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

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

ll N, K;
ll A[10][10], tmp[10]; vector<ll> vec[10]; // vec[i]: i로 시작하는 수 최대 개수. 0으로 시작하는 수는 계수할 때 따로 무시
int V[10];

ll rsum(int L, int R) {
	ll ret = 0;
	for (int i = L; i <= R; i++) ret += vec[i].back();
	return ret;
}

void solve9() {
	if (N < 9) {
		cout << N << '\n';
		return;
	}
	N -= 8;

	ll ans, AA, BB;
	if (N & 1) {
		ans = 9;
		AA = 100, BB = 9;
	}
	else ans = 0, AA = 100, BB = 90;
	N /= 2;
	while (N) {
		if (N & 1) {
			ans = (AA * ans + BB) % 1000000007;
		}
		ll AAA = (AA * AA) % 1000000007, BBB = (AA * BB + BB) % 1000000007;
		AA = AAA, BB = BBB;
		N >>= 1;
	}
	cout << ans << '\n';
}

void solve() {
	cin >> N >> K;
	if (K == 9) {
		solve9();
		return;
	}
	for (int r = 0; r < 10; r++) {
		for (int c = 0; c < 10; c++) {
			if (abs(r - c) < K) A[r][c] = 0;
			else A[r][c] = 1;
		}
	}
	for (int r = 0; r < 10; r++) vec[r].clear(), vec[r].emplace_back(1);
	while (rsum(1, 9) < N) {
		N -= rsum(1, 9);
		for (int r = 0; r < 10; r++) {
			tmp[r] = 0;
			for (int c = 0; c < 10; c++) tmp[r] += A[r][c] * vec[c].back();
		}
		for (int r = 0; r < 10; r++) vec[r].emplace_back(tmp[r]);
	}
	ll ans = 0;
	memset(V, 0, sizeof(V));
	for (int i = 1; i < 10; i++) V[i] = 1;
	while (!vec[0].empty()) {
		int id = 0;
		while (1) {
			if (!V[id]) id++;
			else if (vec[id].back() >= N) break;
			else {
				N -= vec[id].back();
				id++;
			}
		}
		ans = (ans * 10 + id) % 1000000007;
		for (int i = 0; i < 10; i++) vec[i].pop_back();
		for (int i = 0; i < 10; i++) {
			if (abs(i - id) < K) V[i] = 0;
			else V[i] = 1;
		}
	}
	cout << ans << '\n';
}

int T;

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

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

#랜덤 마라톤 · 코스 7 H번

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

이번에 볼 문제는 백준 16132번 문제인 그룹 나누기 (Subset)이다.
문제는 아래 링크를 확인하자.

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

\(N\)개의 수의 총합은 \(N(N+1)/2\)와 같고, 이 값이 홀수이면 두 부분집합의 각각의 원소의 합이 같게끔 집합을 분할할 수 없어 답은 0이 된다. 아래에서는 이 값이 짝수인 경우만을 생각할 것이다. 이 경우, 두 집합 각각의 원소의 합은 \(N(N+1)/4\)와 같게 된다.

주어진 수들을 적절히 골라 그 합이 정확히 \(N(N+1)/4\)가 되게끔 하는 경우의 수는 knapsack DP를 이용해 간단하게 구할 수 있다. \(N\)의 값이 충분히 작으므로 탐색해야 하는 범위 \(N(N+1)/4\)와 총 수의 개수 \(N\)의 값이 작기 때문이다.

한편, 위에서 구한 경우의 수는 정확히 두 개씩 짝을 이루어 두 부분집합을 구성하는 경우의 수를 이루므로, 위에서 구한 경우의 수에 2를 나눈 값이 문제의 답이 된다. 이를 이용해 문제를 해결하는 코드를 작성하자.

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

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

int N, NN;
ll dp[1276];

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

	cin >> N;
	NN = N * (N + 1) / 2;
	if (NN & 1) {
		cout << 0;
		return 0;
	}
	NN /= 2;
	dp[0] = 1;
	for (int i = 1; i <= N; i++) {
		for (int k = NN; k >= i; k--) {
			dp[k] += dp[k - i];
		}
	}
	cout << dp[NN] / 2;
}

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

이번에 볼 문제는 백준 12065번 문제인 gMatrix (Large)이다.
문제는 아래 링크를 확인하자.

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

모든 "K행K열의 부분행렬에 적힌 수의 최댓값"의 합을 구하는 문제이다.

각 행의 모든 연속한 길이 K의 구간의 최댓값은 deque을 이용한 trick으로 선형 시간 복잡도에 전부 구할 수 있다. 이 값들을 다시 열 방향으로 살피면 연속한 길이 K의 구간에 대한 최댓값, 즉 K행K열의 부분행렬에 대한 최댓값을 빠르게 전부 구할 수 있다.

위 관찰을 이용해 문제를 해결하자.

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

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

int N, K, CC, X;
int R[3001], C[3001];
int A[3001][3001];
deque<pair<int, int>> dq[3001]; // {최댓값, 열}

void solve() {
	ll ans = 0;
	cin >> N >> K >> CC >> X;
	for (int i = 1; i <= N; i++) cin >> R[i];
	for (int i = 1; i <= N; i++) cin >> C[i];
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			A[r][c] = ((ll)R[r] * r + (ll)C[c] * c + CC) % X;
		}
	}
	for (int r = 1; r <= N; r++) {
		auto &dque = dq[r];
		dque.clear();
		for (int c = 1; c < K; c++) {
			int val = A[r][c];
			while (!dque.empty() && dque.back().first <= val) dque.pop_back();
			dque.push_back(make_pair(val, c));
		}
	}
	for (int c = K; c <= N; c++) {
		deque<pair<int, int>> dqdq;
		for (int r = 1; r < K; r++) {
			auto &dque = dq[r];
			int val = A[r][c];
			while (!dque.empty() && dque.back().first <= val) dque.pop_back();
			dque.push_back(make_pair(val, c));
			while (dque.front().second + K <= c) dque.pop_front();
			val = dque.front().first;
			while (!dqdq.empty() && dqdq.back().first <= val) dqdq.pop_back();
			dqdq.push_back(make_pair(val, r));
		}
		for (int r = K; r <= N; r++) {
			auto &dque = dq[r];
			int val = A[r][c];
			while (!dque.empty() && dque.back().first <= val) dque.pop_back();
			dque.push_back(make_pair(val, c));
			while (dque.front().second + K <= c) dque.pop_front();
			val = dque.front().first;
			while (!dqdq.empty() && dqdq.back().first <= val) dqdq.pop_back();
			dqdq.push_back(make_pair(val, r));
			while (dqdq.front().second + K <= r) dqdq.pop_front();
			ans += dqdq.front().first;
		}
	}
	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();
	}
}

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

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

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

조건을 만족하는 룩의 배치는 1번부터 \(n\)번까지의 룩이 차례대로 몇 번째 행에 있는지, 몇 번째 열에 있는지를 나타내는 두 순열은 각각 교란순열(derangement;subfactorial)을 이룬다는 것을 어렵지 않게 관찰할 수 있다. 그리고 조금만 더 생각하면 그 역도 성립함을 관찰할 수 있다. 따라서 문제의 답은 크기가 \(n\)인 교란순열의 개수의 제곱을 \(m\)으로 나누어 구할 수 있다.

교란순열의 값을 구하는 대표적인 방법으로는 포제원리(포함-배제의 원리; Inclusion-Exclusion Principle)를 이용하는 것이 있다. 이를 이용하면 크기가 \(n\)인 교란순열의 개수는 \(\binom{n}{0}(n-0)! - \binom{n}{1}(n-1)! + \binom{n}{2}(n-2)! - \cdots\) 와 같은 형태로 계산할 수 있다. 앞의 이항계수는 확실하게 위치를 고정시킬 원소를 고르는 경우의 수, 뒤의 팩토리얼은 남은 수를 나열하는 과정으로 해석하자.

구하는 값은 답을 \(m\)으로 나눈 나머지이므로 계산해볼 필요가 있는 항의 개수가 \(m\)개 이하임을 관찰하자. 뒤의 팩토리얼의 값을 작은 값부터 차례대로 살펴볼 때 그 값이 \(m\)의 배수가 되는 순간 남은 항을 고려할 필요가 없어지기 때문이다.

글쓴이는 위의 저 식을 더 정리할 수 있다는 것을 놓쳐 처음에는 Extended Euclidean Algorithm을 활용해 문제를 지저분하게 풀었었다. 그런 것 필요 없이 위의 식의 각 항은 더 깔끔하게 정리할 수 있으므로 잘 정리해서 문제를 해결하자.

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

//derangement
//iktk님 풀이 보고 다시 풀기
#include <iostream>
using namespace std;
typedef long long ll;
typedef __int128 lll;

ll N, M;
lll ans, V = 1, sgn;

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

	cin >> N >> M;
	if (N & 1) sgn = -1;
	else sgn = 1;
	for (int i = 0; i <= N; i++) {
		if (!V) break;
		ans += V * sgn;
		V = V * (N - i) % M;
		sgn *= -1;
	}

	ans %= M;
	if (ans < 0) ans += M;
	
	cout << (ll)(ans * ans % M);
}

랜덤 마라톤 · 코스 7 - F번