Codeforces Round #648 (Div. 2)

복기를 안할 수가 없다. 물론 Div2이기는 해도 Only Div2이고, 2등은 정말 말도 안되는 결과라고 생각한다. 1년 가량 주변에서는 쭉쭉 오르는데 코포 레이팅 변화가 크게 없어서 굉장히 불안했었다. 이는 Me in PS에서도 몇 번 언급을 했었다. 그런데 뭔가 불안했던 마음이 싹 사라지는 엄청난 코포였다.

A . Matrix Game

어떤 가로줄이나 세로줄에 하나라도 놓여져 있으면 그 줄은 아예 못쓰고, 하나도 안 놓여져 있으면 전체 중 아무데나 놓을 수 있다. 여기서 좀 더 생각해보면, 게임의 어떤 상황에서도 놓을 수 있는 위치들을 모으면 직사각형 모양과 동치라는 것이다. 남은 각 줄에도 딱 한번씩만 놓을 수 있기 때문에 직사각형 모양에서 더 짧은 변의 길이의 홀짝성에 따라 달라진다. 결론적으로 1이 하나도 없는 가로줄의 수와 세로줄의 수를 각각 세서 더 작은 값이 홀수인지 짝수인지 보면 된다. 

생각보다 관찰을 하는게 쉽지는 않은 문제였고, 그래도 10초 남기고 5분대에 푸는 데 성공했다. 00:05

B . Trouble Sort

배열을 정렬하는데 각 숫자에 색깔이 칠해져 있다. 정렬을 하는 시행은 서로 색이 다를 때만 두 숫자를 교환할 수 있다. 이때 전체배열을 정렬할 수 있는 문제이다.

생각을 해보자. 빨간색이 하나만 있으면 모든 파란색과 무한대로 계속해서 교체를 할 수 있다. 이는 색깔이 반대여도 똑같이 적용이 가능하다. 따라서 빨간색과 파란색이 하나씩만 있으면 무조건 정렬이 가능하다. 따라서 전체가 같은 색깔인지 확인하고, 이때 이미 정렬되어 있는 상태인지만 알면 된다. 

문제보자마자 막 바꾸는 것에 대한 생각이 바로 떠올랐고, 이게 가능한지는 생각도 안하고 될거라는 확신을 가지고 바로 달렸다. 결과는 3분 컷 00:08

C . Rotation Matching

두 개의 배열이 있을때 배열을 잘 돌려서 위와 아래의 값이 최대 몇개까지 똑같게 만들 수 있는지 구하시오. 각 배열은 1~N개의 숫자가 한번씩 있다.

각 배열에는 숫자가 한개씩 있기 때문에 딱 한 번씩만 매칭이 된다. 따라서 어떤 숫자에 대해서 몇 번 돌려야 하는지 구할 수 있다. 이를 종합하면 몇 번 돌렸을 때 몇 개의 숫자가 매칭되는 지 알 수 있고, 따라서 그중 최댓값을 구하면 된다. 

그냥 되게 무난하게 쉬운 문제였다고 생각했다. 딱히 생각하는데 어렵지도 않았다. 6분만에 풀었다. 00:14

E . Maximum Subsequence Value 

$max(1,k-2)$ 개의 숫자에 대해서 비트가 켜져 있어야 한다. 
여기서 굉장히 핵심적이면서도 중요한 관찰을 해보자. 3개를 잡아서 그 3개의 어떤 숫자도 켜져있지 않은 비트를 생각해보자. 이 상태에서 어떤 값을 추가해도 2개에 대해서 비트가 켜지지 않는다. 말을 좀 이상하게 했지만 핵심은 3개를 골랐을 때의 값보다 이때 한개를 더 골랐을 때의 값이 절대로 커질수 없다라는 것이다. 따라서 삼중포문을 돌면서 세개의 or값의 최댓값을 고르면 된다.

E가 더 많이 풀려있었길래, (8>6) E를 먼저 봤다. 뭔가 어디서 봤던 것 같은 느낌, 굉장히 익숙한 느낌이라 바로 보였다. "굳이 더 하지 안하는게 이득이다."라는 것은 코포에서 많이 나온다. 문제 해석에서 좀 시간이 오래 걸렸고, N이 100000인줄 알고 시간이 더 걸렸다. 그래도 10분밖에 안걸렸다. 00:24. 순식간에 4등으로 뛰어올랐다. 이때 좀 기대가 되었지만, D 문제를 보고 그 마음이 좀 사라졌다. 

D . Solve The Maze

맵에 벽이 있고, 나쁜 사람이 있고, 착한 사람이 있다. 여기서 빈 칸에 벽을 더 추가해서 나쁜 사람은 아무도 n,m에 도달하지 못하고, 착한사람은 모두 도달하게 할 수 있는지를 판별하는 문제이다.

