Codeforces Round #584 후기 + 풀이

C번에서 아예 생각을 잘못 해서 8번 정도 틀리고, 사소한 구현 실수로 한번 RTE를 받아서 라운드가 망해버렸다. ABCD까지를 빠르게 풀고 E1이나 G1을 열심히 띵킹해서 맞췄어야 했던 라운드인데, C번을 마지막에 5분 남기고 간신히 풀어서...

별개로 문제 자체는 꽤 좋았던것 같다.

---

A. Paint the Numbers

어떤 수 $x$ 를 색 $c$로 칠한다면, $x$의 배수는 모두 $c$로 칠할 수 있다. 따라서, 지금 있는 수 중 가장 작은 수를 골라서 칠하고, 그 배수들을 모두 같은 색으로 칠하면서 지워버리면 필요한 색의 개수를 알 수 있다.

미리 숫자들을 정렬하고 이 작업을 수행하면 편하게 코딩할 수 있다.

#include <bits/stdc++.h>
#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")
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>;
 
vector <pair <int, bool>> v;
bool done()
{
	for(auto it:v)
		if (!it.second)
			return 0;
	return 1;
}
int main()
{
	int n, c = 0;
	cin >> n;
	v.resize(n);
	for (int i = 0; i<n; i++)
	{
		int x;
		cin >> x;
		v[i].first = x;
	}
	sort(all(v));
	for (int i = 0; i<n; i++)
	{
		if (!v[i].second)
		{
			c++;
			v[i].second = true;
			for (int j = 0; j<n; j++)
				if (v[j].first%v[i].first==0)
					v[j].second = true;
		}
		if (done())
			break;
	}
	cout << c;
}

---

B. Koala and Lights

각 전구는 $b_i$ 분 후부터 시작해서, $a_i$ 분에 한 번씩 toggle 된다 (켜져 있으면 꺼지고, 꺼져 있으면 켜진다)

이때 최대한 많은 전구가 켜져 있을 때 켜진 전구의 개수를 세는 문제.

$a_i, b_i \leq 5$ 라는 매우 작은 조건을 가지고 있기 때문에, 사실은 매우 짧은 시간 (길어야 몇백 이내) 에 전체 전구의 상태에 대하여 주기가 돌게 된다. 따라서, 적당한 횟수를 시뮬레이션하면 구할 수 있다.

#include <bits/stdc++.h>
#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")
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>;
 
bool light[120][1500];
string str;
int ans;
int a[120], b[120];
int main()
{
	int n;
	cin >> n;
	cin >> str;
	for (int i = 0; i<n; i++)
		light[i][0] = (str[i]=='1');
	for (int i = 0; i<n; i++)
	{
		cin >> a[i] >> b[i];
		bool cur = light[i][0];
		for (int t = 1; t<b[i]; t++)
			light[i][t] = light[i][t-1];
		for (int t = b[i]; t<1500; t++)
		{
			if ((t-b[i])%a[i]==0)
				light[i][t] = !(light[i][t-1]);
			else 
                light[i][t] = light[i][t-1];
		}
	}
	for (int t = 0; t<1500; t++)
	{
		int tp = 0;
		for (int i = 0; i<n; i++)
			tp += light[i][t];
		ans = max(ans, tp);
	}
	cout << ans;
}

---

C. Paint The Digits

매우 고통받은 문제.

요지는 어떤 0~9들로만 이루어진 문자열 (0~9로 이루어진 수열로 봐도 무방하다) 에 대해서, 이 문자열을 2개의 Non-decreasing Subsequence로 쪼개서 이 두 부분수열을 A, B라고 하자. 이때, A 다음에 B를 이어 쓰는 식으로 쓰면 전체가 Non-decreasing이어야 한다.

 

처음 봤을때는 dlwocks와의 연습에서 돌았던 앳코더의 이 문제 https://atcoder.jp/contests/abc134/tasks/abc134_e 가 생각났다. 이 문제는 주어진 수열을 cover하기 위해 필요한 최소 개수의 increasing subsequence를 세는 문제로, Dilworth's Theorem이라는 좋은 정리가 있어서 쉽게 해결할 수 있는데 이건 나중에 따로 포스팅하기로 하고... 

 

여튼 요점은, 어떤 수열을 증가하는 부분수열 $n$개로 쪼갤 수 있으려면 그 수열의 가장 긴 감소하는 부분수열의 길이가 $n$이어야 한다.

 

그래서 이걸로 뭔가 구하려고 하다가, 생각해 보니 개수만 구하는게 아니라 실제로 판정도 해야 하고, subsequence A 뒤에 B를 이어 쓸 거라서 A의 마지막 digit 보다 B의 첫 digit이 크거나 같아야 한다는것도 있고 해서, 

 

- LIS를 구하고 (사실은 Nondecreasing을 구하는거니까 약간 구현 차이가 있지만 전체 틀은 같다)

- 남은게 Nondecreasing sequence 인지 보고

 

이러면 될 줄 알았는데, 왜인지 잘 모르겠지만 8번을 틀렸다.

 

결국 한참 뒤에 생각한건 대략 다음과 같다.

