Codeforces Round #581 (Div.2) 후기 + 풀이 (퍼플 달성!)

정확히 1900으로 퍼플 찍었다. :dhk:  

 

이번 라운드가 1886으로 참가했어서, 행복회로를 오버클럭하면서 시작했다. 5문제짜리 라운드라서 4솔브하면 무조건 간다 정도로 생각하고 있었는데, 빠른 3솔 (+ 이후 1.5시간 뇌절) 로 퍼플 찍은걸 보니 Codeforces는 타이핑 속도 대결 쉬운 문제를 빨리 푸는거의 영향이 지나치게 높은 것 같다는 생각이 든다.

3문제를 0시간 25분에 해결한 이후 1시간 35분동안 제출 한번도 해보지 못하고 라운드 종료;;

D가 2000점 짜리 String 문제긴 했는데, 계속 생각을 했는데 계속 말려서 결국 Small도 못 긁었다. 차라리 빠르게 D를 손절하고 E를 읽고 시도했으면 풀었든 못 풀었든 더 재밌는 라운드였을것 같다.

---

A. BowWow and The Timetable

$2^{256}$ 스케일의 매우 큰 수 $s$ 에 대하여 $\lceil \log_4{s} \rceil$ 을 계산하는 문제.

대략 첫 비트 외의 나머지가 모두 0인 경우와, 하나라도 1이 있는 경우만 나눈 다음 String의 길이를 이용하여 세면 된다.

#include <bits/stdc++.h>
using namespace std;
 
string str;
int zeros, ones;
int main()
{
	cin >> str;
	int ans = 0;
	int s = str.length();
	for (int i = s-1; i>0; i--)
	{
		int u = s-1-i;
		if (u%2==0)
			ans++;
		if (str[i] == '0')
			zeros++;
		else
			ones++;
	}
	if (ones>0 && str[0] == '1')
		ans += (s%2==1);
	cout << ans;
}

---

B. Mislove Has Lost an Array

조금만 생각해 보면 array 안의 모든 수는 $2^t$ 형태임을 알 수 있다. $l$개의 서로 다른 수가 있으면서 합이 최소인 배열은 1이 최대한 많고 2, 4, ... $2^{l-1}$ 이 하나씩 있는 경우고, $r$개의 서로 다른 수가 있으면서 합이 최대인 배열은 1, 2, ... $2^{r-2}$ 까지가 하나씩 있고 나머지 전부가 $2^{r-1}$ 로 가득 차 있는 배열이 최대.

#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define int ll
int n, l, r;
vector <int> maxarr;
vector <int> minarr;
int minsum, maxsum;
int32_t main()
{
	cin >> n >> l >> r;
	for (int i = 0; i<l; i++)
		minarr.push_back((1LL<<i));
	for (int i = l; i<n; i++)
		minarr.push_back((1LL));
	for (int i = 0; i<r; i++)
		maxarr.push_back((1LL<<i));
	for (int i = r; i<n; i++)
		maxarr.push_back((1LL<<(r-1)));
	for (auto it:minarr)
		minsum += it;
	for (auto it:maxarr)
		maxsum += it;
	cout << minsum << ' ' << maxsum;
}

---

C. Anna, Svyatoslav and Maps

방향 그래프가 주어지고, path 가 하나 주어진다.

이때, path를 정보를 잃지 않으면서 최대한 압축해야 하는데 (원문에서는 subsequence 같은걸로 잘 정의했지만 결과적으로는 압축하라는 말이라서, 내가 이해한 대로 쓰려고 한다), 

path $p$ 가 $a \to \dots \to b$ 일 때, 이걸 $a \to b$ 로 압축할 수 있으려면, 압축하기 전의 path가 $a \to b$ 로 가는 최단 경로 중 하나여야 한다. (즉, 압축된 결과물만 보고 path를 복원할 때, "최단 거리만 따라 가면서" path를 복원할 수 있어야 한다. 이때, 최단 경로가 둘 이상 있을때 그중 하나인 것은 상관이 없다). 정확히는, path $a \to b$ 를 복원할 때, 반드시 "최단 경로 중 하나" 만 을 택한다고 가정하고 이때 원래의 path가 복원되어 나올 확률이 0이 아니면 된다.

 

점이 100개 밖에 없으므로, 일단 Floyd-Warshall 같은걸로 모든 점간의 최단 거리를 구하자. 그다음, 그리디하게 path의 1번 점부터 시작해서, 최대한 압축해서 어디까지 한번에 압축할 수 있는지 찾고, 그다음 압축을 찾고 .... 하면서 매 순간 최대한 많이 압축한 다음 마지막에 path의 마지막 점을 넣어주면 끝.

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define INF 987654321
int graph[120][120];
int dist[120][120];
int path[1010101];
int n, m;
vector <int> goodsub;
void Floyd_Warshall()
{
	for (int i = 1; i<=n; i++)
		for (int j = 1; j<=n; j++)
			for (int k = 1; k<=n; k++)
				dist[j][k] = min(dist[j][k],dist[j][i]+dist[i][k]);
}

int main()
{
	scanf("%d",&n);
	for (int i = 1; i<=n; i++)
		for (int j = 1; j<=n; j++)
			scanf("%1d",&graph[i][j]);
	for (int i = 0; i<120; i++)
	{
		for (int j = 0; j<120; j++)
			dist[i][j] = INF;
		dist[i][i] = 0;
	}
	for (int i = 0; i<120; i++)
		for (int j = 0; j<120; j++)
			if (graph[i][j])
				dist[i][j] = 1;
	Floyd_Warshall();
	scanf("%d",&m);
	for (int i = 1; i<=m; i++)
		scanf("%d",path+i);
	goodsub.push_back(1);
	while(goodsub.back()!=m)
	{
		int curback = goodsub.back();
		int rstart = min(curback+n,m);
		while(dist[path[curback]][path[rstart]]!=(rstart-curback))
			rstart--;
		goodsub.push_back(rstart);
	}
	printf("%d\n",(int)goodsub.size());
	for (auto it:goodsub)
		printf("%d ",path[it]);
}

---

D번 : String 문제인데 1시간 반 생각해서 짠 코드가 바로 반례 생기고 예제도 안나오고... 하튼 던졌다.

E번 : 998244853 을 모듈러로 준 세터의 인성(?) 논란이 있었다가, "문제를 똑바로 읽었어야 하는게 맞다" 라는 의견으로 세터를 옹호하는 사람도 있었고 하튼 그랬는데 세터가 스스로의 인성을 보여주며 자폭했다.

나는 첨에 저 모듈러를 보고 FFT 솔루션을 막으려는게 아닐까 싶었는데, 뭐 그렇게 생각하는 사람도 있는것 같았다. 이게 FFT 문제인지는 사실 잘 모르겠고...

여튼 문제 자체는 꽤 멋진거 같았는데, dp를 이용해서 조건을 만족하는 Array의 개수를 세는? 느낌의 문제였다. 언젠가 업솔빙해야지.

---

다음 Educational Round에서 블루 복귀할 가능성이 높긴 한데 (...) 아무튼 :dhk: