Codeforces Round #767 (Div.2)

어느덧 코포를 시작한지도 열 달, 26번째 코포를 치르게 되었다. 6개월 가까이 블루-퍼플을 반복하며 많이 지친 상태였고, IOI 국대 선발고사 전날이라 할지말지 많은 고민을 했다. 그래도 선발고사가 아침이 아닌 낮 1시에 시작하고, 방학 이후로 한 번도 빠지지 않고 제 시간에 코포를 했던 기록도 깨고 싶지 않아서 참여하게 되었는데, 안 했으면 후회했을만한 기록이 나왔다. 그래서 평소에 안 쓰던 코포 후기를 써보려고 한다.

Codeforces Round #767 (Div.2) 스코어보드

결과 : 7문제 중 6솔, 전체 7등(Carrot 기준 퍼포 2679, 델타 +210)

레이팅 변화 : 1878 -> 2088

 

이 날은 딥1이 함께 있는 날이어서 언레로 참여하는 오렌지 이상의 유저들과 레이티드 퍼플 유저들이 모두 딥1으로 갔고, 이에 따라 딥2에는 블루 이하만 남게 되었다. (이것도 좋은 성적을 기록하는데 한 몫을 한 것 같다.)

또한 평소에 항상 붙어다니는 수식어가 '구현장애'인 나에게 거짓말처럼 구현이 복잡한 문제는 단 한 문제도 나오지 않았다. D에서 1번의 WA, F1에서 3번의 WA를 제외하면 모두 Accepted일 정도로 구현 컨디션도 좋았다. 평소에 구현을 잘하는 친구들이 부러웠는데, 머리 속에 있는 것이 쉽게 코드로 나온다는 것이 어떤 기분인지 조금이나마 이해할 수 있었던 시험이었다. 이 덕분에 많은 문제를 풂과 더불어 더 빨리 풀어서, 수많은 6솔 중에서도 1등을 차지하게 되었다.

이 시험이 끝난 후 생전 받아보지 못한 코포 DM도 많이 받았고, 여러모로 신기한 경험을 많이 했다. 이 글을 쓰고 있는 지금은 IOI 국대 선발고사를 망친 후지만, 이 시험으로 약간의 위안을 삼고 있다. 문제에 대한 나의 접근 방식과 풀이는 아래에 적어두겠다.

 

문제

 

A - Download More RAM

램 등 하드웨어에 대한 용어를 잘 몰라서 문제를 맞게 해석한건지 모르겠다. 해석한대로 설명하자면

현재 램이 주어지고, 여러 소프트웨어가 주어진다. 소프트웨어는 현재 램이 a[i] 이상이어야 돌아가며, 램을 b[i]만큼 늘려준다. 이때 소프트웨어들을 통해 램을 최대로 확장했을 때, 이 값을 구하는 문제이다.

 

풀이)

a[i]를 기준으로 오름차순 정렬 후 앞에서부터 보면서 램을 확장할 수 있으면 하고, 없으면 break한다.

소프트웨어를 모두 확인하였거나 break한 시점의 램이 문제의 답이다.

(사실 break를 하지 않아도 되는데, 뭔가 하는 편이 직관적이어서 나는 하는 편으로 짰다.)

이 문제를 풀 때에는 250등 쯤이었던 것 같다.

 

B - GCD Arrays

수열 L, L+1, ..., R에서 다음과 같은 작업을 반복한다 :

수열에서 임의로 두 원소를 제거하고, 두 원소의 곱을 추가한다.

이 때 이 작업을 K번 수열 전체의 gcd가 1보다 크도록 하는 것이 가능한지 판별하는 문제이다.

 

풀이)

만약 작업이 끝난 후 수열 전체의 gcd가 x이고 남아있는 수가 y개라면, 처음에 적어도 y개의 수는 x의 배수여야 한다.

반대로, 처음에 y개의 수가 x의 배수이면 그 y개의 수에다가 다른 수들을 곱해 x의 배수를 y개만 남길 수 있다.

따라서 최소 횟수로 수열 전체의 gcd가 1보다 크도록 하려면 L, L+1, ..., R에서 x의 배수가 가장 많은 x를 구해 없어져야 하는 수들의 개수를 세어주어야 한다. 여기서 x=2임이 자명하다. 따라서 L, L+1, ..., R에 있는 홀수의 개수는 O(1)에 구할 수 있고, 이 값을 K와 비교해주면 간단하게 해결할 수 있다.

반례는 수열의 전체 길이가 1일 때이다. 수열의 길이가 1일 때는 만약 그 값이 1이면 gcd가 1보다 커질 수 없으므로 NO, 그 외의 경우 YES를 출력해주면 된다.

