취미로 코딩하기

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

이번에 볼 문제는 백준 14595번 문제인 동방 프로젝트 (Large)이다.
문제는 아래 링크를 확인하자.

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

imos법을 이용하면 각 벽에 대하여 해당 벽을 포함하는 구간의 개수를 총 \(O(N+M)\)에 구할 수 있다.

위와 같은 정보를 먼저 구하면, 각 벽에 대하여 해당 구간을 포함하는 구간이 있는지의 여부를 이용해 건물에 남은 벽의 개수를 구하고 이를 통해 답을 구할 수 있다.

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

#include <iostream>
using namespace std;

int N, K;
int A[1000001];
int ans;

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

    cin >> N >> K;
    while (K--) {
        int L, R; cin >> L >> R;
        A[L]++, A[R]--;
    }
    for (int i = 1; i <= N; i++) {
        A[i] += A[i - 1];
        if (!A[i]) ans++;
    }
    cout << ans;
}

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

이번에 볼 문제는 백준 28851번 문제인 Протокол <<Судного дня>>이다.
문제는 아래 링크를 확인하자.

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

\(s_i\)와 \(k_i\)로 이루어진 쿼리는 лондонского метро는 1번 역에서 멀어지는 방향으로 무제한으로 사용 가능하고 секретными тоннелями Кингсман는 (1번 역과 가까워지는 방향으로) 총 \(k\)번 이용 가능할 때 \(s_i\)로부터 이동할 수 있는 1번 역과의 가장 가까운 거리를 구하는 문제이다.

주어진 조건에 따라 1을 루트로 갖고 лондонского метро들을 에지로 갖는 트리의 \(s\)번 역에서 секретными тоннелями Кингсман를 이용해 1과 거리가 \(x\)(단, 1번 역과의 거리는 \(s\)번 역과의 거리보다 짧거나 같아야 한다.)인 역으로 이동할 경우 그 역이 특정(구체적으로, 1과 \(s\)를 잇는 (최단)경로 위의 역)됨을 확인하자. 따라서, 각 노드별로 1을 루트로 갖고 лондонского метро들을 에지로 갖는 트리 기준의 서브트리에서 이동할 수 있는 가장 1번 역과 가까운 역은 유일하게 결정된다. 모든 역에 대한 이러한 역은 DP를 이용해 \(O(N+M)\)에 전부 구할 수 있다.

위와 같은 이동을 \(k\)번 할 때 도착할 수 있는 1번 역과의 가장 가까운 거리 쿼리는 위의 정보를 이용한 sparse table을 미리 만들어 두면 각각 빠르게 처리할 수 있다.

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

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

int N, M;
vector<int> G[200001];
vector<int> GG[200001];

int lv[200001];
int table[18][200001];

void tableinit() {
	for (int k = 1; k < 18; k++) {
		for (int i = 1; i <= N; i++) {
			table[k][i] = table[k - 1][table[k - 1][i]];
		}
	}
}

int dfs(int cur) {
	int ret = cur;
	for (auto &nxt : G[cur]) {
		if (lv[nxt]) continue;
		lv[nxt] = lv[cur] + 1;
		int tmp = dfs(nxt);
		if (lv[tmp] < lv[ret]) ret = tmp;
	}
	for (auto &prv : GG[cur]) {
		if (lv[prv] < lv[ret]) ret = prv;
	}
	table[0][cur] = ret;
	return ret;
}

int Q;

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

	cin >> N;
	for (int i = 1; i < N; i++) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y);
		G[y].emplace_back(x);
	}
	cin >> M;
	while (M--) {
		int x, y; cin >> x >> y;
		GG[x].emplace_back(y);
	}

	lv[1] = 1;
	dfs(1);
	tableinit();
	cin >> Q;
	while (Q--) {
		int x, K; cin >> x >> K;
		for (int k = 0; k < 18; k++) {
			if (K & 1) x = table[k][x];
			K >>= 1;
		}
		cout << x << '\n';
	}
}

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

이번에 볼 문제는 백준 11968번 문제인 High Card Wins이다.
문제는 아래 링크를 확인하자.

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

먼저, 주어진 수들을 읽어 입력으로 주어지지 않은 \(N\)개의 수가 Bessie가 가진 카드에 적힌 수임을 이용해 두 Bessie와 Elsie가 가진 각 카드의 수를 구하자. 또한 Elsie가 어떤 순서로 카드를 내더라도 그에 대응하는 카드를 맞춰 내면 경기의 결과를 변하지 않게 할 수 있으므로 Elsie의 카드 내는 순서는 중요하지 않음을 관찰하자. 아래에서는 Elsie가 자신이 가진 카드 중 작은 수부터 제출하는 경우를 생각할 것이다.

Elsie가 낸 두 카드 \(e_1\)와 \(e_2\), Bessie가 그에 맞춰서 낸 두 카드 \(b_1\), \(b_2\)에 대하여 \(e_1 < e_2\), \(e_1<b_1\), \(e_2<b_2\)가 성립한다고 가정해보자. 이 때 \(b_1>b_2\)가 성립한다면 \(e_1<b_2\), \(e_2<b_1\) 또한 성립함을 관찰하자. 이를 이용하면 어떤 Elsie의 카드의 집합에 대하여 그에 Bessie가 가진 카드의 같은 크기의 부분집합으로 대응되는 Bessie가 모두 이기는 대응이 존재한다면 그 대응을 \(e\)와 \(b\)의 크기순 대응으로도 얻을 수 있음을 알 수 있다.

위에서 알아낸 내용을 이용하면, Elsie의 카드를 작은 값이 적힌 카드부터 살피며 그보다 큰 수 중 가장 작은 수가 적힌 Bessie의 카드를 대응시키는 greedy한 전략으로 Bessie가 얻을 수 있는 최대 점수를 계산할 수 있음을 증명할 수 있다.

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

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

int N;
bool A[100001];
priority_queue<int, vector<int>, greater<>> pq1, pq2;
int ans;

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		A[x] = 1;
	}
	for (int i = 1; i <= N * 2; i++) {
		if (A[i]) pq2.push(i);
		else pq1.push(i);
	}
	while (!pq1.empty()) {
		if (pq1.top() > pq2.top()) ans++, pq1.pop(), pq2.pop();
		else pq1.pop();
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 18866번 문제인 젊은 날의 생이여이다.
문제는 아래 링크를 확인하자.

https://www.acmcipc.net/problem/18866

첫 번째 날부터 \(k\)번째 날까지의 행복도의 최솟값이 \(k+1\)번째 날부터 \(N\)번째 날까지의 행복도의 최댓값보다 크고, 첫 번째 날부터 \(k\)번째 날까지의 피로도의 최댓값이 \(k+1\)번째 날부터 \(N\)번째 날까지의 피로도의 최솟값보다 작은 \(k\)의 값 중 가장 큰 값을 구하는 문제이다.

\(k\) 이하의 날의 행복도의 최솟값 및 피로도의 최댓값은 prefix min/max를 이용해 \(O(N)\)에 계산가능함을 관찰하자. 이는 \(k\) 이상의 날의 행복도의 최댓값 및 피로도의 최솟값에도 똑같이 적용할 수 있다.

따라서 위와 같은 전처리 후 각 \(k\)에 대하여 \(k\)번째 날이 젊은 날과 늙은 날을 구분하는 기준이 될 수 있는지를 각각 \(O(1)\)에 판정해 문제를 해결할 수 있다.

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

#include <iostream>
using namespace std;

int N;
int H[1000002], F[1000002];
int LH[1000002], RH[1000002], LF[1000002], RF[1000002];
int ans = -1;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for (int i = 1; i <= N; i++) cin >> H[i] >> F[i];
    LH[0] = 1000000007;
    for (int i = 1; i <= N; i++) {
        if (!H[i]) LH[i] = LH[i - 1];
        else LH[i] = min(LH[i - 1], H[i]);
    }
    for (int i = N; i > 0; i--) {
        if (!H[i]) RH[i] = RH[i + 1];
        else RH[i] = max(RH[i + 1], H[i]);
    }
    for (int i = 1; i <= N; i++) {
        if (!F[i]) LF[i] = LF[i - 1];
        else LF[i] = max(LF[i - 1], F[i]);
    }
    RF[N + 1] = 1000000007;
    for (int i = N; i > 0; i--) {
        if (!F[i]) RF[i] = RF[i + 1];
        else RF[i] = min(RF[i + 1], F[i]);
    }
    for (int i = 1; i < N; i++) {
        if (LH[i] > RH[i + 1] && LF[i] < RF[i + 1]) ans = i;
    }

    cout << ans;
}

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

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

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

어떤 싱글의 Download Top N차트보다 Single Top N차트의 등수가 더 높다는 것은 이 싱글은 CD Single의 형태로도 구할 수 있음을 지문으로부터 알 수 있다.

이를 이용하면, 각 Download Top N 차트의 \(i\)위 싱글에 대하여 Download Top N 차트의 \(i\)보다 작은 등수의 모든 곡들이 Single Top N 차트에서 더 위에 있는 것은 아니라면 이 싱글은 CD Single의 형태로도 구할 수 있음을 확신할 수 있다.

이 점을 활용해 문제를 해결하자. 구간합 segment tree를 활용하면 위 정보를 간단하게 확인할 수 있다.

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

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

int N;
int seg[262145];
void upd(int qI) {
	int L = 1, R = N, sI = 1;
	while (L < R) {
		seg[sI]++;
		int mid = (L + R) / 2;
		if (mid < qI) L = mid + 1, sI = sI * 2 + 1;
		else R = mid, sI = sI * 2;
	}
	seg[sI]++;
}
int qry(int L, int R, int qL, int qR, int sI) {
	if (R < qL || qR < L)return 0;
	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);
}

vector<int> ans;
void solve() {
	memset(seg, 0, sizeof(seg));
	ans.clear();
	cin >> N;
	for (int i = 1; i <= N; i++) {
		int x; cin >> x;
		if (x > 1 && qry(1, N, 1, x - 1, 1) < x - 1) ans.emplace_back(x);
		upd(x);
	}
	sort(ans.begin(), ans.end());
	cout << ans.size() << '\n';
	for (auto &x : ans) cout << x << '\n';
}

int T;

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

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

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

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

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

조건에 따르면, (1)주어지는 바이러스 진원지 및 (2) 진원지와 직접적으로 인접한 도시들에 ITAI Virus가 퍼지게 됨을 알 수 있다.

각 도시와 연결된 도시가 어디인지를 인접행렬 또는 인접리스트의 형태로 저장하고 주어진 조건을 만족하는지 체크하는 배열을 활용하면 문제가 요구하는 값을 충분히 빠르게 계산할 수 있다.

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

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

int N, M, K;
vector<int> G[1001];
int A[1001];

void solve() {
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) G[i].clear();
	while (M--) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y);
		G[y].emplace_back(x);
	}
	memset(A, 0, sizeof(A));
	while (K--) {
		int x; cin >> x;
		A[x] = 1;
		for (auto &y : G[x]) A[y] = 1;
	}
	int ans = 0;
	for (int i = 1; i <= N; i++) ans += A[i];
	cout << ans << '\n';
}

int T;

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

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