Pinely Round 2 (Div. 1+2)

2023년 8월 30일에 진행한 코드포스 파인리 2회 대회 일지입니다. 컨디션은 회복했는데 머리는 퇴화한 것 같습니다.
그나저나 이제부터는 풀이나 발상을 조금 더 자세히 써보려고 합니다…

0:00~0:04 (4분)

• A번 Channel을 잡았습니다.
• 발상 1(~1분): 모든 사람이 Online인 상황은 판정할 수 있습니다. 이런 상황이 한 번이라도 나온다면 모두가 게시글을 보았다는 것이 보장됩니다.
• 발상 2(~3분): 최초에 온라인이던 유저 수와 중간에 온라인이 된 (중복을 포함할 수도 있는) 유저 수의 합이 전체 유저 수보다 작으면 무조건 게시글을 보지 못한 누군가가 있음을 알 수 있습니다.
• 두 가지를 찾고 나머지 경우에 maybe를 출력하면 됩니다.
• 살짝 오래 걸린 것 같습니다.

0:04~0:11 (7분)

• B번 Split Sort를 잡았습니다.
• 발상 1(~3분): 수열을 증가하는 몇 개의 부분수열으로 나눈 뒤, 수열을 다시 정렬할 때마다 이 부분수열들이 하나씩 앞으로 오게 할 수 있습니다.
• 이를 구현했는데 틀렸습니다. 인덱스를 잘못 잡았습니다(0베 쓰는 것을 더 열심히 해야겠습니다..?)
• 그래서 1번 틀리고 맞았습니다.

0:11~0:19 (8분)

• C번 MEX Repetition을 잡았습니다.
• 발견(~2분): 예제 입출력 중 마지막 케이스를 보면, 입력에서 8만 7로 바꾼 뒤 시프트한 것이 답입니다. 이를 발견하고 나서 바로 그 원리와 무슨 숫자가 어떻게 바뀌는지(이런 게 없었다면 증명하지 않고 바로 풀이했을 것입니다)를 찾고자 했습니다.
• 발상 1(~4분): 주어지는 수는 0 이상 n 이하이므로, n+1개의 수 중 없는 수가 곧 MEX값입니다. 그렇게 되면 지금 막 없어진 값이 MEX값입니다.
• 발상 2(~5분): 주어진 수열의 맨 뒤에 MEX값을 push합시다. 최초 수열은 1부터 n까지고, 그 다음에 처음 수가 n+1째 수로 바뀌면 수열은 n+1 후 1부터 n-1까지입니다. 때문에 발견에서 제시한 시프트가 증명됩니다.
• 이를 구현했고 1번 틀리고 맞았습니다.

0:19~0:27 (7분)

• D번 Two-Colored Dominoes을 잡았습니다.
• 발상 1(~1분): L과 R은 항상 좌우로 있고, U와 D는 항상 위아래로 있습니다. 즉, L과 R은 각 행에서의 흰색/검은색 칸의 개수차를 조절할 수 없고, 비슷하게 U와 D는 열의 개수차를 조절할 수 없습니다.
• 발상 2(~3분): R과 D가 L과 U에 종속되어 있다고 봅시다. 왼쪽에서부터 가장 첫 번째로 L이 홀수 개 나오는 열에 대해, 해당 열을 흰/검의 수가 같도록 칠할 수 없습니다. U에 대해서도 마찬가지입니다.
• 발상 3(~4분): 발상 2에 의해, 각 행/열에는 U/L이 짝수 개 있습니다. 따라서 절반을 흰색, 절반을 검은색으로 칠하면 그 행/열의 U/L과 다음 행/열의 D/R이 모두 짝수개가 되어 채색이 가능합니다.
• 이를 구현했고 맞았습니다.

0:27~2:40

• E번 Speedrun을 잡았습니다.
• 뭔가 위상정렬도 시도했고 스위핑도 시도했고 방향 기반 양쪽 출발 DFS 뭐 그런 것도 시도해봤는데 결론적으로 못 풀었습니다.
• 발상 1: 처음 수행할 과제만 정하면 나머지 과제는 선형시간에 그리디하게 갖다가 붙일 수 있습니다.
• 처음 수행할 과제를 어떻게 고를지를 몰라서 못 풀었습니다.

후기

• 애드혹 발상 속도는 어느 정도 돌아온 것 같습니다. 사실 이정도 속도면 거의 최고 아웃풋이기도 하죠?
• 근데 그에 비해 E를 못 푼 게 좀 컸습니다. 사실 에디토리얼을 보면 E도 어느 정도 풀만한 문제였던 것 같긴 한데(절반 정도 발상했으니까 사실 그리 많이 가지는 못했죠), 좀 아쉽습니다.