이 문제는 60번째 쯤으로 풀었던 것 같다.

 

C - Meximum Array

Mex란 해당 수열에 등장하지 않는 가장 작은 음이 아닌 정수를 말한다. 예를 들어 (0, 0, 0, 2, 2, 2)의 Mex는 1이고, (0, 1, 2, 3, 4, 5)의 Mex는 6이다.

길이 20만 이하의 수열이 주어지고, 이 수열의 숫자들을 연속하도록 그룹으로 묶어, 그 그룹의 Mex로 대체한다. 예를 들어 수열 0, 1, 2, 3, 4를 (0, 1, 2) (3, 4)로 묶었다면 이 수열은 3 0이 된다.

이 때 바뀐 수열이 사전순으로 가장 크도록 만드는 문제이다.

 

풀이)

개인적으로 D, E보다 까다로웠던 문제인 것 같은데, 그리디라는 이유로 C에 배치된 것 같다.

우선 수열 전체의 Mex를 생각하고, 이 값을 key라고 하자. 수열 전체를 하나의 그룹으로 묶으면 새로 만든 수열의 첫 번째 원소가 key가 되므로, 가장 먼저 그룹으로 묶을 수열의 범위를 정할 때 Mex가 key보다 작으면 안된다.

또한 Mex가 key보다 커진 순간보다 더 많은 원소를 그룹으로 묶는다면, 뒤에 쓸 원소가 하나 사라지는 셈이므로 항상 손해라는 것을 알 수 있다. 따라서 우리는 Mex가 key가 되는 그 순간에 그룹을 묶을 것이며, 남은 수열들에 대해서도 새로 key값을 구해 이를 반복할 것이다. 하지만 key값을 매번 새로 구하면 1 1 1 1 1 1 ... 1 같은 수열이 주어졌을 때 시간복잡도가 O(N^2)이 된다.

이를 시간 안에 하기 위해 나는 set과 R[i]라는 배열을 만들었다. R[i]는 i가 수열에 마지막으로 등장하는 위치로, 만약 수열의 첫 위치부터 보다가 R[i]에 도달하면 그 이후에는 i가 나타나지 않는다는 이야기이므로 i가 기존 key값보다 작을 때 이를 갱신해줄 수 있다. 따라서 스위핑 중에 key값이 자동으로 갱신된다. 또한 Mex를 구하기 위해 set을 활용했는데, set에 0부터 key까지 다 넣고 나타나는 원소들을 erase해주며 set의 가장 앞 원소가 key가 될 때까지 반복했다. 하나의 그룹이 끝나 set을 갱신하는데에도 시간이 걸리기에, 0부터 key까지 다 들어있는 set을 하나 만들고 건드리지 않은 상태로 냅두어 O(1)에 갱신했다. set을 사용해서 시간복잡도는 O(NlogN)이 되며, set 없이 배열로도 할 수 있으나 어차피 시간 안에 들어오는거 구현을 쉽게 하는 편이 이득이라고 생각하여 set을 사용했다.

이 문제를 풀었을 때 20등 안쪽으로 들어왔다.

 

D - Peculiar Movie Preferences

영화의 장면들은 길이 3 이하의 영어 소문자 문자열로 표현된다. 우리는 어떤 장면들만 모아 영화를 만들었을 때, 이를 팰린드롬으로 만들고 싶다. 단, 장면들의 순서는 바뀌면 안된다. 예를 들어, ab xy ba라는 장면이 있으면 abba로 팰린드롬을 만들 수 있지만 ab bad라는 장면이 있으면 순서를 바꾸어 badab라는 팰린드롬을 만들 수 없다.

영화의 장면들이 주어졌을 때 팰린드롬을 만들 수 있는지 판단하는 문제이다.

 

풀이)

1글자 장면이 있다면 그 자체로 팰린드롬이기 때문에 항상 가능하다. 이제 2글자, 3글자 장면만 있을 때를 생각하자.

장면들을 쭉 이어붙인 단어들이 팰린드롬이 된다면, 그 장면들 중 가장 마지막 장면이 있을 것이다.

그 장면이 2글자일 때, 일반성을 잃지 않고 ba라고 하자. 그렇다면 시작하는 장면은 무조건 ab 또는 ab? 여야한다. 여기서 관찰해야하는 점은, ab 또는 ab?가 존재하면 abba, ab?ba로 곧바로 팰린드롬을 만들 수 있다는 점이다.

3글자일 때, 일반성을 잃지 않고 cba라고 하면 시작하는 장면은 ab 또는 abc 여야한다. 마찬가지로 곧바로 abcba, abccba로 팰린드롬을 만들 수 있다.

즉, 팰린드롬이 있다면, 항상 길이 6 이하의 팰린드롬이 존재한다는 것이 중요한 관찰인데, 개인적으로 이 관찰이 그렇게 어렵지 않았아서 C보다 쉬운 것 같다.

따라서 첫 장면부터 쭉 보면서 i번째 장면이 끝 장면일때, 앞에서 나왔던 장면들 중 시작 장면이 될 수 있는 장면들을 찾아주면 되고, 이는 각각 26*26 크기의 배열과 26*26*26 크기의 배열에 저장해주면 된다. i번째 장면이 두 글자라면 27개의 수만을, 3글자라면 2개의 수만을 확인해주면 된다. 이 때 i번째 장면을 확인하기 전 i번째 장면으로 시작하는 것도 기록을 해준다면 i번째 장면이 자체로 팰린드롬이 되는 경우도 자연스럽게 걸러진다.

이 문제에서 끝나는 장면이 ba일때 시작하는 장면이 ab?가 될 수 있음을 알고도 구현 시 실수로 고려하지 않아 한 번 틀렸다.

이 문제를 풀고 나서 10등 대에 진입했다.

 

E - Grid Xor

짝수인 N에 대해 N*N 2차원 배열이 있다. 이 배열의 각 칸에 대해 상하좌우 4개(모서리나 꼭짓점은 각각 3개, 2개)의 수들을 모두 XOR한 값이 주어진다. 이 때, 배열의 모든 값을 XOR한 값을 구하여라.

 

풀이)

이 문제에서 풀이는 정해져있다. 기존의 값들 중 일부를 적절히 추출하여, 해당 값들을 XOR하면 답이 될 것 같은 느낌이 마구 든다. 그렇다면 기존의 값들을 어떻게 골라야할까?

우선 이 문제는 체스판 색칠을 했을 때 검정색 칸은 흰색 칸들의 XOR 결과만 저장한다. 따라서 검정색 칸 몇 개를 골랐을 때, 모든 흰 칸에 대해 이웃한 검정색 칸 중 선택된 검정색 칸이 홀수 개가 되면 된다. 실제로는 모두 1개가 되도록 고르는 방법이 존재하며, 나도 특정 이론을 사용했다기보다는 실제로 표를 그려놓고 손으로 색칠하며 규칙을 찾았다.

빨간색 칸들이 선택된 검정색 칸들이다. 모든 흰색 칸들이 한 번씩만 세어짐을 알 수 있다.

따라서 이 점들에 해당하는 값들을 모두 XOR해주면 모든 흰색 칸들의 XOR을 알 수 있다.

또한 반대로 해주면 모든 검정색 칸들의 XOR도 있기 때문에 문제를 해결할 수 있다.

실제 코드는 입출력 제외 변수 선언 1줄과 반복문 2줄이 전부이다.

이 문제에서 다른 유저들이 생각보다 고전했다. F1을 먼저 풀고 E를 푸는 사람들도 있었고, F2까지 다 풀고도 E를 못푸는 사람들도 있었다. 대회 시작 후 정확히 1시간 2초 만에 문제를 해결했고, 다른 사람들이 고전한 문제를 20분 만에 풀어낸 대가로 실시간 3등의 자리를 차지하게 되었다.

 

F1 - Game on Sum (Easy Version)

A와 B가 게임을 한다. A는 N번에 걸쳐 0~K 사이의 실수를 부르면, B는 이를 점수에 더할지 뺄지를 결정한다. 이 때 N번 중 최소 M번을 더해야하며, A는 점수를 최대한 크게 만드는 것이 목표, B는 점수를 최대한 작게 만드는 것이 목표이다. A와 B는 실시간으로 점수가 어떻게 변했는지 알고 있고, 두 플레이어가 최선의 전략으로 게임을 할 때 게임의 최종점수를 구하는 문제이다. 우선 이 문제는 답이 q/p꼴의 유리수로 표현되기 때문에, x=qp*(mod 1e9+7)을 구해야한다.

N, M의 범위는 최대 2000이다.

 

풀이)

어려운 문제는 맞는 것 같다. 우선 이 문제에서 중요한 관찰은 2개 정도이다. 하나는 dp라는 것에 대한 관찰, 하나는 dp 식을 구성하는 것에 대한 관찰이다. 그 전에 간단한 관찰이 하나 필요한데, B는 최대 M번이 아니라 항상 M번을 더한다는 점이다. 점수를 최대한 작게 만드는 것이 목표이기에, M번 초과로 더할 이유가 없다.

 

1. 왜 dp인가?

