AtCoder ABC 244 풀이

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

Tasks - AtCoder Beginner Contest 244

 

 

 

A.

마지막 글자를 출력해줍시다.

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

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int n; string s;
	cin >> n >> s;
	cout << s.back() << '\n';
}

 

 

 

B. 

회전방향을 0123 순으로 북동남서 로 정의합니다. 90도 시계회전은 dir에서 (dir+1)%4로 바뀝니다.

바꿔주면서 전진해나가면 됩니다. 4방향의 (x,y)변화량도 dx, dy로 만들면 쉽게 구현할 수 있습니다.

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

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int n; cin >> n;
	string s; cin >> s; 
	int x = 0, y = 0, dir = 1;
	for (int i = 0; i < n; i++) {
		if (s[i] == 'R') {
			dir = (dir + 1) % 4;
		}
		else {
			x += dx[dir];
			y += dy[dir];
		}
	}
	cout << x << " " << y << '\n';
}

 

 

 

C. 

PASS

 

 

 

D. 

정확히 10^18번만에 S상태에서 T상태로 바뀔지 있는지 묻고 있습니다. 

매우 큰 수를 준걸 보니 홀짝성이 중요하지 구체적인 값은 중요하지 않을 것 같습니다. 

관찰 1.  2번만에 바꿔줄 수 있으면  짝수시간에 항상 가능합니다.

관찰 2.  1번만에 바꿔줄 수 있으면  짝수시간에 항상 불가능합니다.

우선 RGB 로 만드는 6가지 경우를 보면, 

{ RGB, GBR, BRG } , { RBG, GRB, BGR }  이렇게 가능합니다.

이렇게 나누면 같은 집합 내에선 2번만에 바꿔줄 수 있습니다.

다른 집합에 속하면 1번만에 바뀌므로 불가능합니다.

따라서 두 순열이 같은 집합에 있는지만 판단해주면 됩니다. 

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

bool chk(string s) {
	return (s == "R G B" || s == "G B R" || s == "B R G");
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	string s, t;
	getline(cin, s);
	getline(cin, t);
	cout << (chk(s) == chk(t) ? "Yes" : "No");
}

 

 

 

E. 

딱봐도 DP입니다. 필요한 인자는 현재 정점의 번호, 길이, X가 등장한 횟수입니다.

여기서 횟수의 홀짝성만 중요하니 마지막 인자는 0/1로 채워줍니다.

dp[u][len][f]를, 

        u를 마지막으로 채웠고, 현재길이 len, X등장 횟수의 홀짝성이 f일 때 경우의 수로 정의합시다.

dp[u][len][f]는,  v∈g[u]에 대해, 

       dp[v][len+1]로 전이되고, 이 때 f는 v가 x일 땐 flip, v!=x일땐 그대로 f로 전이합니다.

base case는 u=T, len=k+1, f=0일 때 1입니다. 재밌는 문제였습니다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
int n, m, k, S, T, X, u, v;
vector<int>g[2002];
ll dp[2002][2002][2];

ll go(int u, int len, bool f) {
	if (len == k + 1) {
		return (u == T && !f ? 1 : 0);
	}
	ll& ret = dp[u][len][f];
	if (~ret) return ret;
	ret = 0;
	for (int v : g[u]) {
		ret += go(v, len + 1, v!= X ? f : 1 - f);
		ret %= mod;
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m >> k >> S >> T >> X;
	while (m--) {
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	memset(dp, -1, sizeof(dp));
	cout << go(S, 1, 0) << '\n';
}

 

 

 

F.

그래프의 상태가 주어질 때 그 그래프를 만드는 최단시간을 구해주는 문제입니다. 

N이 17로 작으니 비트마스크 dp를 떠올릴 수 있습니다.

dp[s][u]를 상태s이고 u로 끝나는 그래프의 최단시간이라고 정의합시다.

BFS를 하면서 진행해주면 됩니다. 현재 상태 s와 현재 노드 u에서 다음으로 전이할 때

다음 노드 v에 대해 상태는 ns = s^(1<<v)가 됩니다.

목표하는 상태가 각 노드의 홀짝성으로 이루어져 있기 때문에 그렇습니다.

그래서 짝수번 나오면 비트가 꺼져있고 홀수번 나오면 비트가 켜져있는 상태가 됩니다. 

dp[ns][v]=dp[s][u]+1을 갱신해주면 BFS를 진행하면 시간은 O(N*2^N)입니다.

모든 상태 S에 대해 답은 모든 u에 대해 min(dp[S][u])를 더해주면 됩니다.

총 시간 O(N^2*2^N)에 해결해줄 수 있습니다. 

#include<bits/stdc++.h>
using namespace std;
vector<int>g[18];
int n, m, u, v;
int dp[1 << 17 + 1][18];
queue<pair<int, int>>q;

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	while (m--) {
		cin >> u >> v;
		u--, v--; 
		g[u].push_back(v);
		g[v].push_back(u);
	}
	int N = 1 << n;
	fill(&dp[0][0], &dp[N][n], 1e9);
	for (int i = 0; i < n; i++) {
		dp[1 << i][i] = 1;
		q.push({ 1 << i, i });
	}
	while (q.size()) {
		auto [s, u] = q.front(); q.pop();
		for (int v : g[u]) {
			int ns = s ^ (1 << v);
			if (dp[ns][v] != 1e9)continue;
			dp[ns][v] = dp[s][u] + 1;
			q.push({ ns, v });
		}
	}
	long long ans = 0;
	for (int s = 1; s < N; s++) {
		int temp = 1e9;
		for (int u = 0; u < n; u++) {
			temp = min(temp, dp[s][u]);
		}
		ans += temp;
	}
	cout << ans << '\n';
}