SCPC 2024 2차예선 후기 및 풀이

목차
1. 총평
2. 후기
3. 분석
4. 풀이

---

All Solve

겨우 다풀었다.

---

1. 총평

아마 다들 같은 생각이었을것 같은데, "본선 문제가 얼마나 좋길래 예선 문제가 이모양인가" 싶다.

 

참가자는 비슷하거나 약간 많아진 것 같다.

참가자 수준은 꽤 높아진 것 같다.

 

난이도 추세가 이전과 너무 달라 굉장히 당혹스럽다.

그나마 예전의 3번 자리를 지금의 4번이 맡았다고 생각하면 비슷하긴 한데...

 

본선 컷 문제인 4번이 어렵다기 보다는 약간의 ad-hoc적 관찰 + 시간 박아야 풀리는 많은조건분기 문제라서 어렵지 않은 대회였다고 생각한다.

그런데 결과론적이지만 본선 컷(1250점 부근)에 사람들이 굉장히 많이 몰려 있기 때문에, 개같이 망한 대회가 되어버렸다. 원래대로 3번을 어렵게 냈으면 4, 5번에서 긁는 맛이 있었을텐데...

 

아무리 생각해도 본선에서 쓸 문제 빼니까 남은 문제가 없어서 급조한게 아닐까 싶다.

---

2. 후기

올해는 난이도 분포가 이상할 뿐만 아니라 문제 퀄리티도 영 안좋아 보인다.

 

1번은 1번치고 너무 어렵다. 문제를 하도 안풀어서 감이 다 뒤진건지 dp류에 약해서 그런건지 모르겠으나 체감상 최소 골드3~2 되어보인다.

 

반대로 2번, 3번은 너무 쉽다.

2번은 ``offline_query`` 태그 기본 난이도가 좀 있고 ``pbds`` 안쓰면 세그를 써야 한다는 점을 고려하더라도 idea가 직관적이어서 체감 난이도는 더 낮다.

3번은 내가 문제를 잘못 읽었나 싶을 정도로 대충 냈다. 내 생각이지만 1번보다도 더 쉬웠다.

 

4번은 그나마 기존의 3번 포지션이라고 생각하면 봐줄만 했던 것 같다.

발상도 적당히 어렵고 구현도 적당히 어려운 딱 scpc-style 문제. 그런데 생각보다 많이 풀어서 조금 놀랐다. (확실히 참가자 수준이 오른듯)

 

5번 역시 기존의 4번 포지션인 것 같다. (기존 4번보다 비슷하거나 조금 어렵고 5번보다는 확실히 쉬운)

구현이 진짜 때리고 싶었지만 어쨌든 난 풀어서 기분이 좋았다.

 

그나저나 ``std::stoi()`` 함수가 컴파일이 안되던데, 이거 왜이러는건지 모르겠다. 일단 구글링으로 대충 해결해서 내긴 했다만... 문제가 있어보인다. (c++ 버전 바꿔도 안되고, ideone같은 데서는 잘만 됨)

---

3. 분석

본선에 정확히 몇명이 가는지 모르겠는데, 114명~130명 사이로 가는 듯하다.

운이 좋다면 4번까지 풀고 껐어도 가는거고, 없다면 5번까지 박박 긁어야 될것 같다.

 

2, 3번이 워낙에 쉬웠어서 4번을 만점 받아놓고 2, 3번을 못푼 사람은 없다고 본다.

따라서 1,2,3,4번 솔브가 아니면 일단 무조건 떨

 

근데 5번이 생각보다 긁기가 어려운 문제라서, 어떻게 될지 잘 모르겠다. 들리는 말로는 50점 긁은 사람이 엄청 많은 것 같다.

그런 사람들이 본선 진출자 수보다 많다면 1250점에서 5번의 제출 횟수로 갈리게 된다.

(2차예선의 tie break 기준은 뒷문제에서 고득점 > 뒷문제에서 적게 제출 > 뒷문제에서 빠른 실행시간 이다.)

참고로 제출 횟수는 최고득점을 받은 이후 제출도 count된다.

문제별 분석

- 1번 문제는 400명이 냈는데 267명밖에 풀지 못했다. 확실히 어려웠음을 반증한다.

- 1번이 어렵다 보니 1번을 푼 사람들은 웬만해선 2, 3번도 푼 모습을 볼 수 있다.

5번 문제

- 모든 사람이 0점, 50점, 500점 중 하나라고 가정하면, (160 × 156 - 37 × 500) ÷ 50 = 129명 의 사람이 50점을 맞았다.

- 제출자 수 - 만점자 수 = 123명이니까 거의 딱 맞는 숫자다.

- 이렇게 되면 본선 진출자 수에 따라서 제출 많이 한 1250점이 짤리는 그림이 되겠다.

개인적으로는 역대 본선 컷이 정배보다 낮았다가 점점 비슷해진 것을 고려했을 때 그냥 딱 1250점이 컷이 되지 않을까 싶다.

 

