Processing math: 100%
본문 바로가기

프로그래밍 대회 풀이/Atcoder

Atcoder Beginner Contest 205 (ABC 205) 풀이

반응형

 

오랜만에 참가한 ABC인데, 마침 오랜만에 ABC 문제들이 괜찮아서 풀이를 작성해보려고 한다. 결과도 나쁘지 않았다. 

 

문제 링크 : https://atcoder.jp/contests/abc205/tasks

공식 해설 : https://atcoder.jp/contests/abc205/editorial

 

(*) = 난이도

 

A. Kcal (*6)

 

단순 계산 문제이다. 100ml당 A kcal을 얻을 수 있을 때 Bml이 있으면 몇 kcal를 얻을 수 있는지를 구하면 된다.

 

#include<bits/stdc++.h>
using namespace std;
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	double a, b; cin >> a >> b;
	cout << fixed;
	cout.precision(10);
	cout << a * (b / 100);
}

 

B. Permutation check (*16)

 

N개의 원소로 이루어진 수열이 주어질 때, 이 수열이 Permutation인지를 판단해야 한다. 

오름차순으로 정렬하고, 모든 i에 대해 A[i] = i인지만 체크하면 된다.

 

#include<bits/stdc++.h>
using namespace std;

int a[1010];
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int n; cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	sort(a + 1, a + 1 + n);
	for (int i = 1; i <= n; i++) {
		if (a[i] != i) {
			return cout << "No", 0;
		}
	}
	cout << "Yes";
}

 

C. POW (*63)

 

A,B,C가 주어질 때, ACBC를 대소 비교하는 문제이다. A와 B가 음수인지 양수인지에 따라 케이스 분류를 해주면 된다. 

 

#include<bits/stdc++.h>

using namespace std;
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int a, b, c; cin >> a >> b >> c;
	if (c % 2 == 0 || (a >= 0 && b >= 0)) {
		if (abs(a) > abs(b)) cout << '>';
		else if (abs(a) < abs(b)) cout << '<';
		else cout << '=';
	}
	else {
		if (a < 0 && b >= 0) cout << '<';
		else if (a >= 0 && b < 0) cout << '>';
		else {
			if (abs(a) > abs(b)) cout << '<';
			else if (abs(a) < abs(b))cout << '>';
			else cout << '=';
		}
	}

}

 

 

D. Kth Excluded (*713)

 

N개의 원소로 이루어진 수열 A가 주어지고, Q개의 쿼리가 주어지는데, 각 쿼리마다 A에 포함된 원소를 제외한 양의 정수 중에서 K번째로 작은 수를 구하는 문제이다. K번째로 작은 수를 ans라고 하자. 

수열 A의 원소와 K의 범위가 1018이므로, 나이브하게 구할 수는 없다. 

 

먼저 K이하인 A의 원소가 존재하지 않는다면 ans = K이다. 하지만 만약 K이하인 A의 원소가 r개 있다면 적어도 ans >= K + r이다. 

이때, K+1 ~ K+r 범위인 A의 원소가 또 존재한다면 그만큼 다시 ans를 증가시켜줘야 하며, 이 과정을 ans가 증가하지 않을 때까지 반복해주어야 한다. 

 

이를 이분탐색으로 계속 확인하면서 이전보다 포함되는 A의 원소의 개수가 증가했는지를 판단하여 증가하지 않으면 현재 값이 답이 된다. 

 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

ll a[101010];
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int n, q; cin >> n >> q;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= q; i++) {
		ll k; cin >> k;
		int prv = 0;
		while (1) {
			int cnt = upper_bound(a + 1, a + 1 + n, k) - a - 1;
			if (cnt != prv) {
				k += cnt - prv;
				prv = cnt;
			}
			else {
				cout << k << '\n';
				break;
			}
		}
	}
}

 

 

E. White and Black Balls (*2025) 

 

N개의 흰 공과 M개의 검은 공을 일렬로 배치하는 경우의 수 중, 1부터 N+M까지의 모든 i에 대해서 [1, i]에 있는 흰 공의 개수 w와 검은 공의 개수 b에 대해서 w ≤ b + K를 만족하는 경우의 수를 구하는 문제이다. 

 

