AtCoder ABC 239 풀이

https://atcoder.jp/contests/abc239/tasks

Tasks - Denso Create Programming Contest 2022(AtCoder Beginner Contest 239)

 

 

A. 

구하라는 값을 출력해주면 됩니다. long long을 써줍시다.

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

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	ll x; cin >> x;
	cout << fixed << setprecision(10);
	cout << sqrt(x * (12800000 + x));
}

 

 

 

B.

내림함수 x//10을 구하는 문제입니다.

만약 10의 배수가 아니고 음수일때만 x/10-1 이고, 나머지 경우는 x/10이 됩니다. 

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

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	ll x; cin >> x;
	if (x < 0 && x % 10) {
		cout << x / 10 - 1 << '\n';
	}
	else {
		cout << x / 10 << '\n';
	}
}

 

 

 

C.

두 좌표가 주어질 때 knight로 fork를 걸 수 있는지 묻는 문제입니다.

좌표가 정수이기 때문에 fork가 성공하려면 5=1^2+2^2 이므로 항상 (1,2), (2,1) 차이나게 

만들어져야 합니다. 따라서 각 좌표를 기준으로 8방향으로 새롭게 나이트의 이동 좌표를 만들고

그 중 겹치는 좌표가 있다면 Yes를 출력해주면 됩니다. 좌표값 저장은 map으로 해줍시다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int dx[8] = { -2,-2,-1,-1,1,1,2,2 };
int dy[8] = { 1,-1,2,-2,2,-2,1,-1 };

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int x1, y1, x2, y2;
	map<pair<int, int>, int>vis;
	cin >> x1 >> y1 >> x2 >> y2;
	for (int k = 0; k < 8; k++) {
		vis[{x1 + dx[k], y1 + dy[k]}] = 1;
	}
	for (int k = 0; k < 8; k++) {
		if (vis[{x2 + dx[k], y2 + dy[k]}]) {
			cout << "Yes\n";
			return 0;
		}
	}
	cout << "No\n";
}

 

 

 

D. 

게임 문제입니다. Aoki가 이기려면 takashi가 아무 수나 a<=i<=b를 골라도 소수를 만들 수 있는

c<=j<=d가 존재하면 됩니다. 모든 경우 존재하지 않으면 takashi가 이기게 됩니다.

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

bool prime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0) {
			return false;
		}
	}
	return true;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	for (int i = a; i <= b; i++) {
		bool possible = false;
		for (int j = c; j <= d; j++) {
			if (prime(i + j)) {
				possible = true;
			}
		}
		if (!possible) {
			cout << "Takahashi\n";
			return 0;
		}
	}
	cout << "Aoki\n";
}

 

 

 

E. 

트리 구성 문제입니다. K가 20이하라는게 특이합니다. 각 노드마다 20개씩 최댓값들을 저장하면 됩니다.

리프노드부터 DFS를 하면서 최대 20개씩 구성하고 정렬해줍니다. 정렬시간은 20log20밖에 안됩니다.

따라서 총 O(NKlog(NK))에 모든 점에 대해 최대 20개씩 집합을 만들어줄 수 있습니다.

쿼리는 각 집합의 k번째 값이므로 O(1)에 구할 수 있습니다.

#include<bits/stdc++.h>
using namespace std;
int n, x[100001], a, b;
int q, v, k;
vector<int>g[100001];
vector<int>memo[100001]; 

void dfs(int u, int p) {
	vector<int>temp;
	temp.push_back(x[u]);
	for (int v : g[u]) {
		if (v == p)continue;
		dfs(v, u);
		for (int x : memo[v]) {
			temp.push_back(x);
		}
	}
	sort(temp.rbegin(), temp.rend());
	for (int i = 0; i < min(20, (int)temp.size()); i++) {
		memo[u].push_back(temp[i]);
	}
}


int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i++)cin >> x[i];
	for (int i = 1; i < n; i++) {
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(1, -1);
	while (q--) {
		cin >> v >> k;
		cout << memo[v][k - 1] << '\n';
	}
}

 

 

F.

풀이 예정

 

 

G. 

플로우 문제입니다. 그런데 정점을 막아야 하므로 정점분할이 필요합니다.

최대유량 - 최소컷 정리에 따라 최소비용의 답은 최대유량입니다. 이제 막은 도시들을 구해줍시다.

막은 도시들은 BFS를 하면서 in 정점은 방문했으면서 out 정점은 방문하지 않은 점들입니다.

이것들을 출력해주면 됩니다. well-known 문제입니다. 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, m, c;
const int MAX = 202;
vector<int>g[MAX];
ll work[MAX], lv[MAX], cap[MAX][MAX], flow[MAX][MAX];
int vis[MAX];

void add(int u, int v, ll c) {
	g[u].push_back(v);
	g[v].push_back(u);
	cap[u][v] += c;
}

bool bfs(int S, int T) {
	memset(lv, -1, sizeof(lv));
	queue<int>q;
	lv[S] = 0;
	q.push(S);
	while (q.size()) {
		int cur = q.front(); q.pop();
		for (int nxt : g[cur]) {
			if (lv[nxt] == -1 && cap[cur][nxt] > flow[cur][nxt]) {
				lv[nxt] = lv[cur] + 1;
				q.push(nxt);
			}
		}
	}
	return ~lv[T];
}

ll dfs(int cur, ll w, int T) {
	if (cur == T) return w;
	for (ll& i = work[cur]; i < (ll)g[cur].size(); i++) {
		int nxt = g[cur][i];
		if (lv[nxt] == lv[cur] + 1 && cap[cur][nxt] > flow[cur][nxt]) {
			ll f = dfs(nxt, min(w, cap[cur][nxt] - flow[cur][nxt]), T);
			if (f) {
				flow[cur][nxt] += f;
				flow[nxt][cur] -= f;
				return f;
			}
		}
	}
	return 0;
}

ll max_flow(int S, int T) {
	ll ret = 0;
	while (bfs(S, T)) {
		memset(work, 0, sizeof(work));
		while (1) {
			ll f = dfs(S, 1e18, T);
			if (!f) break;
			ret += f;
		}
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	while (m--) {
		int u, v; cin >> u >> v;
		add(u + n, v, 1e18);
		add(v + n, u, 1e18);
	}
	for (int i = 1; i <= n; i++) {
		cin >> c;
		if (i == 1 || i == n) c = 1e18;
		add(i, i + n, c);
	}
	ll S = 1, T = n;
	cout << max_flow(S, T + n) << '\n';

	queue<int>q;
	vis[S] = 1;
	q.push(S);
	while (q.size()) {
		int cur = q.front(); q.pop();
		for (int nxt : g[cur]) {
			if (!vis[nxt] && cap[cur][nxt] > flow[cur][nxt]) {
				vis[nxt] = 1;
				q.push(nxt);
			}
		}
	}
	vector<int>ans;
	for (int i = 1; i <= n; i++) {
		if (vis[i] && !vis[i + n]) {
			ans.push_back(i);
		}
	}
	cout << ans.size() << '\n';
	for (int i : ans) cout << i << " ";
}