Codeforces Round #597 후기 + 풀이::::Gratus' Blog

Codeforces Round #597 후기 + 풀이

알고리즘 문제풀이/Codeforces 2019. 11. 3. 02:44

한참 만에 쓰는 Codeforce 후기 / 풀이인 것 같다.

레이팅은 -8인데, 어차피 E랑 F는 시간 조금 더 있었다고 풀었을것 같지는 않고... B랑 특히 D번 풀이를 아는데도 계속 틀린게 조금 기분나쁘긴 하지만 ㅋㅋ

A. Good ol' Numbers Coloring

숫자 $a, b$ 가 주어졌을때, $k = au + bv$ 형태로 표현되는 자연수 $(u, v)$ 쌍이 있는 $k$ 는 흰색으로, 그 외에는 검은색으로 칠한다. 이때 검은색 수가 무한한지 유한한지 판단하는 문제.

A번치고는 수학적인 생각을 조금 많이 요구한다는 생각이 들었는데, 아마도 예제를 보고 사람들이 대부분 "아 이러면 되겠지?" 라고 찍고 내서 맞은게 아닌가 싶다.

만약에 $k$가 $g = \gcd(a, b)$ 의 배수가 아니라면, $a$와 $b$의 일차결합으로 표현할 수 없으므로 $g > 1$ 이면 Infinite이고, $k$가 충분히 큰 $g$의 배수이면 항상 가능하므로 $g = 1$ 이면 finite이다.

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
	int t, a, b;
	cin >> t;
	while(t--)
	{
		cin >> a >> b;
		cout << ((__gcd(a, b)==1)?"Finite":"Infinite") << '\n';
	}
}

B. Restricted RPS

가위바위보를 하는데, Bob은 가위-바위-보를 내는 순서가 미리 정해져 있고, Alice는 각각을 몇 번 낼지가 정해져 있다. 이때, Alice가 이 허용된 가위-바위-보 갯수로 sequence를 적절하게 만들어서 bob을 전체의 반보다 많이 이길 수 있는지 판정하는 문제.

그리디하게 최대한 앞에서부터 많이 이기는 방식으로 시도하면 된다. 상대가 Rock을 낼 예정이고, 낼 수 있는 Paper가 남았다면 내는 식으로 진행한다.

구현에서 약간 말려서 시간을 좀 허비했었다. 처음에는 막 각 move들이 나오는 인덱스를 세는 식으로 뇌절해서...

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) ((x).begin()),((x).end())
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimization ("unroll-loops")
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using pii = pair<int, int>;
 
char ans[5] = "RPS";
vector <int> seq;
void solve()
{
	int n;
	cin >> n;
	seq.clear();
	seq.resize(n);
	for (int i = 0; i<n; i++)
		seq[i] = -1;
	int a, b, c;
	cin >> a >> b >> c;
	string bob;
	cin >> bob;
	int maxwin = 0;
	for (int i = 0; i<bob.size(); i++)
	{
		if (bob[i] == 'R' && (b > 0))
		{
			seq[i] = 1; b--;
			maxwin++;
		}
		else if (bob[i] == 'P' && (c > 0))
		{
			seq[i] = 2; c--;
			maxwin++;
		}
		else if (bob[i] == 'S' && (a > 0))
		{
			seq[i] = 0; a--;
			maxwin++;
		}
	}
	if (maxwin*2 >= n)
	{
		cout << "YES\n";
	}
	else
	{	cout << "NO\n";
		return;
	}
	for (int i = 0; i<n; i++)
	{
		if (seq[i]==-1)
		{
			if (a)
			{
				seq[i] = 0; 
				a--;
			}
			else if (b)
			{
				seq[i] = 1; 
				b--;
			}
			else if (c)
			{
				seq[i] = 2; 
				c--;
			}
		}
	}
	for (int i = 0; i<n; i++)
		cout << ans[seq[i]];
	cout << '\n';
}
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		solve();
	}
}

C. Constanzes's Machine

w를 타이핑하면 uu가 나오고, m을 타이핑하면 nn이 나오는 기계에서 타이핑된 sequence가 주어지고, 원래 타이핑하려던 글로 가능한 것의 개수를 세는 문제.