전체 수열 seq에 대해서, $i$번째를 수열 B에 집어넣을 조건은 다음 둘 중 하나이다.

- $seq[j] < seq[i]$ 인 $j > i$ 가 존재. (즉, 나보다 작은 수가 내 뒤에 하나라도 나오면)

- $u < seq[i]$ 이면서, 이미 수열 B에 $u$가 들어 있는 경우. (즉, 나보다 작은 수가 이미 B에 들어간 적이 있는 경우)

 

이렇게 하면, 수열 B가 Nondecreasing임은 보장되고, A도 만약 Nondecreasing이 아니라면 첫 조건에서 걸렸을 거라서 Nondecreasing이고, A의 맨 뒤보다 B의 처음이 크거나 같음도 보장되기 때문에 해결할 수 있다. (증명은 라운드 중에는 시간이 후달려서 못 했지만, 대충 생각해 보니 되는거 같았다)

 

그리디하게 / 또는 조금 생각해서 브루트포스로 해결할 수 있는 문제에 LIS 같은걸 열심히 생각하고 망한게 약간 작년 ICPC Preliminary때 Passport Control이 생각나긴 하는데, 이번엔 그런짓 안하게 조심해야지...

 

#include <bits/stdc++.h>
#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")
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>;
string str;
vector <int> seq;
vector <int> ans;
int color[201010];
int lastocc[10];
bool in2[10];
void solve()
{
	int n;
	str.clear(), seq.clear(), memset(lastocc, -1, sizeof(lastocc));
	ans.clear();
	memset(in2,0,sizeof(in2));
	memset(color,0,sizeof(color));
	cin >> n >> str;
	for (int i = 0; i<n; i++)
	{
		int x = str[i]-'0';
		lastocc[x] = i;
		seq.push_back(x);
	}
	for (int i = 0; i<n; i++)
	{
		bool flag = false;
		for (int j = 0; j<seq[i]; j++)
		{
			if (lastocc[j] > i || in2[j])
			{
				flag = true;
				break;
			}
		}
		color[i] = flag?2:1;
		if (color[i]==2)
			in2[seq[i]] = true;
	}
	for (int i = 0; i<n; i++)
		if (color[i] == 1)
			ans.push_back(seq[i]);
	for (int i = 0; i<n; i++)
		if (color[i] == 2)
			ans.push_back(seq[i]);
	for (int i = 1; i<n; i++)
	{
		if (ans[i]>=ans[i-1])
			continue;
		else
		{
			cout << "-\n";
			return;
		}
	}
	for (int i = 0; i<n; i++)
		cout << color[i];
	cout << '\n';
	return;
}
 
int main()
{
	usecppio
	int t;
	cin >> t;
	while(t--)
		solve();
}

---

D. Cow and Snacks

손님 $k$명과 간식 $n$종류가 있고, 각 손님에게는 두 개의 "선호하는 간식" 이 있다.

이때, 누군가를 초대하면 그 사람은 와서 자신이 선호하는 간식을 모두 먹는데, 하나도 먹을 수 없으면 (이미 앞에서 누군가 다 먹었으면) 초대할 수 없다. 최대한 초대할 수 있는 사람 수를 구하는 문제. (사실은 초대할 수 없는 사람을 구하는건데 이건 빼면 되니까...)

 

이 문제를 그래프로 모델링할 수 있는데, 어떤 손님이 $x, y$ 를 선호한다면 $x$번과 $y$번 노드를 이어 줄 수 있다. 이렇게 하면, 아무도 먹을 생각이 없는 간식은 혼자 남게 되고, 그 외에는 간선들이 적당히 있는 그래프가 되는데,

여기서 간선을 하나 고를 때마다 손님을 하나씩 부르는 셈이 되고, 간선을 고르기 위해서는 양쪽 끝 중 하나 이상이 아직 방문한 적 없어야 한다. 이 조건이 뭔가 DSU랑도 매우 비슷한거 같고, 아무튼 결과적으로

$x$개짜리 Connected Component가 있다면, $x-1$ 명을 부를 수 있다. (간선을 그만큼 고를 수 있으니까) 즉, Connected Component의 spanning tree 에 포함된 간선 (사람들) 을 고르면 된다.

#include <bits/stdc++.h>
#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")
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>;
 
vector <int> graph[101010];
bool visit[101010];
int cnt;
void dfs(int r)
{
	visit[r] = true;
	cnt++;
	for (auto it:graph[r])
	{
		if (!visit[it])
			dfs(it);
	}
	return;
}
int ans = 0;
int main()
{
	int n, k;
	cin >> n >> k;
	for (int i = 1; i<=k; i++)
	{
		int x, y;
		cin >> x >> y;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	for (int i = 1; i<=n; i++)
	{
		if (!visit[i])
		{
			cnt = 0;
			dfs(i);
			ans += (cnt-1);
		}
	}
	cout << k-ans << '\n';
}

---

C번 말려서 블루 돌아갔다. :cry:

레드아미도 있고 이번학기는 연습할게 꽤 많으니까 뚝배기가 열심히 깨지다 보면 어떻게 되겠지..? ㅋㅋㅋ