취미로 코딩하기

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

이번에 볼 문제는 백준 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;
}

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

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

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

주어진 두 문자열의 첫 문자부터 i번째 문자까지의 두 부분문자열에 대하여 각 문자열까지의 거리가 \(k\)인 문자열의 개수를 각각 기억하고, 이를 \(i\)를 1씩 늘려나가는 방식의 dp로 문제를 해결하자.

두 문자열의 문자가 서로 일치하는 경우 구현에 다라 적절한 주의를 기울여야 함에 유의하자.

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

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

ll Q, N, D; char charend;
ll dp[201], tmp[201];
string s1, s2;

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

	cin >> Q >> N >> D; charend = '0' + Q;
	cin >> s1 >> s2;
	dp[0] = 1;
	for (int i = 0; i < N; i++) {
		memset(tmp, 0, sizeof(tmp));
		for (char c = '0'; c < charend; c++) {
			int val = 0;
			if (s1[i] != c) val++;
			if (s2[i] != c) val++;
			for (int k = val; k < 201; k++) tmp[k] += dp[k - val];
		}
		swap(dp, tmp);
	}

	cout << dp[D];
}

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

이번에 볼 문제는 백준 2115번 문제인 갤러리이다.
문제는 아래 링크를 확인하자.

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

대충 쓰면, 각 "일자벽"에 각각 최대한 많은 그림을 걸면 문제가 해결될 것임을 쉽게 알 수 있다. 이는 각각의 일자벽의 길이를 알면 계산할 수 있는데, 이 길이를 어떻게 편하게 계산할 수 있을까?

각 일자벽은 (흰칸, 회색칸)의 두 칸의 행방향 나열이 열방향으로 연속으로 있는 형태, 또는 (회색칸, 흰칸)의 같은 방식의 나열로 앞과 같은 방식으로 있는 형태, 또는 앞의 나열방식을 행과 열을 바꾼 형태의 총 네 가지 중 하나에 속한다. 이를 이용하면 아래의 코드와 같이 간단하게 갤러리의 각각의 일자벽의 길이에 한 번씩 접근해 문제를 편하게 해결할 수 있다.

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

#include <iostream>
using namespace std;

int R, C, ans;
char board[1000][1000];

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

	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 + 1 < R; r++) {
		int combo = 1;
		for (int c = 1; c < C; c++) {
			if (board[r][c - 1] == board[r][c] && board[r + 1][c - 1] == board[r + 1][c]) combo++;
			else {
				if (board[r][c - 1] != board[r + 1][c - 1]) ans += combo / 2;
				combo = 1;
			}
		}
	}
	for (int c = 0; c + 1 < C; c++) {
		int combo = 1;
		for (int r = 1; r < R; r++) {
			if (board[r - 1][c] == board[r][c] && board[r - 1][c + 1] == board[r][c + 1]) combo++;
			else {
				if (board[r - 1][c] != board[r - 1][c + 1]) ans += combo / 2;
				combo = 1;
			}
		}
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 30630번 문제인 직각삼각형의 동생은?이다.
문제는 아래 링크를 확인하자.

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

이 문제의 쿼리들은 입력으로 미리 모두 주어지므로, 주어지는 쿼리들을 임의의 순서대로 처리한 다음 입력으로 주어진 순서대로 그 답들을 출력하여 문제를 해결할 수 있다(오프라인 쿼리).

주어진 검은색 점들과 쿼리를 나타내는 점들을 "원점과 이은 반직선"과 \(x\)축이 이루는 각의 크기를 기준으로 정렬해 차례대로 하나씩 살펴보자(각도 기준 스위핑). 이 때 여러 점이 같은 각을 가진다면 검은색 점을 먼저 살펴보자. 검은색 점은 지금까지 살펴본 점들에 추가하고, 쿼리를 나타내는 점은 보일 때마다 지금까지 살펴본 점 중 \(x\)좌표가 자신 이하인 점의 개수를 답으로 계산하면 문제를 해결할 수 있을 것이다.

글쓴이는 위 과정을 구현하는 방법으로 pbds를 사용하였다. 좌표압축과 세그먼트트리를 활용한 구현 또한 가능하나, 주관적으로는 그 구현량이 적지 않고 간단한 편도 아니므로 pbds를 이용한 구현이 더 깔끔한 것 같다.

이 문제는 언젠가 대회에 나가면 활용할 생각으로 pbds 템플릿을 암기한 이래 처음으로 본격적인 문제 풀이에 활용해본 문제라 기억에 남을 것 같다.

pbds가 무엇인지는 링크를 참고하자.

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#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>;

bool comp(pair<pair<int, int>, int> &p1, pair<pair<int, int>, int> &p2) {
	ll val1 = (ll)p1.first.second * p2.first.first, val2 = (ll)p2.first.second * p1.first.first;
	if (val1 != val2) return val1 < val2;
	return p1.second < p2.second;
}
int N, M;
vector<pair<pair<int, int>, int>> Q;
ordered_set<pair<int, int>> st;
int ans[100001];

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

	cin >> N;
	while (N--) {
		int x, y; cin >> x >> y;
		Q.emplace_back(make_pair(make_pair(x, y), 0));
	}
	cin >> M;
	for (int m = 1; m <= M; m++) {
		int x, y; cin >> x >> y;
		Q.emplace_back(make_pair(make_pair(x, y), m));
	}
	sort(Q.begin(), Q.end(), comp);
	for (auto &p:Q) {
		if (p.second) ans[p.second] = st.order_of_key(make_pair(p.first.first + 1, -1));
		else st.insert(p.first);
	}

	for (int i = 1; i <= M; i++) cout << ans[i] << '\n';
}

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

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

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

주어진 각 격자의 칸은 두 대각선으로 잘라서 보았을 때 상하좌우의 삼각형모양의 네 칸으로 나눌 수 있다. 주어진 입력을 이와 같이 나눈 격자로 읽어 그래프로 모델링하면 주어진 문제는 그래프에서의 connected component의 개수를 세는 문제로 어렵지 않게 변환하여 문제를 해결하자.

그래프로 모델링할 때, 원래 격자에서의 인접한 칸 사이의 연결관계와 각 칸 내부에 생성된 삼각형들 사이의 연결관계를 모두 고려해야 함에 유의하자.

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

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

int R, C;
bool board[1000][1000][4];
int dr[4] = {0,0,1,-1};
int dc[4] = {1,-1,0,0};
queue<int> que;

void bfs(int sR, int sC, int sD) {
	board[sR][sC][sD] = 0;
	que.push(sR * 1000000 + sC * 1000 + sD);
	while (!que.empty()) {
		int r = que.front() / 1000000, c = que.front() % 1000000 / 1000, d = que.front() % 1000; que.pop();
		for (int dd = 0; dd < 4; dd++) {
			if ((dd ^ d) & 2) {
				if (board[r][c][dd]) {
					board[r][c][dd] = 0;
					que.push(r * 1000000 + c * 1000 + dd);
				}
			}
		}
		int rr = r + dr[d], cc = c + dc[d], dd = d ^ 1;
		if (rr > -1 && rr < R && cc > -1 && cc < C && board[rr][cc][dd]) {
			board[rr][cc][dd] = 0;
			que.push(rr * 1000000 + cc * 1000 + dd);
		}
	}
}

void solve() {
	cin >> R >> C;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			char x; cin >> x;
			if (x == 'A');
			else if (x == 'B') board[r][c][2] = 1, board[r][c][1] = 1;
			else if (x == 'C') board[r][c][3] = 1, board[r][c][1] = 1;
			else if (x == 'D') board[r][c][3] = 1, board[r][c][0] = 1;
			else if (x == 'E') board[r][c][2] = 1, board[r][c][0] = 1;
			else board[r][c][3] = 1, board[r][c][2] = 1, board[r][c][1] = 1, board[r][c][0] = 1;
		}
	}
	int ans = 0;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			for (int i = 0; i < 4; i++) {
				if (board[r][c][i]) {
					bfs(r, c, i);
					ans++;
					break;
				}
			}
		}
	}
	cout << ans << '\n';
}

int T;

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

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