Educational Codeforces Round 174 (Div. 2)

문제 풀이

A. Was there an Array?

주어진 $b$로 $a$를 구성하지 못하는 유일한 경우는 $b$가 부분 수열 $[1,0,1]$ 을 포함할때가 유일하다는 것을 관찰하면 된다.

B. Set of Strangers

최악의 경우에도 어떤색 $c$를 다른 어떤색상$c'$로 변경하는데 2회의 행동이면 충분하다는 관찰이 중요하다. 이 행동 횟수를 $f(c)$라고 하자. 같은색으로 연결된 인접한 칸들의 그룹이 있다면, 그 그룹안에서 체스판 무늬처럼 색을 변경할 칸을 정한다고 생각하면 이해가 쉽다. 2회의 행동이 필요한 경우의 필요충분조건은 변경할 색상 $c$에 해당하는 그룹중 크기가 2 이상인 그룹이 최소 하나 존재하는 것이라는 것도 쉽게 보일 수 있다.

테이블위의 모든 원소를 한 색상 $c'$으로 통일해야하는데, 어떤 원소로 통일해야 할지는 최대의 $f$값을 가지는 색상으로 정하면 행동을 최대한 아낄 수 있다. 따라서 답은 $\sum_{i=1}^{nm}f(i) - f(c')$ 이다.

C. Beautiful Sequence

아름다운 수열은 첫 원소가 1이고, 마지막 원소가 3이고 그 중간의 원소들은 모두 2인 길이 3이상인 수열만 가능하다는 것을 관찰해야한다.

주어진 수열 $a$에서 한 아름다운 부분 수열을 구성할때, 첫 원소인 1과 마지막 원소인 3의 위치가 각각 $i,j (i<j)$로 주어졌을때, 가능한 경우의 수는 $x$가 수열 $a$에서 범위 $[i,j]$안의 2의 등장횟수라 하면, $2^x-1$라고 할 수 있다. (-1을 제한 이유는 2가 최소한 1개는 등장해야 하기 때문이다)

그러면 가능한 모든 $(i,j)$쌍에 대해서 경우의 수를 더해주어야 한다. 우선 수열 $a$를 왼쪽부터 오른쪽까지 읽을 것이다. 현재 바라보고 있는 인덱스를 $k$라고 하고, $1$이 존재해 시작된 부분수열이지만 아직 답에 기여되지 않은 경우의 수를 $sum$이라고 할 것이다. 매 $k$마다 다음을 수행한다:

• $a_k=1$인 경우: 미래에 완성될지도 모르는 새로운 부분수열이 시작되었다고 할 수 있다. 이 경우 $sum$에 1을 더한다.
• $a_k=2$인 경우: $k$보다 이전 인덱스에서 시작된 모든 부분수열에 2가 추가되는 경우이다. 이 경우 모든 부분수열을 구성하는 경우가 2배가 되기 때문에, $sum:=sum*2$를 수행한다.
• $a_k=3$인 경우: $k$보다 이전 인덱스에서 시작된 모든 부분수열에 대해서 끝나는 경우로 간주할 수 있다. 따라서 답에 $sum-cnt_k$를 하면 된다. $cnt_k$는 수열 $a$에서 $k$이전의 모든 1의 개수를 나타낸다. $cnt_k$를 제하는 이유는 2가 한번도 등장하지 않은 부분 수열 $[1,3]$은 아릅답지 않기 때문에 경우의 수에서 빼야하기 때문이다.

그냥 코드를 적는게 이해가 빠를 것 같긴한데… 어떻게 줄글로 풀어써보고 싶었다.

D. Palindrom Shuffle

우선 주어진 문자열 $s$에서 양끝이 회문인 경우가 있으면 문자열을 잘라준다($ababcba\rightarrow abc$ 와 같은 식으로). 이런 양끝 회문이 주어진 경우에는 회문을 구성하는 부분을 연산에서 제외하는게 항상 최적임은 자명하다.