uuuuu... 가 $k$개 반복되는 경우, 원래 가능했던 경우의 수는 $k$번째 피보나치 수 만큼이다. uuuu... 의 k-2개 sequence + w 하나가 있었거나, k-1개와 u 하나 더 있었거나.

또한, 저런 기계에서 타이핑한 결과이므로 w나 m은 절대 나올 수가 없다. 나온 적이 있다면 항상 잘못된 결과이므로 0을 출력해야 한다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) ((x).begin()),((x).end())
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimization ("unroll-loops")
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using pii = pair<int, int>;
#define int ll
const int mod = 1000000007;
int fibo[101010];
vector <int> tonum;
string str;
int32_t main()
{
	fibo[1] = 1;
	fibo[2] = 2;
	for (int i = 3; i<101010; i++)
		fibo[i] = (fibo[i-1] + fibo[i-2]) % mod;
	cin >> str;
	for (int i = 0; i<str.size(); i++)
	{
		if (str[i] == 'w' || str[i] == 'm')
		{
			cout << 0 << '\n'; return 0;
		}
		if (tonum.empty())
			tonum.push_back(1);
		else
		{
			if (str[i] == str[i-1])
			{
				if (str[i] == 'u' || str[i] =='n')
					tonum.back()+=1;
				else
					tonum.push_back(1);
			}
			else
				tonum.push_back(1);
		}
	}
	int ans = 1;
	for (auto it:tonum)
	{
		ans *= fibo[it];
		ans %= mod;
	}
	cout << ans << '\n';
}

D. Shichikuji and Power Grid

굉장히 재밌게 푼 문제.

좌표평면 상에 $n ( n \leq 2000) $개의 도시가 주어지는데, 각 도시끼리 전선을 연결할 때는 미리 정해진 두 도시의 상수값 $\texttt{k[i]}$ 들에 기반하여 $\texttt{(k[i]+k[j]) * dist(i, j)}$ 의 비용이 들어간다.

또한, 각 도시에는 발전소를 설치할 수 있는데, 이때도 각 도시마다 다른 상수 $\texttt{c[i]}$ 만큼의 비용이 들어간다.

발전소와 연결된 (같은 connected component 상에 존재하는) 모든 도시에 전력을 공급할 수 있도록 하는 최소 비용을 찾는 문제.

뭔가 이런 유형의 문제는 사실 최단 경로거나, MST 같은 문제로 많이 환원된다. 이 문제의 경우, 다음과 같은 생각을 통해 MST 문제로 바꿀 수 있다.

- 가상의 0번 정점을 만든다. 이 정점은 '발전소 설치' 를 의미한다고 하자. 즉, 간선 (0, i) 의 가중치는 $i$번 도시에 발전소를 설치하는 비용에 해당한다.

- 정점들끼리 미리 cost를 모두 계산해서 이어준다.

이렇게 하면 $n+1$개의 정점을 가진 complete graph를 얻는다. $n$이 2천이므로, 간선은 대략 400만 개 (무방향이라서, 역방향과 정방향 간선을 고려하면서 짜느니 간선이 2배 많아지는게 구현이 편할 때가 많다) 정도 된다.

이 그래프에서 MST (Minimum Spanning Tree) 를 찾는 문제는 원래의 문제와 정확하게 같으며, 0번 정점과 이어진 간선을 택하는 행동은 그 위치에 발전소를 짓는 것으로 간주하면 된다.

뭐 이렇게 짜면 되는데, 5번 MLE를 받았다. 사실 400만개의 간선이 각각 start, end, weight를 가지면 그것만으로 저장해야할 정보가 1200만 개에, 시간을 잘 줄이기 위해서는 마킹해야 하므로 사용한 간선들도 다시 저장해 줘야 하고... 그래도 안 들어갈 만큼은 아니라고 생각했는데, 구현에서 메모리 오버헤드가 좀 크게 짰던 것 같다.

