취미로 코딩하기

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

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

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

주어진 원순열을 하나의 사이클로 구성된 그래프로 생각하자. 이 때 각각의 주어지는 세 점의 묶음은 어떤 한 정점과 그와 인접한 두 정점들로 이루어져 있으므로, 각 묶음에서 두 정점을 고르면 그래프상에서의 두 점 사이의 거리가 1 또는 2가 됨을 알 수 있다.

추가로, \(n\)이 4보다 큰 경우 각 묶음으로부터 얻을 수 있는 두 정점 선택의 쌍을 모두 모으면 거리가 1인 쌍은 두 번씩 등장하며 2인 쌍은 한 번씩 등장하게 됨을 관찰할 수 있다. 이를 이용하면 주어진 원순열을 구성하는 에지가 무엇인지를 map 등을 이용해 판별할 수 있고, 이를 이용해 문제를 해결할 수 있다.

\(n=3\)인 경우는 가능한 원순열이 한 종류밖에 없으므로 자명한 답을 보인다. 또한 \(n=4\)인 경우 네 수 가운데 하나씩 빠진 묶음 4개가 항상 등장해야 하므로 입력이 유일하고, 이 경우 또한 자명한 답을 보인다. (한편, 아래의 코드는 이 경우들에 대해서도 제대로 된 답을 도출한다.)

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

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

int N;
vector<int> G[200001];
map<pair<int, int>, int> mp;
bool visited[200001];

void dfs(int cur) {
	cout << cur << ' ';
	visited[cur] = 1;
	for (auto &nxt:G[cur]) {
		if (visited[nxt]) continue;
		dfs(nxt);
	}
}

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

	cin >> N;
	for (int k = 0; k < N; k++) {
		int x, y, z; cin >> x >> y >> z;
		mp[make_pair(min(x, y), max(x, y))]++;
		mp[make_pair(min(y, z), max(y, z))]++;
		mp[make_pair(min(z, x), max(z, x))]++;
	}

	for (auto &p:mp) {
		if (p.second > 1) G[p.first.first].emplace_back(p.first.second), G[p.first.second].emplace_back(p.first.first);
	}

	dfs(1);
}

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

이번에 볼 문제는 백준 1471번 문제인 사탕 돌리기이다.
문제는 아래 링크를 확인하자.

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

주어진 문제의 상황은 functional graph로 모델링되는데, 이러한 그래프는 어느 정점에서 출발하더라도 대응되는 사이클을 끝없이 돌게 된다.

따라서 주어진 그래프에서 사이클을 모두 찾고, 각 사이클로부터 사이클에 포함되지 않는 정점까지의 거리를 구하는 것으로 문제를 해결할 수 있다.

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

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

int N;
int G[200001];
vector<int> invG[200001];
int visited[200001];
int dist[200001];
queue<int> que;
int ans;

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

	cin >> N;
	for (int i = 1; i <= N; i++) {
		int ii = i, val = 0;
		while (ii) {
			val += ii % 10;
			ii /= 10;
		}
		int nxt = i + val;
		if (nxt > N) nxt -= N;
		G[i] = nxt;
		invG[nxt].emplace_back(i);
	}
	for (int i = 1; i <= N; i++) {
		if (visited[i]) continue;
		int ii = i;
		while (!visited[ii]) {
			visited[ii] = i;
			ii = G[ii];
		}
		if (visited[ii] == i) {
			int iii = ii, cnt = 1;
			while (G[iii] != ii) {
				iii = G[iii], cnt++;
			}
			iii = ii;
			dist[iii] = cnt;
			que.push(iii);
			while (G[iii] != ii) {
				iii = G[iii];
				dist[iii] = cnt;
				que.push(iii);
			}
		}
	}
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		ans = max(ans, dist[cur]);
		for (auto &x:invG[cur]) {
			if (dist[x]) continue;
			dist[x] = dist[cur] + 1;
			que.push(x);
		}
	}

	cout << ans;
}

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

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

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

어떤 같은 자릿수의 서로 다른 두 양의 정수 \(A\)와 \(B\)에 대하여 \(A\)를 일정 횟수 연속으로 이어붙여 얻은 수와 \(B\)를 연속으로 이어붙여 얻은 수의 사전순 대소는 \(A\)와 \(B\)의 사전순 대소를 따라가며, 크기의 경우 이어붙인 횟수를 따라감을 확인하자.

따라서, 서로 다른 \(n\)개의 세자리 수를 준비한 뒤 수열의 \(i\)번째 수를 준비한 수 중 \(i\)번째 수를 반복한 수를 적으면 주어진 수들이 사전순으로 나열됨을 알 수 있다. 이제 각 수를 적절히 반복시켜 자릿수를 늘리는 것으로 문제 조건에 맞게 대소관계를 설정해 문제를 해결하자.

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

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

int N;

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		string s = to_string(i + 100);
		int x; cin >> x;
		while (x--) cout << s;
		cout << ' ';
	}
}

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