4. 풀이

1. 연속 1

체감 난이도: 골드 3~1

알고리즘: dp

풀이

 일단 누가 봐도 dp문제긴 한데, 사람마다 풀이가 다 다르다. 본인한테 편한대로 풀면 된다

 

``i``번째 수까지 봤을 때,

- 모든 수가 ``0``인 경우

- 현재 ``1`` 이 이어지고 있는 경우

- 이미 ``1`` block이 등장했다가 지금은 0인 경우

이렇게 dp배열 3개를 잘 계산하면 된다.

 

사실 난 이렇게 안풀었다. 그래서 이 풀이가 맞는지도 확실하지 않다.

2. 라운드 로빈

체감 난이도: 골드 1~플래 4

알고리즘: offline_query, binary_search, data_structure

풀이

난이도를 높게 써놨는데, 이건 태그 자체의 기본 난이도가 높아서 그럴 뿐 idea를 떠올리는 데 필요한 난이도는 골드 4정도 된다고 본다.

 

일단 이건 예제를 놓고 같이 봐야된다.

``번호: 1 2 3``

``개수: 3 1 2``

``실제 할당: 1 2 3 / 1 3 / 1``

쿼리: ``5``번째 cpu 번호

 

일단 각 쿼리마다 몇 번째 바퀴인지 구해야 된다. 정확하게는 cpu가 몇 개 남은 시점인지 알아야 한다.

- 이는 먼저 $N$개의 cpu를 할당된 슬롯 개수로 sort하고, ``i``번째 cpu까지 전부 소진했을 때 슬롯을 총 몇 개 쓰는 지 구해두고 이분탐색 해주면 된다. 주의할 점은 기준이 "바퀴"가 아닌 "cpu"로 구해야 된다. (바퀴 수는 매우 크기 때문에...)

- 예제를 보면 ``cnt[1]=3``, ``cnt[2]=5``, ``cnt[3]=6``으로 쿼리인 ``5``는 ``cnt[1]<5<=cnt[2]`` 이기 떄문에 cpu가 2개 남았을 때임을 구할 수 있다.

 

그 다음에는 그 중에서 정확하게 몇 번째 cpu를 알고 싶은지 구해야 된다.

- 이건 단순히 현재 개수 직전까지 소진한 슬롯 개수를 빼준 뒤 현재 개수로 나눈 나머지가 되겠다.

- 예제로 보면 ``(5 - cnt[2-1]) % 2 = 1``이므로 2개 중 2번째로 번호가 큰 cpu를 구하면 되겠다.

 

이제 실제 정답을 구하는게 약간 어렵다.

일단 문제를 단순화하자면 $1,2,\dots ,N$에서 숫자 한개씩 빼면서 그때그때 $k$번째 수가 뭔지 구하는 문제이다.

이거에 익숙하면 바로 세그나 ``pb_ds``가 떠오른다.

 

그러면 모든 쿼리를 "cpu 개수"로 sort한 뒤 세그나 ``pb_ds``를 써서 쿼리당 log N에 쉽게 구할 수 있다.

3. 방범 시스템

체감 난이도: 골드 4~3

알고리즘: sorting, sweeping

풀이

너무 쉬워서 깜짝 놀랐다.

일단 $x$, $y$축 독립이니 분리하고 1차원으로 봐주고...

좌표 둘다 sort해주고 ``left``, ``right`` 변수 잡아서 가장 첫 확인지점 기준으로 왼쪽에 있는 애는 ``left`` 변수에 기댓값 더해주고 오른쪽은 ``right``에 더해준다.

그다음에 ``now`` 변수 만들어서 맨 처음에는 O(N) 돌면서 naive하게 구해준다.

그다음에 sweeping 하면서 ``right``에서 ``left``로 넘어가는 기댓값 처리 해주면서 바로 직전 지점과의 거리 차이만큼 ``now`` 바꿔주면서 답을 잘 구해주면 되겠다.

4. 수열 탈집중화

- 체감 난이도: 플래 5~3

- 알고리즘: constructive, case_work, implementation

- 풀이

관찰 1) 결국 수열에는 최소값과 최대값만 남는게 반드시 좋다.

- 증명: 만일 그렇지 않은 원소 $x$가 있다면 최소값과 최대값 중 개수가 적은 쪽으로 바꾸는게 반드시 더 좋다.

관찰 2) 최소값과 최대값은 똑같은 개수만큼 있어야 한다. (N이 홀수면 한 개 차이)

- 자명

관찰 3) 그렇게 만들기 위해서는 시행을 최대 2번만 해주면 된다.

 

이거만 봤으면 이제 구현 열심히 깎아주면 된다. (개인적으로 본선 컷 문제 치고는 쉬운 관찰이라고 생각한다.)

 

case 1) 처음부터 싹 같은 수 -> 정답 ``0``

 