디스크립션은 간단하다. 

대회 중에 해결하지 못한 문제이다. 해설을 보고 나서야 웰논인 문제임을 깨달았다. K가 0이라면 올바른 괄호 문자열의 개수를 구할 때 사용하는 카탈란 수와 관련된 문제와 매우 유사하다.

언뜻 보면 dp스럽지만 N과 M이 100만이라 dp가 잘 떠오르지 않았다. 아마 안되지 않을까 싶다...

 

이 문제를 2차원 좌표평면상으로 가져와보자. 흰 공을 y축, 검은 공을 x축이라고 생각하면, N개의 흰 공과 M개의 검은 공을 일렬로 배열하는 경우의 수는 가로/세로로 1칸씩 이동할 수 있다고 할 때, (0, 0)에서 (M, N)으로 가는 경우의 수와 동일하다. 

가로/세로로 1칸 이동하는 것을 검은/흰 공을 1개 이어 붙이는 것과 동일하게 생각할 수 있다. 

그러면 조건을 만족하지 않는 경우는 언제일까? 

 

위의 그림에서 (0, 0)에서 (M, N)으로 이동하는 과정에서 한번이라도 y = x + K 직선 위로 올라가는 경우는 조건을 만족하지 않는 경우이다. y > x + K 즉, w > b + K인 경우이기 때문이다. 

이는 반드시 y = x + K+1를 한번 이상은 만난다는 의미가 된다. 

 

위 그림과 같이 (0, 0)을 y = x + K+1에 대해 점대칭을 시킨 (-K-1, K+1)를 생각해보자. (-K-1, K+1)에서 (M, N)으로 가는 경로는 반드시 y = x + K+1와 만나게 되며, 그 교점을 P라고 하면 (0, 0) ~ P의 경우의 수와 (-K-1, K+1) ~ P의 경우의 수가 동일하다. 

따라서, 조건을 만족하지 않는 경우의 수는 (-K-1, K+1)에서 (M, N)으로 가는 경우의 수와 동일하다. 

 

N > M + K인 경우에는 항상 0인 점을 주의하자.

 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = (int)1e9 + 7;

#define MN 2000000
ll fac[MN + 10], facinv[MN + 10];
ll mpow(ll a, ll x) {
	ll res = 1;
	while (x > 0) {
		if (x % 2) res = (res*a) % MOD;
		a = (a*a) % MOD;
		x /= 2;
	}
	return res;
}
void fac_init() {
	fac[0] = 1;
	for (int i = 1; i <= MN; i++) fac[i] = fac[i - 1] * i % MOD;
	facinv[MN] = mpow(fac[MN], MOD - 2);
	for (int i = MN - 1; i >= 0; i--) facinv[i] = facinv[i + 1] * (i + 1) % MOD;
}
ll C(ll n, ll r) {
	return ((fac[n] * facinv[r]) % MOD) * facinv[n - r] % MOD;
}
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	fac_init();
	int n, m, k; cin >> n >> m >> k;
	if (n > m + k) cout << 0;
	else cout << (MOD + C(n + m, n) - C(n + m, m + k + 1)) % MOD;
}

 

 

F. Grid and Tokens (*2088)

 

H x W 격자판이 있고, N개의 블록을 격자판에 놓으려고 한다. (H, W, N≤100)

2가지 조건이 있는데, 각 블럭은 각자 주어진 A, B, C, D 값에 따라 (A, C)를 왼쪽 위, (B, D)를 오른쪽 아래 꼭짓점으로 하는 직사각형의 범위에만 놓을 수 있으며 같은 행과 열에는 2개 이상의 블록을 놓을 수 없다. 

이때, 놓을 수 있는 블럭의 최대 개수를 구하는 문제이다. 

 

이 문제는 최대유량 알고리즘으로 해결할 수 있다. 먼저 A, B, C, D 조건이 없이, 같은 행과 열에 2개 이상 놓을 수 없다는 조건만으로 그래프 모델링을 해보자. 