그렇다면 이제 양끝이 회문이 아닌 $s'$가 남게 된다. 여기서 한번의 연산으로 $s'$을 회문으로 바꾸어야 하는데, 양끝이 회문이 아니기 때문에 $s'$의 왼쪽끝이나 오른쪽끝이 연산에 항상 포함됨을 쉽게 알 수 있다. $s'$에서 $[1,i]$ 범위안에 있는 알파벳 중복집합을 $ls_i$, $[i,n]$ 범위안에 있는 알파벳 중복집합을 $rs_i$ 라고 하자 ($n$은 $s'$의 길이).

만약 $ls_i \supset rs_{i+1}$ 라면, 연산을 통해 $[1,i]$ 범위의 문자열을 재배치해서 문자열 전체를 회문으로 만들 수 있음을 알 수 있다. 반대도 마찬가지이다.

$s'$의 중앙이 회문으로 구성되어 있는 경우($aabbac$와 같은 경우)는 고려해야할 연산이 한종류 더 존재한다. 중앙 회문이 존재한다면, 그 범위를 $[i,n-i+1]$ 이라고 하자. 중앙 회문의 왼쪽에 해당하는 범위 $[1,i-1]$, 오른쪽에 해당하는 범위 $[n-i+2,n]$ 에 존재하는 알파뱃 중복집합이 일치한다면 해당 중앙 회문이 답을 최적화하는데 도움이 될 수 있을 것이라고 생각해볼 수 있다 ($ls_{i-1}\equiv rs_{n-i+2}$).

위에 소개된 전략중 문자열 전체를 회문으로 만드는 제일 작은 범위의 연산을 사용하면 된다.

E. A, B, AB and BA

$A$, $B$는 자유롭게 배치할 수 있으므로, $AB$, $BA$를 최대한 많이 배치하는 문제로 환원하여 풀어보자. 그리디한 접근이 유효한데, 우선 AB를 그리디하게 배치하고, 남는 공간에 BA를 배치한다. 이때, 문제에서 주어진 $ab$, $ba$ 횟수는 고려하지 않는다.

그리고 우리는 $AB$를 배치했을때 $BA$를 배치하지 못하는 경우와 그 역이 존재하는 어떤 “회색지대”에 대한 생각을 해야한다. 구체화 해봤을때. 주어진 문자열 $s$중 $ABAB...$ 처럼 다른 문자열이 교차되는 경우가 해당하는 경우라고 볼 수 있다.

예를 들어 $ABAB$가 있다고 가정하자. 처음 $AB$를 그리디하게 배치했기 때문에, 다음과 같은 배치를 이룰 것이다:

그런데, 문제에서 주어진 $ab$수보다 $AB$를 더많이 배치한 경우가 존재할 수 있고, 주어진 $ba$수보다 $BA$를 덜 배치해서 $ba$를 활용하지 못하는 경우가 존재할 수 있다. 그래서 “최적”의 방법으로 $AB$배치를 $BA$배치로 변경하면서 yes를 출력할 수 있는지 확인할 것이다. 만약 위의 경우에 $BA$를 더 배치한다면 $A(BA)A$와 같은 배치가 될 것이다. 여기서 사용된 $AB$는 2회 줄어들었지만 $BA$배치는 1회 증가하였다.

어떤 배치변경이 최적일지는 케이스워크를 하면 보일 수 있다. 우선 다음과 같이 홀수 길이의 교차문자열을 고려해보자:

위의 경우에서는 $AB$를 한번 제외할때마다 $BA$를 배치할 수 있다는 것을 알 수 있다. 따라서 1:1 등가 교환이 가능한 경우이다. 그렇다면 짝수 길이의 교차문자열은 어떨까?

$A$로 시작하는 교차문자열은 $BA$를 하나 배치하기 위해서 $AB$하나를 추가로 “희생”해야 한다. $B$로 시작하는 교차문자열은 $BA$를 배치하기 위해 $AB$를 하나만 제거하면 되어 홀수 길이의 교차문자열과 같은 케이스처럼 보이지만, 해당 교차문자열을 전부 다 $BA$로 변경했을때 기존에 배치된 $AB$의 갯수보다 1개 더 보너스로 배치가 가능하다.

처음엔 $AB$우선적으로 배치했으니, 교환은 $BA$우선적으로 가능하도록 해보자. 우선순위는 다음과 같이 될 것이다:

1. $B$로 시작하는 짝수길이의 교차문자열, 길이가 짧을수록 우선순위가 높다. (보너스를 받는 시점이 빨리지기 때문이라고 생각하면 쉽다)
2. 홀수길이의 교차문자열
3. $A$로 시작하는 짝수길이의 교차문자열, 길이가 길수록 우선순위가 높다. ($AB$를 한번 “희생”했으면, 그 이후에는 교환비가 1:1이기 때문에 한번의 희생으로 최대한 많은 “등가교환”을 이루어내면 좋다)

이러한 교환을 우선순위큐와 같은 자료구조에 정렬하여 그리디하게 교환하면서 답을 구성할 수 있는 경우가 있는지 체크하면 된다.

F. Graph Inclusion

N/A

총평

D를 푸는데 너무 많은 시간이 걸렸다는 점에서 아쉬움이 남는다. 늦은 4솔~빠른4솔간에 엄청난 인원이 몰려있어 퍼포먼스를 꽤 높일 수 있는 기회였는데, 중앙 회문에 대한 케이스에 대한 구체화를 이상하게 해버려서 3틀을 해버렸다. 아쉽지만 실수만 줄이면 퍼포먼스 올라갈 룸이 더 많이 남았다고 긍정적으로 생각해보고 싶다.

E는 업솔브 해보니 내가 잘하는 유형은 아니였어서 한시간을 줬어도 풀지 못했을 것이라는 생각이다. 문제 퀄리티 자체는 꽤 마음에 들었다. E번 같은 유형에 강해진다면 CF 레이팅 올리는데 정말 도움되겠구나 하는 생각을 했다.