case 2) 시행 1번으로 가능한 경우

- 최소값 혹은 최대값이 아닌 값이 나오는 가장 왼쪽과 가장 오른쪽 지점을 구한다.

- 시행은 해당 구간을 반드시 포함해야 한다.

- 시행이 min으로 만드는 시행인지 max로 만드는 시행인지 또 나눠서 생각하자.

- min으로 만드는 시행을 한다고 해보자. 그러면 해당 구간에서 가장 가까운 최소값이 어딘지 구해준다. (구간 안에 있을 수도 있음)

- 그 지점까지 구간을 연장한다.

- 그 구간 밖에 최대값이 $N/2$ 개 이상 있어야 한다. (없을 시 시행 1번으로 불가능)

- 구간 밖에 최대값이 $N/2$ 개일 때 구간을 한 칸씩 확장해주고 출력

 

case 3) 시행 2번 하기

- 수열의 정확히 중간 부분이 최소값과 더 가까운지 최대값과 더 가까운지 경우를 나눈다.

- 최소값이 더 가깝다고 하자. 이제 수열의 중간 부분 기준으로 최소값과 최대값이 같은 쪽인지 반대편인지 나눈다.

- 같은 쪽이면 (수열의 끝, 최소값) 구간을 min으로 민 후 (중간지점, 최대값쪽 수열의 끝) 구간을 max로 민다.

- 반대편이면 (최소값쪽 수열의 끝, 중간지점) 구간을 min으로 민 후 (중간지점, 최대값쪽 수열의 끝) 구간을 max로 민다.

5. 보물찾기

체감 난이도: 플래 2~다야 5

알고리즘: game_theory, topological_sort

풀이

Alice의 노드는 A, Bob의 노드는 B라 하자. 어떤 노드가 A인지 B인지를 "색깔"이라 하자.

 

그래프를 쭉 돌면서 같은 색으로 이루어진 연결요소로 group화 하면서 아래 4가지 case중 어떤 경우인지 체크

1) A*: A가 2개 이상 있고 보물이 1개 이상 있는 연결요소 (Alice가 반드시 이기는 땅)

2) A: A가 단 1개 있거나 보물이 아예 없는 연결요소 (A 안에서만 말을 돌려서는 Alice가 이기지 못함)

3) B*: 보물이 없는 B 2개가 연결된 부분이 존재하는 연결요소 (Bob이 반드시 이기는 땅)

4) B: 그렇지 않은 연결요소 (B 안에서만 말을 돌려선 Bob이 이기지 못함)

 

1)과 3)은 바로 정답이 정해진다.

또한 만일 A에서 게임을 시작하는데 Alice가 미쳤다고 B*으로 말을 옮기지는 않을 거기 때문에 반드시 B로 옮길거고, 마찬가지로 B에서 게임을 시작하는데 Bob이 미쳤다고 A*으로 말을 옮기지는 않을 거기 때문에 반드시 A로 옮길 것이다.

그래서 A*과 B*은 이제 고려할 필요가 없다.

 

여기서 한가지 더 관찰해야 될게 있다.

A->B 옮길 때 edge의 두 노드에 모두 보물이 없으면 안된다. Bob이 말을 다시 고대로 돌려주는게 반드시 좋기 때문이다. 그렇게 말이 계속 왔다갔다 하면 Bob의 승리이다.

마찬가지로 B->A 옮길 때 edge의 두 노드 중 하나라도 보물이 있으면 안된다. Alice가 말을 다시 돌려주면 Alice의 승리이기 때문에...

 

위 점을 고려해서 그래프를 재구성하자. (구현 매우 귀찮음)

재구성된 그래프의 A->B edge에 보물이 있기 때문에 cycle을 도는 등 말이 뺑뺑이를 돌면 기본적으로 Alice의 승리이다. (default로)

그래서 우리는 Bob이 어디서 이길 수 있는지에 관심을 가져야 한다.

 

Bob이 이기려면 B에서 갈 수 있는 A 중 한 곳에서 Alice가 져야 한다.

그러려면 우선 갈 곳이 없는 A (leaf) 에서 Alice가 패배하고, 그러면 B에서는 또 Bob이 이기고, ...

 

나는 여기서 바로 위상정렬을 때렸다.

다른 누군가는 dfs인지 bfs로 잘 풀었다는데, 여기서부터는 취향껏 풀면 될것 같다.

cycle 처리는 할필요가 없는게 기본적으로 Alice 승리이고, Bob이 이기는 지점만 찾는게 목표라서 그거 처리만 잘 해주면 된다.

(Alice가 지는 A로 갈 수 있는 B는 무조건 Bob 승리인 것을 미리 처리)

 

사실 풀이를 다 보고 나면 그렇게 어렵지는 않은거같은데... SCPC 문제들은 처음부터 끝까지 모든 부분에서 풀이자를 귀찮게 만드는 신기한 능력이 있다.