이번에 볼 문제는 백준 27503번 문제인 요가 수업이다.
문제는 아래 링크를 확인하자.

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

주어진 조건으로부터, 꼭 지켜져야 하는 규칙들은 다음과 같이 요약할 수 있다:

(1) \(M\)개의 동작 중, 대응되는 대체 동작이 있는 동작은 원래 동작과 대체 동작 중 적어도 하나의 동작을 해야 한다.

(2) \(M\)개의 동작 중, 대응되는 대체 동작이 없는 동작은 무조건 해야 한다.

(3) \(K\)가지 쌍에 해당하는 동작들은 두 동작 중 적어도 하나의 동작을 하지 않아야 한다.

위와 같은 위의 내용을 CNF로 치환하면 이 문제는 2-SAT문제로 변환된다. 따라서 주어진 문제를 implication graph로 변환 후 SCC를 구해 모순이 발생하는지 확인하는 것으로 문제를 선형시간에 해결할 수 있다.

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

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

int N, M, C, K;
bool chk[500001];
vector<int> G[1000001];
int dfidx, dfi[1000001];
int scidx, sci[1000001];
vector<int> stk;

int dfs(int cur) {
	stk.emplace_back(cur);
	int ret = dfi[cur] = ++dfidx;
	for (auto &nxt : G[cur]) {
		if (sci[nxt]) continue;
		if (dfi[nxt]) ret = min(ret, dfi[nxt]);
		else ret = min(ret, dfs(nxt));
	}
	if (ret == dfi[cur]) {
		scidx++;
		while (stk.back() != cur) {
			sci[stk.back()] = scidx;
			stk.pop_back();
		}
		sci[stk.back()] = scidx;
		stk.pop_back();
	}
	return ret;
}

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

	cin >> N >> M >> C >> K;
	while (M--) {
		int x; cin >> x;
		chk[x] = 1;
	}
	while (C--) {
		int x, y; cin >> x >> y;
		G[x + 500000].emplace_back(y);
		G[y + 500000].emplace_back(x);
		chk[x] = chk[y] = 0;
	}
	while (K--) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y + 500000);
		G[y].emplace_back(x + 500000);
	}
	for (int i = 1; i <= N; i++) {
		if (chk[i]) G[i + 500000].emplace_back(i);
	}

	for (int i = 1; i <= N; i++) {
		if (!sci[i]) dfs(i);
		if (!sci[i + 500000]) dfs(i + 500000);
	}
	for (int i = 1; i <= N; i++) {
		if (sci[i] == sci[i + 500000]) {
			cout << "NO";
			return 0;
		}
	}

	cout << "YES";
}

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

이번에 볼 문제는 백준 12347번 문제인 한수 2이다.
문제는 아래 링크를 확인하자.

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

등차수열의 공차가 0이 아닌 한수는 길어봐야 10자리(9876543210)이고, 그 외의 한수는 한 가지 숫자가 반복되는 형태의 수밖에 없음을 관찰하자. 이 관찰을 이용하면 주어진 범위 내의 한수는 매우 적음을 발견할 수 있다.

따라서, \(10^{18}\) 이하의 모든 한수를 생성하여 그 수가 범위 내에 포함되는지 판단하는 것으로 문제를 해결할 수 있다.

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

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

ll N, ans;

void func(int x, int y) {
	int d = y - x;
	lll val = x * 10 + y;
	while (val <= N) {
		ans++;
		y += d;
		if (y < 0 || y > 9) break;
		val = val * 10 + y;
	}
}

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

	cin >> N;
	for (int i = 1; i < 10; i++) {
		if (i <= N) ans++;
		for (int j = 0; j < 10; j++) {
			func(i, j);
		}
	}
	cout << ans;
}

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

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

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

주어진 모든 수 가운데 주어진 순열의 현재 순서의 수보다 "앞서 나올 수 있는" 수의 개수를 빠르게 접근할 수 있다면 이 문제는 어렵지 않게 해결할 수 있을 것이다.

이와 같은 작업은 좌표압축과 세그먼트트리를 이용하여 할 수 있음이 잘 알려져 있지만, pbds(의 rbtree)를 이용하면 (pbds가 무거워서 실행속도는 조금 느리지만) 코드를 빠르게 작성할 수 있다. 이는 코드를 작성하는 속도 대결인 cp에서 유리한 점이라고 생각해 pbds에 익숙해질 겸 pbds로 문제를 해결해보았다.

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

#include <iostream>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename K> using ordered_set = tree<K, null_type, less<K>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;

int N;
int A[300000];
ordered_set<int> st;
int fact[300000];
int ans = 1;

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

	cin >> N;
	fact[0] = 1;
	for (int i = 1; i < N; i++) fact[i] = ((ll)fact[i - 1] * i) % 1000000007;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		st.insert(A[i]);
	}

	for (int i = 0; i < N; i++) {
		int ord = st.order_of_key(A[i]);
		ans = ((ll)ord * fact[N - i - 1] + ans) % 1000000007;
		st.erase(A[i]);
	}

	cout << ans;
}