특히 평소에 integer overflow가 우려되는 문제에서 뭐가 int고 뭐가 long long이어야 하는지, 언제 long long으로 캐스팅해야 하는지 (곱셈하고 캐스팅하면 오버플로우가 이미 난 상태라 이미 망해 있으므로, 캐스팅하고 곱셈해야 한다) 생각하기가 어렵기도 하고 귀찮기도 하고 하다보니 맨 위에 $\texttt{#define int ll}$ 을 때려넣었는데, 이렇게 하면 메모리 소비가 2배 많아져서 메모리 제한에 더 잘 걸리게 된다.

결국 Prim으로 짰던 MST 구현을 Kruskal로 급히 바꾸고, $\texttt{#define int ll}$을 없애고 직접 캐스팅해서 냈다. 512MB 메모리 주면 어디 덧나나...ㅠ

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using pii = pair<int, int>;
ll n, station[2020], k[2020];
int dist[2020][2020];
pii town[2020];
inline int df(pii &a, pii &b)
{
	return (abs(a.first - b.first) + abs(a.second - b.second));
}

struct edge
{
	int s, e;
	ll w;
	bool operator<(const edge & other)
	{
		if (w == other.w) return (s+e) < (other.s + other.e);
		return w < other.w;
	}
};
vector <edge> edgelist;

struct Disjoint_Set_Union
{
#define V 2020
	int parent[V], size[V];
	Disjoint_Set_Union(int N = V-1)
	{
		init(N);
	}
	void init(int N)
	{
		for(int i=0;i<=N;i++)
		{
			parent[i]=i;
			size[i]=1;
		}
	}
	int Find(int K)
	{
		while(K!=parent[K])
		{
			parent[K]=parent[parent[K]];
			K=parent[K];
		}
		return K;
	}
	void unite(int x, int y)
	{
		int u=Find(x), v=Find(y);
		if(u==v)
			return;
		if(size[u]>size[v])
			swap(u, v);
		size[v]+=size[u];
		size[u] = 0;
		parent[u] = parent[v];
	}
} dsu;

vector <pii> pp;
ll Kruskal()
{
	ll mstlen = 0;
	sort(edgelist.begin(),edgelist.end());
	for (auto it:edgelist)
	{
		if (dsu.Find(it.s)==dsu.Find(it.e)) 
			continue;
		else
		{
			dsu.unite(it.s,it.e);
			pp.push_back({it.s, it.e});
			mstlen += it.w;
		}
	}
	return mstlen;
}



int build[2020];
int32_t main()
{
	usecppio
	cin >> n;
	for (int i = 1; i<=n; i++)
		cin >> town[i].first >> town[i].second;
	for (int i = 1; i<=n; i++)
		cin >> station[i];
	for (int i = 1; i<=n; i++) cin >> k[i];
	for (int i = 1; i<=n; i++)
		for (int j = 1; j<=n; j++)
			dist[i][j] = df(town[i], town[j]);
	for (int i = 1; i<=n; i++)
	{
		edgelist.push_back({i, 0, station[i]});
		edgelist.push_back({0,i,station[i]});
	}
	for (int i = 1; i<=n; i++)
	{
		for (int j = 1; j<=n; j++)
		{
			if (i == j) continue;
			edgelist.push_back({i, j, (ll)dist[i][j]*(k[i]+k[j])});
			edgelist.push_back({j, i, (ll)dist[i][j]*(k[i]+k[j])});
		}
	}
	ll Len = Kruskal();
	cout << Len << '\n';
	int bc = 0;
	int uu = 0;
	for (auto it:pp)
	{
		if (it.first == 0)
		{
			build[it.second] = 1;
			bc++;
		}
		else if (it.second == 0)
		{
			build[it.first] = 1;
			bc++;
		}
		else uu++;
	}
	cout << bc << '\n';
	for (int i = 1; i<=n; i++)
		if (build[i])
			cout << i << ' ';
	cout << '\n';
	cout << uu << '\n';
	for (auto it:pp)
	{
		if (it.first != 0 && it.second!=0)
			cout << it.first <<' ' << it.second << '\n';
	}
}

D번이 그럭저럭 재밌어서 풀만했다. E랑 F는 좀 많이 빡센 것 같던데, 언제 업솔빙하지...

'알고리즘 문제풀이 > Codeforces' 카테고리의 다른 글

Codeforces Edu78 F [Cards] 풀이 (0)	2019.12.20
Codeforces Round 603 (Div.2) 후기 + 풀이 (0)	2019.12.01
Codeforces Round #584 후기 + 풀이 (0)	2019.09.15
Codeforces Round #583 후기 + 풀이 (0)	2019.09.05
Codeforces Round #581 (Div.2) 후기 + 풀이 (퍼플 달성!) (4)	2019.08.21

Gratus' Blog