지지난주와 지난주에 KOI 1차와 SCSC Div.2를 봤다. 솔직히 조금 아쉽긴 했다. 어제 코포도 치니깐 -30 찍어서 조금 슬펐다. 그래도 PS 재활을 해보려고 하는데, 대회를 많이 쳐보는게 좋을 것 같다.
그래서 PPC 옾콘을 쳐보기로 했다! 수상은 솔직히 힘들거 같았지만, 열심히 한번 해보기로 했다. 닉네임은 포스틱으로 참가했다. (포스틱은 내가 먹을 수 있는 과자이다!)
금요일에 학원 끝나고 집에 가서 테트리스 돌리다가 잔 뒤로 일어나보니 1시가 약간 넘어있었다. 난 빠르게 노트북을 켜고 대회 창을 열었다.
대회 기록
우선 A번을 보았다. 매우 간단한 문제였는데 조건에 등호를 안붙여서 1번 틀렸다.
A AC (0:18, 1 WA)
그 다음에 B번을 보았다. cyclic shift를 한 후 몇개의 문자를 제거하여 부분문자열로 CPP을 가지게 못하는 문제였다. 나는 슬라이딩 윈도우마냥 "CPP"의 개수를 세어주고, 그 최소를 구하면 될거라고 생각하고 제출했지만 틀렸다.
문제를 다시 읽어보니 CCPPP 같은 경우에는 한번 제거한다고 CPP이 없어지지 않는다는 걸 깨닫고 PPC와 CPP 문제가 떠올라 일단 튀기로 했다.
B WA (0:27, 1 WA)
C번으로 넘어갔다. 순열을 구성하는 문제였는데, 적절히 바로 옆 칸끼리의 차이와 2칸 옆끼리의 차이를 이용하면 잘잘 구성할 수 있을 것 같았다. 약간 루날리티의 그 0.4% 문제가 연상됐다. 그런데 틀렸다! 그래서 내 구성이 어딘가 잘못되었을 거라 생각했고, 내가 문제를 잘못 읽었다는걸 깨달았다..
쿼리는 $A_l$ ~ $A_r$ 의 최대 - 최소를 반환하는 거였는데, 나는 $A_r$ - $A_l$의 절댓값인 줄 알았다.
그래서 다시 다른 방식으로 구성해봤는데, 또 틀렸다. 그 구성은 좀 말이 안되는거 같아서 다시 원래 구성 방식으로 돌아왔다.
그랬더니, 약간만 바꿔주면 잘 돌거같은거다!
C AC (1:25, 2 WA)
C에 시간을 너무 많이 박았다. (약 1시간)
이제 슥보를 까고, 슥보를 따라가기로 했다.
일단 E번을 봤다. 적당히 생각을 해보니, prefix max와 suffix max의 최솟값으로 잘 해주면 될 것 같았다.
E AC (1:35)
그리고 K번을 봤다. 대충 생각해보니까 1x1만 예외처리하고 홀짝으로 칸을 분리해서 같은 숫자가 있는지를 보면 될 것 같았다.
K AC (1:43)
많이 풀린 J번을 봤는데, 원소 값이 a일 때 같이 있을 수 있는 원소의 범위는 [0, 2a] 이기 때문에 min을 fix해놓고 적당히 경우의 수를 계산해주면 됐다.
J AC (1:54)
문제 이해가 잘 안됐는데, 그냥 1xn, mx1인 경우는 1개, 아닌 경우는 위 아래에 한줄씩 긋고 교차로 색을 놓으면 진짜 나무처럼? 트리를 구성할 수 있어서 쉽게 풀었다. 근데 배열 범위 잘못 잡아서 1틀함 ㄱ-
H AC (2:02, 1 WA)
읽기 싫어서 안 풀고 있었는데, 알고보니 엄청 쉬운 그냥 구현 문제였다. 얼탱
D AC (2:11)
이제부터 고민이 시작됐다. F번을 잡아봤는데 잘 안보여서 튀었다. 그렇다고 B번을 보기에는 애매하다고 생각해서, 문제 제목이 마음에 드는 L번을 잡았다. (Last Dance)
문제를 읽어보니까 간선이 도착 시간 자체를 결정하는 다익을 짜면 될거 같았다. (이건 작년 코이 1차 2번에서 쓴거랑 유사하다고 생각했다)
그리고 처음 했던 생각은, 2번의 cycle 안에는 모든 가능한 자세들의 탐색을 다 할 수 있을 거 같아서 음에 따른 시간을 저장하는 배열에 t와 t+K를 넣고, 탐색 시 현재 시간에 맞게 lower_bound를 해줘서 시간을 구했다. 그리고 쿼리에서는 2번의 cycle 후의 시간의 범위가 100만 이하이니 이걸 prefix sum으로 관리해줬다.
근데 틀렸다!
다시 생각해보니까 대략 K번의 cycle이 가능했다. 그렇다고 t, t+K, ..., t+K*K를 다 넣을 수는 없었다..
찬찬히 생각해보니 그냥 배열에 t만 넣고, 현재 시간의 mod K 를 이용해서 적당히 구해줄 수 있었다. getNxt 함수를 짜고 변수들을 ll로 바꾼 뒤에 실행시켰다.
L AC (2:52)
내가 슥보에서 3번째로 L을 풀어낸 사람이 되었다!!!
근데 풀이가 생각보다 많이 쉬워서 왜 슥보가 저런지 의문이 들었는데, 그냥 사람들이 맨 마지막 문제라고 제대로 안 보고 다른거 잡아서 그런거 같다. 앞으로도 슥보만 따라가지 말고, 이렇게 대담한 시도를 해봐야겠다.
마지막으로, F번을 읽어봤다.
대충 선형일때 어떻게 풀까 고민하다가 A_i - average의 prefix를 구한 뒤에, 그 값이 0이 되는 횟수를 구해주면 됐다. 근데 이걸 바꿔서 생각해보니까 그냥 그 값들 중 최빈값의 개수를 구하면 됐다! 그래서 map에 담고 잘 처리해줬다.
F AC (3:19)
후에 다른 3개의 문제를 봤지만 다 어려워보여서 그냥 테트리스를 켰다.
생각보다 좋은 성적인 16등이 되었다! L번을 푼 사람이 되게 없길래 놀랐던 기억이 제일 인상 깊었던 듯 하다.
페널티 관리는 내 고질적인 문제인 것 같다. 저기서 브론즈 문제랑 실버 문제를 1틀씩 한게 약간 아쉽다. 페널티 관리만 잘 했으면? 10등 내도 가능했었을 것 같지만, 난 이정도로 만족한다. 다음에는 슥보를 빨리 보기 시작해야겠다. 그러면 C를 시작하고 1시간동안 붙잡는 일은 없을 것 같다 ㅋㅋㅋ