Codeforces Round #656 (Div. 3) 가상 참가 후기

1학기 조별과제, 계절학기, 기타 등등 이런저런 사정으로 인해 거의 세 달 가까이 코포를 하지 못했다. 그래서 내 실력이 얼마나 늘었는지, 또는 늘기는 했는지 알아보기 위해 대회에 가상으로 참여해 보기로 했다. 코드포스의 대회에 Virtual Participation을 신청하면 실시간처럼 대회에 참여할 수 있다. 물론 이미 끝난 대회만 가능하다.

 

대회는 내가 가장 많이 참여했던 Div.3을 선택했다.

Dashboard - Codeforces Round #656 (Div. 3) - Codeforces

---

A. Three Pairwise Maximums

 

$x, y, z$가 주어질 때, $x = max(a, ~b), ~y = max(a,~ c), ~z = max(b, ~c)$를 만족시키는 $a, b, c$를 찾으시오. 

코드포스의 전형적인 '아무거나 찾으시오' 문제이다. 이럴 때는 가장 쉬운 답을 찾으면 된다. 그런데 나는 $x,~y,~z$를 논리적으로 비교하면 뭔가 답이 나올 것 같아서 열심히 관계식을 짜 봤는데.. 쉽지 않다. 역시 제일 쉬운 답을 찾는게 빠르다.

 

답을 찾기 위해 다음의 배열 arr를 선언한다.

$$arr = \{x,~y,~z,~max(x,~y,~z), max(1,~min(x,~y,~z)-1)\}$$

대충 가능해 보이는 값들을 전부 모은 배열이다. 마지막 원소는 원래 $min(x,~y,~z)-1$을 의미하는데, 이 값이 0이 되는 문제가 있어서 조금 수정했다. 이거 때문에 한 번 틀렸다.

 

그런 다음 $arr$의 모든 순열을 구하여, 앞의 세 값이 $a,~b,~c$가 될 수 있는지 확인하면 된다. 어떠한 경우에도 답이 안 나온다면 NO를 출력하면 된다. 

 

아이디어를 너무 늦게 떠올렸다. 오답 페널티를 감안해도 10분 걸린 건데, 이런 건 5분 안에 풀고 넘어갈 수 있어야 한다.

B. Restore the Permutation by Merger

주어진 조건에 따라, 수열 $a$에서 길이가 $n$인 순열 $p$를 찾으시오. $p$는 항상 유일하게 존재한다.

순열 $p$는 $1$부터 $n$까지의 수를 한 번씩만 사용하여 만든 수열이다. 따라서 $a$에는 $1$부터 $n$까지의 자연수가 각각 두 번씩 나타난다. $a$의 모든 값$(cur)$에 대해 다음을 수행한다.

 

1. $cur$을 이미 찾았다면 아래를 건너뛴다.
2. $cur$의 뒤에 $cur$과 같은 값이 등장하는 위치를 $loc$이라고 하자. 등장하지 않는다면 아래를 건너뛴다.
3. $cur$의 위치부터 $loc$ 이전까지의 각 값$(it)$이 $p$에 등장한 적이 없다면 $it$을 $p$에 추가하고, 이미 등장했다면 추가하지 않는다.

수열 $a$는 순열 $p$의 복사본 $p1$, $p2$로부터 만들어졌다. 이때 같은 복사본에 속하는 값끼리는 순서를 지키도록 했기 때문에 위의 알고리즘이 성립한다. 예제의 두 번째 테스트 케이스를 생각해 보자.

$$ 1~3~1~ 4~ 3~ 4~ 2~ 2 $$

두 개의 $1$ 사이에 존재하는 $3$은 $p$에서 $1$의 바로 뒤에 위치해야만 한다. 그렇지 않으면 $a$를 위처럼 만들 수 없다. 마찬가지로 두 개의 $3$ 사이에 존재하는 $4$는 $p$에서 $3$의 바로 뒤에 존재해야 한다. $1$은 이미 앞에서 처리했기 때문에 중복해서 추가하면 안 된다.

 

발상이 어렵지 않았다. 아직까지는.

C. Make It Good

수열 $a$에서, 앞에서부터 몇 개의 원소를 제거하여 좋은 수열 $b$를 만들고자 한다. 원소를 최소한 몇 개 제거해야 하는가?

$b$로부터 $c$를 만들 때 원소를 맨 앞 또는 맨 뒤에서 취하므로, $b$는 대략 이런 산봉우리 모양이 되어야 한다. 

인스턴트 그림

증가 또는 감소하는 도중에 같은 값이 연속해서 존재해도 된다. 백준에도 바이토닉 수열이라고 해서 비슷한 문제가 존재한다. 단 백준에서는 단조 증가하다가 단조 감소해야 한다.

 

어쨌든 $a$에서 앞의 몇 개를 지우고 남은 수열이 산봉우리 모양이어야 한다. 그럼 뒤에서부터 보면 된다. 뒤에서부터 산봉우리 모양이 유지되는 최대의 길이 $len$을 찾으면 정답은 $n-len$으로 쉽게 구할 수 있다.

 

# 사실 한 번 틀렸다

앞에서부터 찾으면 최대 $O(N^2)$로 시간 초과가 난다. 이런 실수가 제일 기분 나쁜데.

D. a-Good String

주어진 문자열 $s$를 a-Good string으로 만들기 위해 최소 몇 번 연산해야 하는가?

어떤 문자열이 $c$-good한지는 재귀 탐색으로 쉽게 판단할 수 있다. 따라서 문자열을 'a'-good으로 만드는 데 필요한 연산의 최소 횟수 역시 재귀적으로 구할 수 있다. 문자열 s가 $c$-good한지 판단하는 함수 $solve(c,~s)$를 다음과 같이 정의한다.

1. $s$의 길이가 1일 때, 구하는 값은 $s[0] = c$이면 $0$, 아니면 $1$이다.
2. $s$의 길이가 1보다 크다면, 두 번째 조건 또는 세 번째 조건을 만족하도록 하기 위해 필요한 연산의 최솟값 중 더 작은 값을 찾으면 된다.

그런데 구현에 문제가 있나.. 왜 예제조차 틀리지?

 

결국 D는 못 풀었다. 사실 평소대로 대회가 시작했다면 딱 한 시간 된 이때쯤 끄고 잔다. 

 

# 틀린 이유

두 번째 조건을 만족하려면 s의 왼쪽 절반을 모두 c로 바꿔야 한다. 마찬가지로 세 번째 조건을 만족하려면 s의 오른쪽 절반을 모두 c로 바꿔야 한다. 그런데 나는 왼쪽 절반과 오른쪽 절반 모두 solve를 호출했으니 틀릴 수밖에 없다. 시간이 조금 더 있었으면 맞혔을 지도 모른다..라는 희망을 가져 본다.

---

예상 레이팅 변화 -69점

오랜만에 해서 그런지 실수가 잦았다. D에 유효 슈팅을 몇 번 날리긴 했다는 점에서 만족해야 할 듯. 5월의 나는 C번까지 겨우 풀고 잤으니 조금이나마 발전했다고 할 수 있..겠지?

 

당분간은 Div. 3이 없는 것 같던데. Div. 2를 해 봐야 하나?