취미로 코딩하기

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

이번에 볼 문제는 백준 32685번 문제인 4-LSB이다.
문제는 아래 링크를 확인하자.

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

어떤 자료의 마지막 4-LSB는 이진수 1111(십진수로는 15가 된다)을 and하여 빠르게 구할 수 있다.

이를 이용해 각 수의 4-LSB를 계산하여 문제의 답을 구하자.

leading zero의 개수를 적절히 채워야 함에 유의하자.

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

#include <iostream>
using namespace std;

int A, B, C;
int ans;

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

	cin >> A >> B >> C;
	ans = (A & 15) * 256 + (B & 15) * 16 + (C & 15);
	if (ans < 1000) cout << 0;
	if (ans < 100) cout << 0;
	if (ans < 10) cout << 0;
	cout << ans;
}

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

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

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

Juta가 문제에서 주어진 제한대로 움직이면 세 수 중 첫 번째 수는 1 또는 3, 두 번째 수는 6 또는 8, 세 번째 수는 2 또는 5여야 한다.

각 세 수를 비교하여 하나에서라도 그 외의 수가 주어진다면 "EI"를, 그렇지 않다면 "JAH"를 출력해 문제를 해결하자.

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

#include <iostream>
using namespace std;

int N;

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

	cin >> N;
	if (N != 1 && N != 3) {
		cout << "EI";
		return 0;
	}
	cin >> N;
	if (N != 6 && N != 8) {
		cout << "EI";
		return 0;
	}
	cin >> N;
	if (N != 2 && N != 5) {
		cout << "EI";
		return 0;
	}
	cout << "JAH";
}

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

이번에 볼 문제는 백준 32674번 문제인 Palindromic Word Search이다.
문제는 아래 링크를 확인하자.

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

직사각형 영역의 임의의 행과 열을 하나씩 고르면 고른 행과 열에 공통으로 속한 칸이 항상 존재한다. (좌표의 원리를 생각하자.) 따라서, 임의의 직사각형 영역에 문제의 조건을 만족하는 행방향의 팰린드롬과 열방향의 팰린드롬이 하나씩 있다면 그 둘을 모두 포함하는 어떤 칸이 항상 존재한다.

따라서 이 문제는 각 칸을 지나는 행방향 팰린드롬의 길이의 최댓값과 열방향 팰린드롬의 길이의 최댓값을 모두 구해 각 칸을 교점으로 하는 직사각형의 넓이의 최댓값을 구하는 것으로 해결할 수 있다.

하나의 행 또는 열에 대하여, 각 문자(또는 두 문자 사이)를 중심으로 하는 팰린드롬의 길이의 최댓값은 manacher 알고리즘 등을 이용해 빠르게 구할 수 있고, sweeping을 통해 각 행 또는 열의 칸에 대하여 그 칸을 포함하는 해당 방향 팰린드롬의 길이의 최댓값을 구해낼 수 있다.

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

// 찾는 사각형은 공통된 칸이 있고,
// 해당 칸 포함 가로 팰린드롬 최대 길이와 세로 팰린드롬 최대 길이를 각각 전처리해서
// 모든 칸에 대해 계산 시도
#include <iostream>
#include <queue>
using namespace std;

int R, C, ans;
char board[500][500];
int valR[500][500], valC[500][500];
string s;
int dp[1001];

void manacher(string& S) {
	int N = S.length();
	priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, greater<>> pq1;
	pq1.push(make_pair(make_pair(0, 0), 0));
	dp[0] = 0;
	for (int c = 0, i = 1; i < N; i++) {
		if (i <= c + dp[c]) dp[i] = min(dp[c - (i - c)], (c + dp[c]) - i);
		else dp[i] = 0;
		while (-1 < i - dp[i] - 1 && i + dp[i] + 1 < N && S[i - dp[i] - 1] == S[i + dp[i] + 1]) dp[i]++;
		if (c + dp[c] < i + dp[i]) c = i;
		pq1.push(make_pair(make_pair(i - dp[i], i + dp[i]), dp[i]));
	}
	priority_queue<pair<int, int>> pq2;
	for (int i = 0; i < N; i++) {
		while (!pq1.empty() && pq1.top().first.first == i) {
			pq2.push(make_pair(pq1.top().second, pq1.top().first.second));
			pq1.pop();
		}
		while (pq2.top().second < i) pq2.pop();
		dp[i] = pq2.top().first;
	}
}

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

	s.reserve(1001);
	cin >> R >> C;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			cin >> board[r][c];
		}
	}

	for (int r = 0; r < R; r++) {
		s.clear();
		s += '#';
		for (int c = 0; c < C; c++) {
			s += board[r][c];
			s += '#';
		}
		manacher(s);
		for (int c = 0; c < C; c++) valR[r][c] = dp[c * 2 + 1];
	}

	for (int c = 0; c < C; c++) {
		s.clear();
		s += '#';
		for (int r = 0; r < R; r++) {
			s += board[r][c];
			s += '#';
		}
		manacher(s);
		for (int r = 0; r < R; r++) valC[r][c] = dp[r * 2 + 1];
	}

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			ans = max(ans, valR[r][c] * valC[r][c]);
		}
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 32628번 문제인 두 스택이다.
문제는 아래 링크를 확인하자.

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

