Codeforces Global Round 22

8문제 중 6문제를 푸는 데 성공하며 2551점까지 레이팅을 끌어올렸습니다.

A번

평소 A번보다는 어려운 느낌이 있던 문제였습니다. 먼저 0 타입의 스킬과 1 타입의 스킬을 정렬한 뒤, 0 타입 스킬의 개수<1 타입 스킬의 개수이면 11110101 순서, 0 타입 스킬의 개수=1 타입 스킬의 개수이면 10101010 또는 01010101 순서, 0 타입 스킬의 개수>1 타입 스킬의 개수이면 00001010 순서로 배열하면 됩니다.

#include <bits/stdc++.h>
using namespace std;
#define int long long
int vis[100100];
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int T;
	cin >> T;
	while (T--)
	{
		int N;
		cin >> N;
		int i;
		vector<int>a, b;
		for (i = 0; i < N; i++)
		{
			cin >> vis[i];
		}
		int ans = 0;
		for (i = 0; i < N; i++)
		{
			int x;
			cin >> x;
			ans += x;
			if (vis[i])
			{
				b.push_back(x);
			}
			else
			{
				a.push_back(x);
			}
		}
		sort(a.begin(), a.end());
		sort(b.begin(), b.end());
		if (a.size() < b.size())
		{
			for (i = 0; i < a.size(); i++)
			{
				ans += a[i];
			}
			for (i = b.size() - a.size(); i < b.size(); i++)
			{
				ans += b[i];
			}
		}
		else if (a.size() > b.size())
		{
			swap(a, b);
			for (i = 0; i < a.size(); i++)
			{
				ans += a[i];
			}
			for (i = b.size() - a.size(); i < b.size(); i++)
			{
				ans += b[i];
			}
		}
		else
		{
			for (i = 0; i < a.size(); i++)
			{
				ans += a[i];
			}
			for (i = b.size() - a.size(); i < b.size(); i++)
			{
				ans += b[i];
			}
			ans -= min(a[0], b[0]);
		}
		cout << ans << '\n';
	}
}

 

B번

A[n].A[n-1].....a[n-k+2]까지는 알 수 있습니다. 이 수열이 증가수열이 아니면 no를 출력하고, 아닐 경우에는 a[n-k+1]의 최솟값이 s[n-k+1]/(n-k+1)을 올림한 값이므로 이 값고 a[n-k+2]를 비교하면 됩니다.

k=1인 경우와 s[n-k+1]이 음수인 경우를 주의합시다.

#include <bits/stdc++.h>
using namespace std;
#define int long long
int vis[100100];
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int T;
	cin >> T;
	while (T--)
	{
		int N,K;
		cin >> N>>K;
		int i;
		vector<int>r;
		for (i = 0; i < K; i++)
		{
			int a;
			cin >> a;
			r.push_back(a);
		}
		int b = (r[0] + N - K+(N-K+1)*(1LL<<30)) / (N - K + 1)-(1LL<<30);
		for (i = 1; i < K; i++)
		{
			if (r[i] - r[i - 1] < b)
			{
				break;
			}
			else
				b = r[i] - r[i - 1];
		}
		if (i < K)
			cout << "NO" << '\n';
		else
			cout << "YES" << '\n';
	}
}

C번:

문제의 상황을 홀수 a개와 짝수 b개가 주어졌을 때 alice가 홀수를 짝수 개 가져갈 수 있는지로 바꿀 수 있습니다. a와 b가 100 이하이므로 dp[i][j][k][l]=홀수 i개와 짝수 j개가 있고, alice는 홀수를 k(0 또는 1)개 가져갔고, 현재 l(0이 alice)의 차례일 때 l이 이길 수 있는 지를 나타내는 dp식을 새울 수 있습니다. 이 dp식은 홀수와 짝수 가져가는 경우를 보며 전이할 수 있습니다. 홀수의 개수를 구할 때 음수를 조심합시다.

