[Atcoder] ARC132 후기

앳코더 2000이 되니 rated contest가 ARC밖에 없어서(사실상 AGC는 한두달에 한번이니) 요즘 좀 심심했다. ABC도 각잡고 풀면 좋을텐데 rated가 아니다보니 난이도 2400 내외의 한두문제 보고 풀이 떠올리고 이정도 이상은 귀찮아서 안 하게 되더라. 아무튼 오늘 간만에 앳코더를 쳤고, 퍼포 2330정도로 나름 선방한 것 같다. 앳코더를 볼수록 생각하는 힘은 길러지는데 코딩은 점점 느려지는 것 같다 ㅋㅋ!

https://atcoder.jp/contests/arc132/tasks

A
두 배열 $R$, $C$가 주어진다. $i$번째 열에는 $R_i$개의 #이, $j$번째 행에는 $C_j$개의 #이 있도록 격자가 채워진다. 각 위치에 대해 #인지 아닌지 판별하는 문제다.

$i, j$가 주어졌을 때 $R_i+C_j$가 n보다 크면 #, 아니면 .을 찍으면 된다. 적당히 순서를 바꿔서 오름차순으로 놓는다 치면 삼각형 형태로 배열되어야 함이 자명하므로, 이를 떠올릴 수 있다.

B
순열을 뒤집거나 맨 앞에 있는 원소를 뒤로 보내서 정렬하기 위한 최소 연산횟수를 구하는 문제다.

결국 순열을 뒤집어서 뒤로 보내는 것은 뒤에걸 앞으로 가져오는 것과 같으므로, 결론적으로는 순열이 주어졌을때 양방향으로 돌리는 수행밖에 할 수 없다. 따라서 적당히 돌리고 뒤집어서 1 2 3 ...의 숫자들이 연속해야 한다. 1 2 3이 정방향일때, 역방향일 때를 나누고 돌리고 뒤집을 건지 뒤집고 돌릴 건지 등을 잘 생각하면 4가지 케이스를 처리하면 충분.

C
순열 $P_i$에 대해 $|i-P_i| \leq d$를 만족하도록 순열의 빈칸을 채우는 경우의 수를 구하는 문제다. $d$가 5로 작다.

각 숫자를 기준으로 최대 양옆 $d$개, 총 $2d+1$개의 후보 중에 하나를 고를 수 있으므로 이 중에서 고른 것을 $1$, 안 고른 것을 $0$으로 나타내면 $2^{2d+1}N$개의 상태가 나오고, 이러한 dp table을 채울 수 있다.

나는 답을 찍을 때 필요한 비트를 만드는 걸 실수해서 디버깅으로 20분정도 날렸다... 이번 대회에서 제일 뼈아팠던 부분.

D
총 $M$개의 $1$과 $N$개의 $0$으로 이루어진 두 문자열 $s, t$가 있다. 인접한 문자만 바꿔 최소 횟수로 $s$를 $t$로 바꿀 때 그 과정에 있을 수 있는 문자열들을 $s$와 $t$ 사이에 있다고 하자. $s, t$ 사이의 문자열 중 인접한 두 문자가 같은 개수의 최대는?

각 $1$들의 위치를 생각해보면, 결국 $s$와 $t$에서 $1$이 등장하는 순서대로 매칭이 되야 함을 알 수 있다. 이 사실에 입각하면, 결국 $s$에서 $i$번째 $1$의 위치를 $ps_i$, $t$에서 $i$번째 $1$의 위치를 $pt_i$라 하면 $s$와 $t$ 사이의 문자열은 $i$번째 $1$이 $[ps_i, pt_i]$ (또는 $[pt_i, ps_i]$)에 있어야 한다. 이 때 $i$번째 $1$의 위치에 $i$를 뺀다고 생각하면, 어떤 두 $1$의 위치가 같은 숫자일 때 두 $1$은 인접하다. 따라서 이 문제는 $M$개의 구간에 대해 최소 개수의 점으로 임의 구간에 대해 적어도 하나의 점을 포함시키도록 하는 문제와 동일하다. 그리고 이는 시작과 끝점이 모두 단조증가하도록 정렬되어있기 때문에 그냥 간단한 그리디(시작점이 빠른 것부터 골라 더 이상 겹치지 않을 때 새로운 점 형성)로 풀 수 있다. 이를 적용하면 $O(N+M)$에 문제를 풀 수 있게 된다.

다만 여기서 주의할 점은, $1$이 맨 처음에 나타날 때나 맨 끝에 나타날 때 총 인접한 두 문자가 같은 개수를 세는 방법이 달라진다. 모두 포함 안 할 때, 한 쪽만 포함할 때, 양 쪽 다 포함 할 때 총 4개의 경우로 나누어 비슷한 그리디를 반복해주면 된다.

여담으로 모두 0이거나 모두 1일때 예외처리를 안 해서 한 번 틀렸다.

E는 그냥 하면 될 것 같았는데 난이도나 솔브수를 보니 내가 문제를 잘못 이해한 듯 싶었다.

나도 빨리 2600에서 2800짜리 문제도 대회시간에 푸는 고수가 되고 싶다. 후기 끝.