CodeChef Starters 98 (Div. 4)

menborong님이 CodeChef가 괜찮다고 추천을 꾸준히 하셨는데, 학기 중에는 시간이 없어서 못 치고 이제야 첫 라운드에 도전했다. CodeChef 라운드는 큰 문제 셋을 적당히 쪼개서 Division 1~4로 나누어 운영되는 것 같다. 나는 첫 참가였기에 Div. 4에 배정되었다. menborong과 qjatn0120 선배가 본인들은 1등 했다고 주장하셔서 1등을 목표로 임했다. 제출에 의한 페널티가 없다고 해 제출은 막 했다.

 

P1. Messi vs Ronaldo (0:01) *316

브론즈 5 문제이다. 그냥 짜면 된다.

 

P2. FIND A and B (0:03) *802

각 수를 B에 대입하고 다른 두 수로 A를 만든 후 판별해주면 된다.

 

P3. Airport Management (0:14) *1201

최빈값을 찾으라는 문제이다. 4번이랑 동시에 봐서 조금 지연되었다.

 

P4. Ball Distribution (0:15) *1442

\(max(0,\sum{A_i} - n(m-1))\)이 답이다. 적당히 잘 찍어서 맞긴 했는데, 잘 생각해보면 증명을 할 수 있을 것 같다.

 

P5. 3-Blast Palindrome (0:23) *1699

길이가 4 이상이라면 3씩 줄여주는 것이 최적이다. 따라서 길이 1, 2, 3인 팰린드롬을 만들 수 있는지만 판별하면 된다.

\(N = 3k+1\)이라면 길이 1인 팰린드롬을 무조건 만들 수 있다. 길이가 2, 3인 팰린드롬의 존재 여부를 판별하는 것은 비교적 어려운데, 2인 경우에만 설명하자면 0-indexed 기준으로 \(s_i = s_j, i<j, i \equiv 0 \pmod{3}, j \equiv 1 \pmod{3}\)인 \(i,j\)를 찾으면 된다. 이는 문자와 3으로 나눈 나머지를 기준으로 DP처럼 저장해주면 배열을 훑으며 찾을 수 있다. 길이가 3인 경우에도 비슷하게 해주면 된다.

 

P6. Sub-Array With Maximum Sum (0:44) *2786

여기부터는 좀 어려웠다. Alice가 정할 인덱스를 정하면, 해당 인덱스 앞 뒤로는 일단 최적으로 배치한 뒤 해당 인덱스에 숫자를 넣는 두 케이스의 값을 구해 비교하면 된다. Kadane DP를 앞에서 하나, 뒤에서 하나 돌려놓은 뒤 케이스 워크를 열심히 하면 답을 구할 수 있다.

 

P7. Happiness (1:23) *2850

각자가 움직인 거리의 합이 \(M\)의 배수이면 된다. \(dp(i,j) = \) \(i\)번째 사람까지 봤을 때 움직인 거리의 합을 \(M\)으로 나눈 나머지가 \(j\)일 때의 최대 합으로 냅색을 돌려 주자. 각 사람당 움직일 수 있는 경우의 수가 \(M\)가지 이므로 \(O(NM^2)\)에 문제를 해결할 수 있다.

 

P8. Build Towers (1:47) *2688

https://www.acmicpc.net/problem/26079 와 사실상 똑같은 문제이다. 지문에 있는 minimum 부분을 보지 못해 시간을 많이 잡아먹었다. 깨닫고는 그냥 똑같이 짜서 AC를 받았다.

 

6~8번의 난이도는 아마 Div. 4 기준 솔브수가 다 5명 안쪽이라 저렇게 찍힌 것 같다. 솔직히 막 잘하진 않았는데 Div.4라 전체 우승을 차지할 수 있었다. Div.1 기준으로도 10등 안쪽인 것 같은데, 등수가 높게 찍히니 일단 기분은 좋다. Div. 4에서 짤린 Div. 1 뒷 문제들도 봤는데, 사이트 규모에 비해 문제도 전체적으로 괜찮은 편이라 놀랐다. 여유가 되면 아마 계속 칠 것 같다.