Codeforces Round 603 (Div.2) 후기 + 풀이

Pretest 에서는 한 번도 안 틀리고 갔는데, B번에서 Failed System Test를 받았다. 프리텟을 9개 미만으로 넣었냐

 

퍼플 복귀 성공 :)

---

A. Sweet Dreams

최근에 본 A번 중 가장 어려운거 같다. 한 5분정도 생각이 안나서 라운드를 던질지 고민했었는데..

$a, b, c$ 개씩의 세 종류의 사탕이 주어졌을 때 (Without loss of generality, $a \geq b \geq c$ 라 하자) 가 주어졌을 때, 서로 다른걸로 두개씩 고르는 행동을 몇 번 할 수 있는지 묻는 문제.

일단 $c$는 다 챙길 수 있으므로, 적어도 답은 $c$ 이상이다. 3번 사탕을 다 챙기되, 뭐랑 매칭해서 챙길지의 문제.

$a - b  =g$ 를 고려해서, 나중에 $a$와 $b$의 개수가 최대한 비슷하도록 $a$에서 조금 많이 챙기는 식으로 가면 된다.

#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);
#define int ll
int a, b, c;
 
void solve()
{
	a = 0, b = 0, c = 0;
	int x, y, z;
	cin >> x >> y >> z;
	a = max(x, max(y, z));
	c = min(x, min(y, z));
	b = x+y+z-a-c;
	int v = min(c,(c+a-b)/2);
	int u = c-v;
	a -= v, b -= u;
	int ans = 0;
	ans += c + min(a,b);
	cout << ans << '\n';
}
int32_t main()
{
	int t;
	cin >> t;
	while(t--)
		solve();
}

---

B. Pin Codes

최대 10개까지의 코드가 들어오면, 적어도 몇 글자를 바꿔야 하는지 찾는 문제. 

10개라서 최악의 경우에도 각각에게 다른 1의 자리 수를 줄 수 있으므로, 이렇게 하면 된다.

(3010과 3010, 3011 이렇게 3개가 들어오면 하나를 3012로 바꾸는 식)

오프라인으로 한번에 받고 바꿔야 하는데 받으면서 하다가 틀렸다. 당연히 나중에 뭐가 들어올지 모르는 상황에서, 지금 있는 것들만 가지고 결정할 수가 없으니까... 생각해보면 당연히 말도 안되는 코드인데 이게 프리테스트를 왜 통과하냐;;;

---

C. Everyone is a Winner!

$n$이 주어졌을 때, $[n / x]$ 로 가능한 서로 다른 정수를 찾는 문제. 만약 $n$이 13이면, 

$x = 14$ 이상일 때의 0, $x = 7,8,9,10,11,12,13$ 일 때의 1, $x = 5, 6$ 일 때의 2, $x = 4$일 때의 3, $x = 3$ 일 때의 4, $x = 2$ 일 때의 6, $x = 1$ 일 때의 13.. 이런 식으로.

잘 생각해 보면, $ab \leq x$ 인 $a$ 와 $b$ 조합을 서로 다르게 찾는 거고, 두 수 중 하나는 $\sqrt n$ 보다 작거나 같아야 하므로 $\sqrt n$ 까지만 검사하면 문제를 풀 수 있다. 이 비슷한 발상은 워낙 많이 쓰여서 어디선가 본거 같은데, 그런거치고는 얼른 생각이 안 나서 은근히 시간을 많이 잡아먹었다. 

#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);
#define int ll
 
vector <int> v;
void solve()
{
	int n;
	cin >> n;
	v.clear();
	for (int i = 1; i*i<=n; i++)
	{
		if (i==n/i) v.push_back(i);
		else
		{
			v.push_back(n/i);
			v.push_back(i);
		}
	}
	v.push_back(0);
	sort(all(v));
	cout << v.size() << '\n';
	for (auto it:v)
		cout << it << ' ';
	cout << '\n';
}
int32_t main()
{
	usecppio
	int t;
	cin >> t;
	while(t--)
		solve();
}

---

D. Secret Password

Two Password (문자열) is equivalent if and only if,

- 두 문자열에 공통으로 들어있는 문자가 하나 이상 있거나 (둘다 a가 들어있다든가) 

- 어떤 다른 문자열 S와 둘 다 equivalent.

 

잘 생각해 보면, 사실 가능한 equivalence class는 총 26개다 (a가 포함된 문자열, b가 포함된 문자열, ....) 

이제 어떤 문자열에 두 개 이상의 서로 다른 문자가 포함되어 있다면, 이들 간의 equvalent 관계를 새로 만들어주는 것이므로 Union-Find로 이 연산을 빠르게 처리할 수 있다.

 