위에서부터 총 \(K\)개의 물건을 들어 없애는 방법의 수는 한 스택에서 0, 1, \(\cdots\), \(K\)개의 물건을 들어내고 다른 스택에서 \(K\), \(K-1\), \(\cdots\), 1, 0개의 물건을 들어내는 방법 중 실제로 실현이 가능한 것(각 스택에서 들어내는 물건의 개수가 \(N\) 이하인 것)의 수와 같다. 이는 최대 \(K+1\)가지이다.

따라서 prefix sum으로 각 스택의 밑에서부터의 물건의 수를 미리 전처리해 두고 최대 \(K+1\)가지의 모든 경우에 대하여 원빈이가 들어야하는 물건의 값을 각각 조사해 그 중 최솟값을 구하는 것으로 문제를 선형시간에 해결할 수 있다.

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

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

int N, K; ll ans = 2000000000000000007LL;
ll A[100001], B[100001];

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

	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		A[i] += A[i - 1];
	}
	for (int i = 1; i <= N; i++) {
		cin >> B[i];
		B[i] += B[i - 1];
	}

	for (int i = 0; i <= N; i++) {
		int j = (N * 2 - K) - i;
		if (j < 0 || j > N) continue;
		ans = min(ans, max(A[i], B[j]));
	}
	cout << ans;
}

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

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

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

모든 기둥의 반지름이 동일하므로, 구하고자 하는 벽의 모양은 주어진 기둥의 중심을 모두 포함하는 최소볼록다각형(convex hull)으로부터 도형의 바깥쪽으로 \(R\)만큼 떨어진 점들을 모두 포함하는 모양을 이루게 된다.

위 도형의 둘레의 직선부는 convex hull의 길이와 같고 곡선부는 모두 합치면 반지름이 \(R\)인 원의 둘레가 됨을 관찰하자.

이를 이용하면 convex hull을 구해 각 변의 길이와 원의 둘레의 길이를 합하는 것으로 문제의 답을 구할 수 있다.

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;

ll CCW(pll p1, pll p2, pll p3) {
	return p1.first * p2.second + p2.first * p3.second + p3.first * p1.second
	-p1.second * p2.first - p2.second * p3.first - p3.second * p1.first;
}

int N, R;
pll P[1000];
int usize, lsize;
vector<pll> uhull, lhull;

void chull() {
	for (int i = 0; i < N; i++) {
		while (uhull.size() > 1) {
			if (CCW(uhull[uhull.size() - 2], uhull.back(), P[i]) <= 0) uhull.pop_back();
			else break;
		}
		uhull.emplace_back(P[i]);
	}
	for (int i = 0; i < N; i++) {
		while (lhull.size() > 1) {
			if (CCW(lhull[lhull.size() - 2], lhull.back(), P[i]) >= 0) lhull.pop_back();
			else break;
		}
		lhull.emplace_back(P[i]);
	}
}

ld ans;

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

	cin >> N >> R;
	for (int i = 0; i < N; i++) cin >> P[i].first >> P[i].second;
	sort(P, P + N);
	chull();

	usize = uhull.size();
	for (int i = 0; i + 1 < usize; i++) ans += hypot((ld)(uhull[i + 1].first - uhull[i].first), (ld)(uhull[i + 1].second - uhull[i].second));
	lsize = lhull.size();
	for (int i = 0; i + 1 < lsize; i++) ans += hypot((ld)(lhull[i + 1].first - lhull[i].first), (ld)(lhull[i + 1].second - lhull[i].second));
	ans += acos((ld)-1) * R * 2;

	cout << fixed;
	cout.precision(12);
	cout << ans;
}

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

이번에 볼 문제는 백준 11583번 문제인 인경호의 징검다리이다.
문제는 아래 링크를 확인하자.

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

어떤 양의 정수의 trailing zero의 개수는 주어진 수가 10을 얼마나 많이 소인수로 가지고 있는지와 같다. 이는 그 수의 2와 5 각각의 개수의 최솟값과 같다.

따라서 문제에서 주어진 과정으로 얻을 수 있는 수 가운데 trailing zero의 개수가 최소인 수 중에는 2의 개수가 가장 적게 들어있거나 5의 개수가 가장 적게 들어있는 수가 있음을 관찰할 수 있다.

따라서 가능한 2를 가장 적게 포함하는 수와 5를 가장 적게 포함하는 수의 2와 5의 개수를 각각 구해 문제를 해결할 수 있다.

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

#include <iostream>
using namespace std;

int N, K;
int A[200001], B[200001];

void solve() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		int cnt2 = 0, cnt5 = 0;
		while (x % 2 == 0) {
			x /= 2, cnt2++;
		}
		A[i] = 0x3f3f3f3f;
		for (int k = max(0, i - K); k < i; k++) {
			A[i] = min(A[i], A[k]);
		}
		if (A[i] == 0x3f3f3f3f) A[i] = 0;
		A[i] += cnt2;
		while (x % 5 == 0) {
			x /= 5, cnt5++;
		}
		B[i] = 0x3f3f3f3f;
		for (int k = max(0, i - K); k < i; k++) {
			B[i] = min(B[i], B[k]);
		}
		if (B[i] == 0x3f3f3f3f) B[i] = 0;
		B[i] += cnt5;
	}
	cout << min(A[N - 1], B[N - 1]) << '\n';
}

int T;

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

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