착한사람과 n,m을 묶어서 한 묶음으로 묶을 수 있으면 가능하다. 그 주위를 싹다 벽으로 채워버리면 되기 때문이다. 이때 그 묶음 안에 나쁜 사람이 있거나 한칸 옆에 나쁜 사람이 있으면 벽을 놓을 수가 없기 때문이다. 다르게 생각하면 나쁜 사람 주위 4칸을 막아놓으면 나쁜 사람은 절대 도달할 수 없으므로 남은 모든 착한 사람이 도달할 수 있는지만 확인하면 된다. 이 과정은 기본 맵에 전처리를 해놓고 dfs 한번을 돌려서 끝낼 수 있다. 시간 복잡도는 $O(TN^2)$

이 문제도 관찰이 좀 어려웠다. 그리고 시간복잡도가 너무 남아돌아서 내 풀이가 맞는지에 대한 불안감도 있었다. 하지만 풀이가 굉장히 좋다고 생각해서 바로 짜서 냈다. 사실 좀 많이 흥분된 상태였기 때문에 내 풀이가 맞는지의 여부는 상관이 없었다. D를 못풀어서 200밑으로 쭉 떨어졌었는데, 그래도 60등 정도까지 끌어올렸다. 22분 사용 00:46

F . Swaps Again

두 개의 배열이 존재할 때, n/2 개 이하의 prefix를 잡고, 같은 길이의 suffix를 잡아서 둘을 바꾸는 작업을 한다. 이때 두 배열이 같아질 수 있는지를 판단하는 문제이다.

문제를 보자마자 a,b,c,d,e 를 적었다. 그리고 c는 일단 고정이라는 사실을 깨달았다. 그 다음 계속 시행을 하다보니까 깨달았다. 중앙을 중심으로 a,e가 한쌍으로 움직이고 b,d가 한쌍으로 움직인다. 또한 쌍 끼리는 자유로운 배치가 가능하다. 따라서 두개의 배열에서 n/2개의 쌍을 만들어서 그 쌍들의 집합이 같은지를 비교하면 된다. 하나하나 비교하기에는 $O(N^3)$의 시간복잡도가 너무 불안해서 정렬을 해서 푸는 방식을 사용하였다.

진짜 고민 안했다. a,b,c,d,e 3번쯤 바꿔보고 위의 성질들을 파악하였다. 사실 파악했다고 하기 보다는 그럴것이라고 추측을 했을 뿐이다. 그냥 강하게 밀어붙였고, 생각대로 되었다. 풀고나니까 12등이었다. 11분 사용 00:57. 굉장히 흥분되었다. 12등은 처음 경험하는 수치였고, 조금 지났음에도 내 점수를 따라 잡을 수 없었다. G는 아예 안풀리고 있었기 때문에, 이대로 가고 시스페일만 안 당하면 12등으로 굉장히 행복하게 마무리 할 것이라고 생각했다.

G . Secure Password

일단 인터렉티브에 한번 겁을 먹었다. 1~n의 모든 i에 대하여 i을 제외한 aj들의 곱을 각각 구해야 하는 문제이다. 인터렉티브였고, 13번이하의 질문을 통해 1000 이하의 n에 대해서 풀어야 한다.

일단 2^13을 생각할 수 있다. 그래서 비트로 나누는 것을 생각했다. 문제의 핵심 부분은 i를 질문 안한 경우에 질문한 모든 숫자의 합집합은 i를 제외한 모든 숫자여야 한다.  ans[i]= i를 질문 하지 않았을 때의 값의 모두 bit or을 취한 값으로 하면 된다. 같은 숫자를 여러번 bit or하는 것은 상관 없기 때문에 결국 적당히 잘 물어봐서 i를 안물어 봤을 때 적당히 나누어서 나머지를 다 물어봐야 한다는 것이다. 

하지만 비트로 나눠서는 이 문제를 해결할 수가 없었다. 어떤 수는 10번넘게 질문을 하는 숫자에 포함되는데, 어떤 숫자는 1번밖에 포함이 안되기도 한다. 핵심은 어떤 숫자도 약 절반 정도의 질문 횟수에만 포함되어야 하며, 어떤 임의의 두 숫자 쌍도 포함되고, 안포함되는 것이 13번 모두 동일하면 안된다. 그래서 13C6을 생각했다. 12C6이 아슬아슬하게 1000이 안된다는 것을 알게 된 순간 이 풀이가 맞을거라는 강력한 직감이 들었다. 1000개의 숫자에 대해서 13개중 서로 다른 6개의 조합을 주고 그때만 포함이 되도록 하였다. 그리고 위에서 언급한 방법대로 해결하면 된다.

12등에서 거의 포기를 하고 다른 것을 하려고 했다. 그러기에는 12등과 2등의 차이가 너무커서 도전을 안해볼 수가 없었다. 처음에 비트로 짜고 내가 왜 틀렸는지 모르고 있다가 13C6이 떠오르자마자 바로 뚝딱해서 해결했다. 그러니까 말도 안되는 역대 최고 등수인 2등이 되어있었다. 1시간 5분이 걸렸다. 02:02. 2시간 짜리였으면 땅을 치고 후회하지 않았을까 싶다.

대회가 끝나고 엄청 긴장하며 전체 채점을 구경했다. 다행히 하나도 안틀려서 잘 마무리 될 수 있었다. 굉장히 행복하다. 결과는 2등 +297 현재 레이팅은 2270.