Codeforces Round #578 (Div.2) 후기/풀이

한국인 세터 라운드기도 하고, 시간도 평소처럼 밤이 아니라 9:35 ~ 11:35라서 바로 등록했다 :) 

E번 왜틀린지 모르겠다. 분명히 풀이는 맞았는데, 구현 실수를 결국 라운드 끝나고도 못 찾았다.

레이팅 : +39 (1800 -> 1839)

 

세터의 국적을 따라 문제에 등장하는 사람 이름은 Gildong과 Amugae 로 나왔다 ㅋㅋ

---

A. Hotelier

시키는 대로 구현하면 된다. L이 들어오면 왼쪽부터 빈방을 찾고, R이 들어오면 오른쪽부터 빈방 찾고... 

#include <bits/stdc++.h>
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

bool hotelroom[10];
string op;
int main()
{
	usecppio
	int n;
	cin >> n;
	cin >> op;
	for (auto it:op)
	{
		if (it=='L')
		{
			for (int i = 0; i<10; i++)
			{
				if (!hotelroom[i])
				{
					hotelroom[i] = 1;
					break;
				}
			}
		}
		else if (it=='R')
		{
			for (int i = 9; i>=0; i--)
			{
				if (!hotelroom[i])
				{
					hotelroom[i] = 1;
					break;
				}
			}
		}
		else if ('0' <= it && it <= '9')
			hotelroom[it-'0'] = 0;
	}

	for (int i = 0; i<10; i++)
		printf("%d",hotelroom[i]?1:0);
}

---

B. Block Adventure

1번부터 $n$번까지 블록들을 따라서 갈건데, 높이가 $k$ 이하만큼 차이나야 다음 블록더미로 점프할 수 있다.

가방에 블록을 넣어 놓을 수 있는 칸이 무한하며, 일단 되는대로 블록을 챙겨 놓으면 다음에 높이가 모자랄 때 쓸 수 있는 여지가 있으므로, 항상 $h[i+1]-k$ 개만 남기고 모든 블록을 일단 가방에 넣는 게 최선이고, 블록이 모자랄 때도 딱 저만큼만 써 가면서 블록을 최대한 많이 들고다니는게 최적임을 알 수 있다.

처음에 구현 실수로 지금 서 있는 블록 칸이 음수가 되었는데도 가방에 블록을 넣어버려서(...) 1틀. $\max$ 를 쓰려다가 실수로 $\min$을 써서 1틀 더했는데 다행히 Pretest 1에서 틀려서 안 깎였다.

#include <bits/stdc++.h>
#define ll long long
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
#define int ll
int n, m, k;
int h[120];
int32_t main()
{
	usecppio
	int tc;
	cin >> tc;
	while(tc--)
	{
		bool flag = true;
		cin >> n >> m >> k;
		memset(h,0,sizeof(h));
		for (int i = 1; i<=n; i++)
			cin >> h[i];
		for (int i = 1; i<n; i++)
		{
			int u = max(h[i+1]-k,0LL);
			if (u <= h[i])
			{
				m += (h[i]-u);
				h[i] = u;
			}
			else
			{
				if (h[i]+m >= u)
				{
					m -= (u-h[i]);
					h[i] = u;
				}
				else
				{
					flag = 0;
					break;
				}
			}
		}
		cout << (flag?"YES\n":"NO\n");
	}
}

---

C. Round Corridor

백준 슬랙에서도 그렇고, 많은 사람들이 습격자 초라기를 떠올린 문제. 나도 처음에 습격자 초라기랑 그림이 비슷해서 엄청 어려운 문제일줄 알고 쫄았는데, 그림만 비슷하게 생긴 문제다.

안쪽이 $n$칸, 바깥쪽이 $m$ 칸으로 나눠져 있는데, 여기서 어떤 두 칸을 서로 오갈 수 있는지 판정하는 문제.

어차피 안쪽과 바깥쪽의 벽이 둘 다 쳐져 있는 칸들 외에는 벽이 없는 것이나 다름없는데 (안쪽-바깥쪽을 왔다갔다하면서 마음대로 그 사이를 배회할 수 있다) 그러면 벽은 정확히 $\gcd(m, n)$ 개 남는다. 

이 벽들의 위치를 기준으로 방의 번호를 다시 매긴 다음 (0번부터 $g-1$번 까지), 쿼리가 들어올 때마다 같은 방에 있으면 OK, 다른 방에 있으면 갈 수 없다. 

#include <bits/stdc++.h>
#define ll long long
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
#define int ll
int n, m, g, q;
int32_t main()
{
	usecppio
	cin >> n >> m >> q;
	g = __gcd(m,n);
	int u = n/g;
	int v = m/g;
	while(q--)
	{
		int sx,sy,ex,ey;
		int a, b;
		cin >> sx >> sy >> ex >> ey;
		sy--; ey--;
		a = (sx==1)?(sy/u):(sy/v);
		b = (ex==1)?(ey/u):(ey/v);
		cout << (a==b?"YES\n":"NO\n");
	}
}

---

D. White Lines