같은 행에 2개 이상 놓을 수 없으므로, 소스(S)에서 각 행별로 용량이 1인 간선을 연결해주면 같은 행에 2개 이상 들어가지 않는다. 

그다음, 각 행에서 모든 열로 용량이 1인 간선을 연결해주고, 각 열 별로 싱크(T)로 용량이 1인 간선을 연결해주면, 같은 열에 2개 이상 들어갈 수 없으면서 행과 열을 연결하면 블록이 들어갈 위치가 정해지게 된다. 

즉, 다음과 같은 형태로 이루어진다. 

 

그런데 여기에 조건이 하나 추가된다. 

각 블럭별로 놓을 수 있는 범위가 주어지기 때문에, 각 블록별로 가능한 행과 열이 제한된다. 

따라서, 블럭도 함께 그래프 모델링을 해줘야 한다. 

행과 열 사이에 블럭을 넣고, 각 블록별로 가능한 행과 열에 모두 연결을 해주면 행과 열이 매칭 되는 것이 블록을 (행, 열)에 놓는 것과 동일하다. 

다만, 블럭은 한 번만 사용될 수 있으므로 정점 분할을 통해서 블록이 여러 번 사용되는 것을 방지해준다. 

 

 

 

#include<bits/stdc++.h>
using namespace std;
const int MAX = (int)2e9;

#define MAX_V 510
int S, T;
struct Dinic {
	struct edge {
		int v, c, rev;
		edge(int v, int c, int rev) : v(v), c(c), rev(rev) {}
	};
	int n;
	vector<vector<edge>> adj;
	vector<int> level, see;
	Dinic(int n) : n(n) {
		adj.assign(n + 1, vector<edge>());
		level.assign(n + 1, -1);
		see.assign(n + 1, 0);
	}
	void addedge(int u, int v, int capa) {
		adj[u].push_back({ v, capa, (int)adj[v].size() });
		adj[v].push_back({ u, 0, (int)adj[u].size() - 1 });
	}
	bool bfs() {
		level.assign(n + 1, -1);
		queue<int> q;
		level[S] = 0;
		q.push(S);
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (auto i : adj[u]) {
				if (level[i.v] == -1 && i.c > 0) {
					level[i.v] = level[u] + 1;
					q.push(i.v);
				}
			}
		}
		return level[T] != -1;
	}
	int dfs(int u, int flow) {
		if (u == T) return flow;
		for (; see[u] < (int)adj[u].size(); see[u]++) {
			auto i = adj[u][see[u]];
			if (level[i.v] == level[u] + 1 && i.c > 0) {
				int now = dfs(i.v, min(flow, i.c));
				if (now > 0) {
					adj[u][see[u]].c -= now;
					adj[i.v][adj[u][see[u]].rev].c += now;
					return now;
				}
			}
		}
		return 0;
	}
	int solve() {
		int ret = 0;
		while (bfs()) {
			see.assign(n + 1, 0);
			while (1) {
				int flow = dfs(S, MAX);
				if (!flow) break;
				ret += flow;
			}
		}
		return ret;
	}
};
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int h, w, n; cin >> h >> w >> n;
	S = 0;
	T = 501;
	Dinic dc = Dinic(MAX_V);
	//S = 0, 행 : 1 ~ 100, piece = 101~200, 201~300, 열 : 301~400, T = 501
	for (int i = 1; i <= h; i++) dc.addedge(S, i, 1);
	for (int i = 1; i <= w; i++) dc.addedge(300+i, T, 1);
	for (int i = 1; i <= n; i++) {
		dc.addedge(100 + i, 200 + i, 1);
		int a, b, c, d; cin >> a >> b >> c >> d;
		for (int j = a; j <= c; j++) {
			dc.addedge(j, 100 + i, 1);
		}
		for (int j = b; j <= d; j++) {
			dc.addedge(200 + i, 300 + j, 1);
		}
	}
	cout << dc.solve();
}
반응형