반응형 후기/대회3 SCPC 2023 2차 예선 후기 1번 일단 윷놀이를 열심히 구현한 다음 시뮬레이션하면서 사이클을 찾는다. 사이클을 찾았으면 사이클은 그냥 뛰어 넘어주고 남은 칸 또 시뮬레이션. 2번 스택을 사용하면서 현재 탐색 중인 괄호 이후에 concatenate 되어 있는 괄호문의 개수를 구한다. concatenate 되어 있는 서브 괄호문의 개수를 k개라 하면, 해당 부분에서 찾을 수 있는 올바른 괄호 문자열의 개수는 kC2개. 3번 DP로 될 것 같다는 생각은 들었다. O(N^3)이라도 짜는 걸 목표로 했으나 결국 풀이를 생각해내지 못하고 시간이 종료되었다ㅠㅠ 2023. 8. 25. SCPC 2023 1차 예선 후기 1번 브루트포스로 최댓값 찾으면 된다. 2번 방향 전환을 여러 번 하는 것은 의미가 없다. 어차피 가장 먼 곳까지 가는 길 중간에 다 수확 가능하기 때문이다. 따라서 한 방향으로 맥시멈까지 갔다가 반대방향으로 전환해서 남은 이동거리만큼 최대한 가면 된다. 맥시멈 정하기는 O(N)에 할 수 있고, 맥시멈까지 가면서 수확할 수 있는 양은 정렬 후 이분탐색으로 O(logN)에 구할 수 있으므로 총 시간복잡도 O(NlogN)에 해결가능하다. 1. 왼쪽 먼저 가기 → -(lmax)까지 갔다가 +(D-2*lmax)까지 가기 2. 오른쪽 먼저 가기 → +(rmax)까지 갔다가 -(D-2*rmax)까지 가기 3번 시뮬레이션할수록 빈 바구니가 줄어들게 된다. 따라서 '총 구슬 개수의 합'이 '바구니 개수'보다 크거나 같.. 2023. 8. 3. SCPC 2022 1차 예선 후기 1번 문제 제출 횟수가 2번인 건 비밀입니다:) 2번은 (내가 이상하게 푼 건지 모르겠지만) 예외 케이스 처리를 따로 해주어야 하는 경우가 있었는데 놓쳐서 3번 만에 AC를 받았다. 3번은 2번이랑 같은 배점인데 2번에 비해 너무 쉬워서 2번을 이상하게 꼬아서 푼 것 같다는 생각이 계속 들었다.. 4번은 아이디어 생각해내는데 시간을 너무 많이 썼다. 5번은 대충 감은 잡았는데 구체적인건 좀 더 시간 써서 생각해봐야 할 것 같았다. 근데 너무 졸려서 그냥 잤다. 나한테는 이번이 두 번째 SCPC였다. 그래서 올해 난이도는 잘 가늠이 안되지만 개인적으로는 중간에 다른 일정 없었으면 올솔도 가능했을 것 같아서 조금 아쉽다. 1차 통과해도 2차 예선 날 아침부터 풀로 다른 일정이 있어서 참가 못할 것 같다..ㅠ.. 2022. 7. 18. 이전 1 다음 반응형