#include <bits/stdc++.h>
using namespace std;
#define int long long
int vis[100100];
int dp[101][101][2][2];
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int T;
	cin >> T;
	dp[0][0][0][0] = 1;
	dp[0][0][1][1] = 1;
	int i;
	for (i = 0; i <= 100; i++)
	{
		int j;
		for (j = 0; j <= 100; j++)
		{
			if (i)
			{
				dp[i][j][0][0] |= !dp[i-1][j][0][1];
				dp[i][j][0][1] |= !dp[i - 1][j][0][0];
				dp[i][j][1][0] |= !dp[i - 1][j][1][1];
				dp[i][j][1][1] |= !dp[i - 1][j][1][0];
			}
			if (j)
			{
				dp[i][j][0][0] |= !dp[i][j-1][1][1];
				dp[i][j][0][1] |= !dp[i][j-1][0][0];
				dp[i][j][1][0] |= !dp[i][j-1][0][1];
				dp[i][j][1][1] |= !dp[i][j-1][1][0];
			}
		}
	}
	while (T--)
	{
		int N;
		cin >> N;
		int a = 0;
		int b = 0;
		int i;
		for (i = 0; i < N; i++)
		{
			int x;
			cin >> x;
			if ((x + (1LL << 30)) % 2)
				b++;
			else
				a++;
		}
		if (dp[a][b][0][0])
			cout << "Alice" << '\n';
		else
			cout << "Bob" << '\n';
	}
}

D번

여기서부터 문제가 조금 어려워지기 시작했습니다. k는 min(b[1]~b[k])>k인 최대 k로 잡으면 됩니다. k가 정해졌으면 i에서 b[i]로 가는 간선들로 그래프를 만들어줍니다.

그래프를 만들었으면 먼저 0이나 n+1로 가는 위치들을 벡터에 넣어줍니다(둘 중 한 종류만 있습니다)

그리고 이들 중에서 들어오는 간선이 없는 것들을 먼저 넣어줍니다.

들어오는 간선이 있는 것은 최대 하나이고, 이를 마지막으로 넣어준 뒤 벡터를들어오는 간선의 시작지점들로 바꿔주고 이를 반복하면 됩니다.

k=0이나 n인 경우가 예외일 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
#define int long long
int arr[100100];
vector<int> c[100100];
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int T;
	cin >> T;
	while (T--)
	{
		int N;
		cin >> N;
		int i;
		int mi=N;
		int k = -1;
		for (i = 0; i < N; i++)
		{
			c[i + 1].clear();
			cin >> arr[i];
			mi = min(mi, arr[i]-1);
			if (mi <= i&&k==-1)
			{
				k = i;
			}
		}
		if (k == -1)
			k = N;
		for (i = 0; i < N; i++)
		{
			c[arr[i]].push_back(i+1);
		}
		vector<int>f;
		for (i = 0; i < N; i++)
		{
			if (arr[i] == N + 1 || arr[i] == 0)
			{
				f.push_back(i+1);
			}
		}
		cout << k << '\n';
		while (f.size())
		{
			for (i = 0; i < f.size(); i++)
			{
				if (!c[f[i]].size())
				{
					cout << f[i] << ' ';
				}
			}
			vector<int>nf;
			for (i = 0; i < f.size(); i++)
			{
				if (c[f[i]].size())
				{
					cout << f[i] << ' ';
					nf = c[f[i]];
				}
			}
			f = nf;
		}
		cout << '\n';
	}
}

E번

조합론 문제입니다. 우선 투 포인터를 사용해서 1~i까지의 합==j에서 n까지의 합이고, i+1~j-1 사이에 0이 아닌 원소가 있는 지점을 찾습니다. 지점 하나를 찾으면, 1~i'까지의 합이 1~i까지의 합과 같은 곳이 몇 군데=a 있는 지 확인하고, j 쪽도 똑같이 해줍니다=b. 이제 t를 0에서 min(a-1,b-1)까지 돌리면서 (a-1)C(t)*(b-1)C(t)를 모두 더한 값을 곱해주면 됩니다.(t가 x일 경우 이 사이를 x번 짜르는 것)

그리고 1~i까지의 합==i+1~j까지의 합인 곳이 있다면 하나 있을 때마다 답에 2를 곱해주면 됩니다.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MOD 998244353
int arr[100100];
int psuml[100100];
int psumr[100100];
int pw(int n, int k = MOD - 2)
{
	if (k == 0)
		return 1;
	if (k % 2)
	{
		return pw(n, k - 1) * n % MOD;
	}
	int a = pw(n, k / 2);
	return a * a % MOD;
}
int fact[100100];
int rev[100100];
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int T;
	cin >> T;
	int i;
	fact[0] = 1;
	rev[0] = 1;
	for (i = 1; i <= 100010; i++)
	{
		fact[i] = fact[i - 1] * i % MOD;
		rev[i] = pw(fact[i]);
	}
	while (T--)
	{
		int N;
		cin >> N;
		int i;
		int s = 0;
		for (i = 0; i < N; i++)
		{
			cin >> arr[i];
			s += arr[i];
			psuml[i] = arr[i];
			if (i)
			{
				psuml[i] += psuml[i - 1];
			}
		}
		for (i = 1; i < N; i++)
		{
			psumr[i] = s - psuml[i - 1];
		}
		psumr[0] = s;
		int ans = 1;
		int e = N-1;
		i = 0;
		while(i<N-1)
		{
			if (psuml[i] * 2 > s)
				break;
			if (psuml[i] * 2 == s)
			{
				ans *= 2;
				ans %= MOD;
				i++;
				continue;
			}
			while (psumr[e] < psuml[i])
			{
				e--;
			}
			if (psumr[e] == psuml[i])
			{
				int ni = i;
				int ne = e;
				while (psuml[ni] == psuml[i])
					ni++;
				while (psumr[ne] == psumr[e])
					ne--;
				int v = ni - i;
				int v2 = e - ne;
				int va = 0;
				int j;
				for (j = 0; j <= min(v,v2); j++)
				{
					va += (fact[v] * rev[j] % MOD * rev[v - j] % MOD) * (fact[v2] * rev[j] % MOD * rev[v2 - j] % MOD);
					va %= MOD;
				}
				ans *= va;
				ans %= MOD;
				i = ni;
				e = ne;
				if (ni >= ne)
				{
					break;
				}
			}
			else
			{
				i++;
			}
		}
		cout << ans << '\n';
	}
}

F번

왜 되는지 모르겠는 풀이를 냈는데 맞았습니다.

풀이: 가장 degree가 높은 정점 중 아직 현재 연결 요소가 충분히 크지 않은 정점을 골라서, 충분히 많은 정점들과 연결이 될 때 까지 쿼리를 해주고, 간선을 찾으면서 유니온 파인드를 해줍니다. 만약 중간에 연결 요소가 충분히 커져서 이 연결 요소가 조건을 만족하게 된다면 바로 다른 정점으로 가주면 됩니다.

#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
#define int long long
int d[1010];
int uf[1010];
int siz[1010];
int siz2[1010];
int f(int n)
{
	return uf[n] == n ? n : uf[n] = f(uf[n]);
}
void u(int n, int m)
{
	n = f(n);
	m = f(m);
	if (n == m)
		return;
	siz[m] += siz[n];
	siz2[m] += siz2[n];
	uf[f(n)] = uf[f(m)];
}
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int T;
	cin >> T;
	while (T--)
	{
		int N;
		cin >> N;
		int i;
		for (i = 0; i < N; i++)
		{
			cin >> d[i];
			uf[i] = i;
			siz[i] = 1;
			siz2[i] = d[i];
		}
		int c = 0;
		while (1)
		{
			pair<int, int>ma = { 0LL,0LL };
			for (i = 0; i < N; i++)
			{
				if (siz2[f(i)] > siz[f(i)]* siz[f(i)])
				{
					ma = max(ma, { d[i],i });
				}
			}
			if (ma.first == 0)
				break;
			int v = ma.second;
			for (i = 0; i < ma.first; i++)
			{
				if (siz2[f(v)] <= siz[f(v)] * siz[f(v)])
				{
					break;
				}
				c++;
				assert(c != N);
				cout << "? " << v+1 << '\n';
				cout.flush();
				int a;
				cin >> a;
				u(v, a - 1);
			}
		}
		cout << "! ";
		for (i = 0; i < N; i++)
		{
			cout << f(i) + 1<< ' ';
		}
		cout << '\n';
		cout.flush();
		
	}
}