$n \times n$ 정사각형 판에서 몇 칸이 검은색으로 칠해져 있고, '지우개' 를 한 번 쓰면 $k \times k$ 칸을 모두 흰색으로 밀어버릴 수 있다. 지우개를 한 번만 써서 최대한 많은 White line (줄 전체가 흰색인 행 또는 열) 의 수를 최대화하는 문제.

 

일단 열에 대해서도 똑같이 셀 수 있으니, 행에 대해서 세는 경우만 생각해 보자.

만약 어떤 행에서 가장 왼쪽과 오른쪽에 검은색이 나오는 index를 가지고 있다면, 어떤 임의의 칸 $(i, j)$ 에 지우개를 딱 찍었을 때 그 행이 white line이 되는지를 $O(1)$ 에 판정할 수 있다. 즉, $O(k)$ 에 한 번 지우개를 찍어 볼 수 있다.

이 행동을 $O((n-k)^2)$ 번 해야 하므로, 전체 시간 복잡도는 $O((n-k)^2 k)$ 로 시간 초과를 받는다. (최댓값이 대략 12억 정도길래 일단 pragma 붙이고 기도한번 해봤는데, 생각해보면 이걸 열에 대해서도 해야 하므로 2배가 되어 당연히 안 된다!)

 

생각해 보면, $(i, j)$ 에 위치한 박스를 아래로 한 칸 $(i+1, j)$ 로 밀 때 (행, 열 이므로 좌표가 일상에서 사용하는 것과 반대다), 이미 $k-1$행에 대해서는 연산이 끝난 상태이다. 즉 박스를 아래로 한 칸 밀때, 원래 위치에서 맨 위에 있는 행(즉, 박스에서 빠져나가는 행) 과, 새로 박스에 들어오는 행만 보면 되고, 그 사이는 이전 위치에서 white line이 되는지 이미 확인해 놓은 상태이므로 다시 확인할 필요가 없다.

 

그림으로 나타내면, 

이러한 박스 위치를 이미 계산했다고 하자. 즉, 이 때 3번, 4번, 5번째 행에 대해서 White line이 되는지를 이미 계산했다고 하자.

박스를 한 칸 내릴 때,

이렇게 내리면 분홍색 부분에 대한 정보는 이미 계산해 놓은 상태이므로, 앞에서 그냥 가져와주고 파란색으로 새로 칠해진 부분만 확인하면 된다. 즉 많아야 두 행만 보면 된다는 것이다.

 

이를 이용하면 필요한 정보를 memoization으로 줄일 수 있고, 한 번 밀 때마다 $O(1)$ 에 확인할 수 있으므로, 많아야 몇 번 정도만 $O(k)$ 에 처리하고 나면 행과 열에 대한 정보들을 따로따로 계산할 수 있어서 $O(n^2)$ 시간에 문제를 풀 수 있다.

 

코드 : https://codeforces.com/contest/1200/submission/58609147 

---

E. Compress Words

처음으로 KMP를 이용한 뭔가 "응용 문제" 를 풀어봤...다고 생각했는데, 틀렸다. 왜인지 잘 모르겠다;; 라운드 끝나고 나서 꽤 오래 생각해 봤지만 찾지 못했다.

 

대충 문제 요지는, 두 String을 합칠 때, 이전 String에서 최대한 많이 겹치는 부분만큼을 스킵하고 붙인다. 예를 들어

 

ABCDEF 와 DEFGHI를 붙일 때, ABCDEFGHI 로 붙인다.

 

이렇게 붙인 결과를 출력하는 문제인데, 지금까지 가져온 String에서 뒤에 일부를 뗀 다음 새로 들어올 String을 앞에 붙여서 같이 KMP의 실패함수를 돌려주면 (즉, 위 예시에서는 DEFGHI ABCDEF 를 놓고 실패함수를 돌린다) 나오는 결과값이 정확히 스킵해야 하는 문자의 개수가 되고, 그만큼 스킵해주면 된다.

 

근데 왜 안되지;;; :frozen_thinking:

 

처음에 해싱으로 풀 수 있을 것 같은데 소수를 어떻게 골라야 Hack을 안당하고 잘 해싱할 수 있을지 고민하다가 접고 다른 생각을 했었는데, 

dlwocks31 (재활해야한다더니 오렌지 복귀했다. :fan:) 에게 이런 문제에서 해싱을 안 뚫리게 랜덤으로 숫자를 골라서 해싱하면 된다는걸 배웠다. 끝나고 코드 볼 때 아니 왜 이사람은 해싱하는데 mt19937 랜덤을 뽑나 싶었는데, 특정 소수를 뚫는 데이터를 만들어 Hack하는 사람들로부터 안전하기 위해 매번 모듈러에 쓸 수를 mt19937 정밀랜덤으로 다시 뽑는 추한 고인물 :uwek: 테크닉을 배웠다. :uwek: 

---

E번 틀린건 아쉽지만 아무튼 +39점 받았다. D번같은 문제를 빠르게 생각해 낼 수 있어야 하는데, Naive에서 저걸 찾는데 꽤 오랜 시간이 걸렸다. 종이에 몇가지 예시를 써보면서 "어 왜 이 소문제를 여러번 풀고 있지?" 라는 생각을 해보는건 꽤 유효한 방법인 것 같다.