간선을 미리 다 만들어 놓고, 26개의 정점으로 된 그래프 위에서 이 간선들을 따라 Union-Find하면 매우 빠르게 문제 해결 가능. 한 문자열이 들어올때마다 싹 Union-Find 하면 필요한 최대 Union-Find가 엄청 많을 수도 있지만 아무튼 시간 내에는 돌 것 같아서 그냥 대충 냈다. 개느려야 하는데 왜 안 느린지 사실 잘 모르겠다.

#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);
#define int ll
using pii = pair<int, int>;
using ppp = pair<int , pii>;
 
vector <string> vv;
bool occ[26];
bool checked[26];
 
struct Disjoint_Set_Union
{
#define V 30
	int parent[V], size[V];
	Disjoint_Set_Union(int N = V-1)
	{
		init(N);
	}
	void init(int N)
	{
		for(int i=1;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;
	}
	int getSize(int K)
	{
		return size[Find(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;
 
 
int32_t main()
{
	usecppio
	int n;
	cin >> n;
	vv.resize(n);
	for (int i = 0; i<n; i++)
	{
		string s;
		cin >> s;
		memset(occ,0,sizeof(occ));
		for (auto it:s)
		{
			occ[it-'a'] = 1;
			checked[it-'a'] = 1;
		}
		for (int u = 0; u<26; u++)
		{
			if (!occ[u]) continue;
			for (int v = u+1; v<26; v++)
				if (occ[u] && occ[v])
					dsu.unite(u, v);
		}
		vv[i] = s;
	}
	vector <int> pars;
	for (int i = 0; i<26; i++)
		if (checked[i])
			pars.push_back(dsu.Find(i));
	sort(all(pars));
	pars.erase(unique(all(pars)),pars.end());
	cout << pars.size() << '\n';
}

---

E. Editor

처음에 보고 그냥 자러 갈까 싶었는데, 1시간 20분이 남아서 뭐...

일단 문제는 대략,

'커서' 를 0부터 시작해서 움직이는데, L (Left), R(Right) 연산이 가능하다. 0보다 작은 위치로는 갈 수 없다.

현재 커서 위치의 글자를 '(', ')' 또는 다른 문자로 만들 수 있다. (L과 R이 아닌 모든 글자는 글자 치환 연산) 

매 순간 현재의 문자열이 괄호만 봤을 때 올바른 괄호 문자열인지 판정해야 하고, 올바른 괄호 문자열이라면 최대 괄호 깊이를 확인해야 한다.

ex : ( ( ( ) ) ( ) ) 는 최대 깊이가 3

 

즉, 이 문제를 괄호 문자열을 숫자로 치환해서 풀 때의 방법을 이용해서 수열의 관점에서 생각하면 (는 +1, )는 -1이고 그 외의 모든 문자는 0이다. 1과 -1, 0 으로 구성된 수열이 100만개까지 있을 때, 이것들의 Prefix sum 중 최소의 값을 빠르게 연산해야 하고 (Prefix sum이 0 미만인 점이 하나 이상 있으면 실패) Prefix sum 중 최대의 값을 빠르게 연산해야 하고 (이 최대의 값이 최대 괄호 깊이니까), 전체의 합이 0이 되는지도 확인해야 한다 (0이 아니면 실패)

 

어떤 수열의 Prefix sum의 최대 또는 최솟값을 빠르게 ($\log$ 시간 정도에) 계산하는 방법으로, Segment Tree 를 사용할 수 있다. Segment tree on prefix sum에 대한 사용할 수 있는 코드도 어디선가 찾아서 넣어놨었던거 같고... 아무튼 템플릿에서 긁어왔다. 전체의 합이 0이 되는지도 Segment Tree로 해결 가능.

 

3개의 Segment tree를 매 순간 업데이트하고, 합을 구하는 연산을 한번씩 하면 대략 시간 복잡도는 $O(n \log n)$ 이고 상수가 굉장히 크다. (원래 세그가 갖는 상수에, 3번이니까 *3) 딱히 나은 방법이 없어서 그냥 세그 3개를 짜고 한번에 맞았다 (구현할 자신 없었는데...)

 

코드가 190줄이니까 접은글 처리.

#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>;
using ppp = pair<int , pii>;
#define MAXN 4040404
int arr[1010101];
int nn;
 
struct segsum
{
	int n;
	int tree[4040404];
	void update(int left,int right, int node, int change_node ,int diff)
	{
		if (!(left <= change_node &&change_node <= right))
			return; //No effect on such nodes.
		tree[node] += diff; // This part must be changed with tree function.
		if (left != right)
		{
			int mid = (left + right) / 2;
			update(left, mid, node * 2, change_node, diff);
			update(mid +1,right, node * 2 +1, change_node, diff);
		}
	}
	void update(int pos, int diff)
	{
		update(1,n,1,pos,diff);
	}
	int Query(int node, int left, int right, int start, int end)
	{
		if (right < start || end < left)
			return 0; //Node is out of range
		if (start <= left && right <= end)
			return tree[node]; //If node is completely in range
		int mid = (left + right) / 2;
		return Query(node * 2, left, mid, start, end)+Query(node*2+1,mid+1,right,start,end);
	}
	int sum(int right)
	{
		return Query(1,1,n,1,right);
	}
};
struct Node
{
	int sum;
	int prefix;
};
struct segmax
{
	vector <Node> tree;
	int s;
	Node combine(Node a, Node b)
	{
		Node c;
		c.sum = a.sum + b.sum;
		c.prefix = max(a.prefix , b.prefix + a.sum);
		return c;
	}
	segmax(int n = 0)
	{
		for (s = 1; s<n; s*=2);
		tree.resize(s*2);
	}
	void update(int x, int val)
	{
		int l = x+s-1;
		tree[l].sum = val;
		tree[l].prefix = val;
		l /= 2;
		while (l>=1)
		{
			tree[l] = combine(tree[l*2],tree[l*2+1]);
			l /= 2;
		}
	}
	int maxquery()
	{
		return tree[1].prefix;
	}
};
struct segmin
{
	vector <Node> tree;
	int s;
	Node combine(Node a, Node b)
	{
		Node c;
		c.sum = a.sum + b.sum;
		c.prefix = min(a.prefix , b.prefix + a.sum);
		return c;
	}
	segmin(int n = 0)
	{
		for (s = 1; s<n; s*=2);
		tree.resize(s*2);
	}
	void update(int x, int val)
	{
		int l = x+s-1;
		tree[l].sum = val;
		tree[l].prefix = val;
		l /= 2;
		while (l>=1)
		{
			tree[l] = combine(tree[l*2],tree[l*2+1]);
			l /= 2;
		}
	}
	int minquery()
	{
		return tree[1].prefix;
	}
};
segsum BIT;
segmax MAXTREE;
segmin MINTREE;
string str;
int ans[1010101];
int32_t main()
{
	usecppio
	cin >> nn;
	cin >> str;
	int rpt = 1;
	int pt = 1;
	MAXTREE = segmax(nn);
	MINTREE = segmin(nn);
	BIT.n = nn;
	int cur = 0;
	for (auto it:str)
	{
		cur++;
		int u = arr[pt];
		if (it=='L')
		{
			pt--;
			if (pt == 0)
				pt = 1;
			ans[cur] = ans[cur-1];
			continue;
		}
		else if (it == 'R')
		{
			pt++;
			if (pt > rpt)
				rpt++;
			ans[cur] = ans[cur-1];
			continue;
		}
		else if (it == '(')
		{
			arr[pt] = 1;
			BIT.update(pt, 1-u);
			MAXTREE.update(pt, 1);
			MINTREE.update(pt, 1);
		}
		else if (it == ')')
		{
			arr[pt] = -1;
			BIT.update(pt, -1-u);
			MAXTREE.update(pt, -1);
			MINTREE.update(pt, -1);
		}
		else
		{
			arr[pt] = 0;
			BIT.update(pt, -u);
			MAXTREE.update(pt, 0);
			MINTREE.update(pt, 0);
		}
		if (BIT.sum(rpt)!=0 || MINTREE.minquery()<0)
			ans[cur] = -1;
		else
			ans[cur] = MAXTREE.maxquery();
	}
	for (int i = 1; i<=nn; i++)
		cout << ans[i] << ' ';
	cout << '\n';
}

 

끝나고 알았는데, Segment Tree with Lazy Propagation을 이용하면 더 쉽게 코딩할 수 있다는 사실을 알았다. 근데 lazy 잘 못 쓰니까 처음에 생각난게 저거였다면 아마 짜는거 포기했을것 같다.

Seg * 3 코드가 280ms고, lazy가 딱히 빠르지도 않을거 같고... string 가지고 풀 수 없게 하기 위해 $n = 1e6$ 을 준 거 자체는 이해하겠지만, 이거 C++ 외의 언어로 풀 수 있는건 맞나?

 

라고 생각했었는데, Editorial 을 까보니 정해는 Stack을 몇개 이용해서 복잡도를 내리는 방법이 있는것 같았다. 언제 다시 읽어봐야지...

---

뭔가 B번 틀린건 좀 그렇지만 E 맞아서 일단 레이팅은 꽤 많이 올랐다. 실수 줄이는 것도 연습 좀 하고, Lazy propagation 같은것도 몇번 더 짜봐야 할거 같다. F는 *미친 플로우* 같던데, 이건 전혀 모르는 거고...