처음에는 게임이론 쪽으로 문제를 접근해보려고 했으나, 도저히 감이 잡히지 않았다. dp라는 생각은 하지도 않고 있다가, 단순히 이 문제가 Hard Version이 존재하며, N, M의 범위가 2000이라는 점 때문에 억지로 dp를 끼워맞추기 시작했다. 끼워맞추다 보니 dp가 정해라는 사실을 알게 되었다.

dp[i][j]는 숫자를 i번 불렀고, 이 중 j번을 더했을 때 A가 '보장 가능한' 최대 점수이다. i번째 부른 수를 x라고 하자.

만약 i번째 숫자를 더했다면, dp[i][j]=dp[i-1][j-1]+x가 될 것이고,

i번째 숫자를 뺐다면, dp[i][j]=dp[i-1][j]-x가 될 것이다.

즉, 그 이전 상태를 그대로 활용할 수 있다. i번째 숫자를 부르기 전까지는 i번째 숫자가 그 이전 게임에 영향을 미치지 않기 때문이다.

 

2. dp배열을 어떻게 채울 것인가?

이 때 dp[i-1][j]가 dp[i-1][j-1]보다 큼은 dp의 정의에 따라 자명하다.

여기서 '보장 가능하다'는 것은 최악의 경우에도 그 이상의 점수를 만들 수 있어야하므로

dp[i][j]=min(dp[i-1][j-1]+x, dp[i-1][j]-x)이다. 이를 최대로 만드는 x는 두 값을 같게 만드는 경우임이 자명하다.

따라서 최종적으로, dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])/2가 된다. 식은 생각보다 매우 깔끔하게 나온다.

 

초깃값은 dp[i][0]=0, dp[i][i]=i*K이다.

즉, 초깃값은 모두 정수이고, 우리는 이 값들의 평균을 계산한다. 또한, 이 값들의 평균을 계산한 것을 토대로 다시 평균을 계산하므로, 계속 2로만 나누게 된다. 따라서 dp[i][j]는 항상 s/(2^r) 꼴로 표현된다. 두 dp값을 더할 때 통분하려면 분모가 그대로 있는 것보다는 2^r으로 표현되는 편이 낫다. 따라서 나는 각 dp값을 pair<ll,ll>={r,s}로 표현하였고, 이렇게 표현하면 통분이 훨씬 쉬워진다. 2로 나눌 때도 r++만 해주면 된다.

이렇게 해서 출력값을 구해주면 문제를 해결할 수 있다. 출력값을 구할 때 p*를 구하는 방법에는 유명한 테크닉이 있는데, 이 글을 읽는 분들 중 모르시는 분들도 계실 것 같아 적어본다. 정수론의 가장 기본적인 정리 중 페르마 소정리라는 정리가 있다. 페르마 소정리란 소수 p와 p의 배수가 아닌 정수 a에 대해 a^(p-1)==1(mod p)라는 것이다. 이 식을 통해 우리는 mod p에서 a의 잉여역수가 a^(p-2)임을 알 수 있고, 이는 분할정복을 이용한 거듭제곱을 통해 O(logP)에 구해줄 수 있다. 이 문제에서 오버플로우의 영향인지 초깃값의 잘못된 설정인지 아직 이유는 모르겠지만 약 20분간 맞왜틀을 했고, 시험이 6분 남은 1시간 54분에 이 문제를 풀며 6등으로 올라섰다. 대회가 끝나기 직전에 E만 못풀었던 사람이 E를 풀며 7등이 되었다.

 

F2 - Game on Sum (Hard Version)

F1과 같은 문제이며, N, M의 제한이 100만으로 늘었다. F1에서 풀었던 것처럼 2차원 dp가 불가능하다.

시간 부족의 이유로 이 문제를 풀지는 못했지만, 잠깐이나마 고민했던 아이디어에 대해 적어본다.

우선 dp식이 dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])/2로 표현되기 때문에, 이 식을 통해 계속해서 거슬러 올라갈 수 있다.

그렇다면 dp[i][j]는 2의 거듭제곱을 분모로 가지는 특정 유리수 a[k]들에 의해 a[0]*dp[1][0]+a[1]*dp[1][1]+...+a[j]*dp[j][j]로 표현될 수 있다. 이 계수 a[k]들이 어떻게 표현될지 정확히 계산해보지는 않았지만, N-M과 관련있는 식으로 모든 a[k]값을 O(M)에 계산할 수 있을 것 같다. 그렇다면 전체 답을 계산하는 것도 O(M)에 해결할 수 있으므로 시간복잡도는 O(M)이 된다. N, M의 제한이 10만이나 20만이 아니라 100만인 것으로 보아 로그가 가능은 하겠지만 선형을 의도로 낸 문제였던 것 같다.