SCPC 2022 2차예선 후기 및 풀이

- 참고: SCPC 2022 본선 후기

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

---

결과: 585점

5번에서 이상하게 한번 틀려서...

---

1. 총평

1번을 점점 어렵게 내는 추세

근데 2번은 이에 비해 쉽게 나옴

3번은 '19년보다는 어렵고(구현이), '20년보다는 쉽고, '21년보다도 쉬웠다.

특히 4, 5번 긁는게 너무 쉬워서 순위 가늠이 잘 안되는 대회

 

의외로 빡셌던 것 같음. (문제 난이도에 비해 만점자 수가 많아서)

보통 3솔 하면 웬만하면 붙겠다 싶은데, 이번에는 그런 느낌이 없음

하지만 아무리 그래도 585점은 붙어야 되는 점수. 이게 떨어지면 ㄹㅇ 답없는 대회

 

그렇게 판단해서 3번 풀고 귀찮아서 4, 5번 고민을 깊게 안함

3번 만점자 수가 제일 중요한데, 7~8시간 때까지 70명 이하였는데 어느새 120명 가까이 됐네요;;

2. 후기

올해는 문제의 질이 좋았다고 생각합니다.

온라인 대회 특성상, 검색으로 쉽게 풀리지 않도록 내야 하는데 이런 관점에서도 정말 좋았다고 생각합니다.

이와는 별개로 Codeforces 셋 냄새가 나기는 했지만..

 

1, 2번은 전형적인 Codeforces 문제 느낌이 났습니다. 그래서 의외로 발목잡힌 사람들이 있을수도 있을듯

역시 SCPC 2차 예선은 3번 문제가 제일 중요한데, 올해는 3번을 정말 잘 낸것 같아요. 누가 냈죠?

반면 4번은 4번답지 않게 쉬웠다고 생각합니다. 물론 난 안(못) 풀었지만.

 

결국 3번에서 적절한 알고리즘 발상 + 적절한 구현 모두 성공한 사람들이 웃었던 대회

 

아래는 시간대별 Solve 스샷

(각각 1, 2, 3, 4번 제출 직후 / 5번 직후는 맨위에)

---

3. 분석

우선 본선에는 약 130명 정도가 간다. (참고: [1] [2])

외국인도 참가하지만, 아마 동일하게 1차 예선 2차 예선 봐야 하는거로 안다.

따라서 우리는 2차 예선 130등이 몇 점일지 고민하면 된다.

 

+추가) 500점 (1, 2, 4번) 이 떨어졌고, 512점 (1, 2, 3, 4-2) 이 붙었다고 합니다.

 

1, 2번 못풀면 무조건 떨

4, 5번 긁는게 너무 쉬워서, 3번까지만 풀고 껐으면 (450점) 떨어질 것 같다.

3까지 풀고 4-1까지만 긁었으면 461점인데, 이는 매우 아깝게 떨어지거나 딱 커트가 될 것 같다.

 

내가 생각하는 안정권은 5-1만 긁은 523점 (근데 이렇게 받기가 되게 애매해서)

또한 완전 커트라인은 3번 만점이 아니어도 3-2(K=0), 3-3(K=-1), 4-2, 5-1까지 긁은 461점이지 싶다.

→ 참고로 3번에서 만점을 받고 4-1을 긁어서 나온 461점보다 더 등수가 높다. 5번에서 득점이 있기 때문에...

 

온사이트 한답시고 갑자기 적게 뽑아버리면 위에서 3-1도 긁었거나, 아니면 아예 3번을 맞고 4-2까지 긁은 512점은 되어야 할 듯

 

참고로 3번 안풀고 4번 풀었어도 됐다. 3번은 여러모로 말릴 수 있기 때문에...

실제로 아이디어만 떠올리면 구현은 4번이 훨씬 간단할 것 같다. (안풀어서 모름)

문제별 분석

1번 수열연산

- 만점자 312명 ('21년 466명, '20년 248명)

- 난이도는 제일 어려웠으나, 가장 쉬웠던 2020년보다는 많은 사람들이 참여

- 18명 빼고 다 맞춤. → 아예 못 풀었거나, 내면 다 맞는다.

- 2021년 1차예선 1번 만점자가 1300명, 올해 1차예선 1번 만점자가 611명인 것을 고려하면 올해 참가자의 관심 및 수준이 많이 오름

2번 반 협동게임

- 만점자 254명 ('21년 203명, '20년 251명)

- 개인적으로 어려운 줄 알았는데 결과를 보니 난이도 조절이 제일 잘된 문제

- 12시간 동안 꾸준히 1번 만점자보다 약 70명 적었다.

- 사실 아무렇게나 뽑아도 점수가 똑같지만, 어떤 기준에 의해 greedy하게 뽑아서 풀어도 틀리는 건 아니기 때문에 잘들 푼 것 같다

3번 ABC

- 만점자 117명 ('21년 130명, '20년 72명)

- 제출자 214명, 평균점수 117.7 / 200

- 제출자가 0점 초과인 사람의 수를 의미한다고 가정해 봅시다. 점수의 총합은 214 × 117.7 = 25187.8점, 만점자의 총합은 117 × 200 = 23400점. 이 차이는 1787.8점

- 따라서 부분점수를 받은 97명은 평균 18.43점을 얻었습니다.

- 만일 제출자 수에 0점인 사람이 포함된다 하여도, 뭐 한 대충 40명 정도가 0점 초과라고 하면 그들의 평균은 44.7점 입니다.

 

- 18점이면 1번 부분문제보다 살짝 높은 수준. 이거만 긁어선 절대 통과 못함

- 통과하려면 적어도 K=0, K=-1인 경우는 풀었어야 한다고 생각하는데, 만점을 받지 않은 사람들 중에서는 많아야 20명 같네요

- 따라서 3번 만점이 아니어도, K=0, K=-1 긁었으면 붙을 확률이 커짐

4번 직사각형

- 만점자 54명 ('21년 34명, '20년 51명)

- 제출자 218명, 평균점수 99.9 / 250

- 제출자가 0점 초과인 사람의 수를 의미한다고 가정해 봅시다. 점수의 총합은 218 × 99.9 = 21778.2점, 만점자의 총합은 54× 250 = 13500점. 이 차이는 8278.2점

- 따라서 부분점수를 받은 164명은 평균 50.48점을 얻었습니다.

 

- 이제 사람들이 잘 긁네요. 3번보다 많이 냈으니..

- 4-2까지가 62점이기 때문에, 위 수치는 매우 설득력 있습니다. 적어도 130명 이상은 62점까지 긁었겠네요.

5번 황금 카드

- 만점자 6명 ('21년 0명, '20년 27명)

- 제출자 118명, 평균점수 111.5 / 300

- 제출자가 0점 초과인 사람의 수를 의미한다고 가정해 봅시다. 점수의 총합은 118 × 111.5 = 13157점, 만점자의 총합은 6× 300 = 1800점. 이 차이는 11357점

- 따라서 부분점수를 받은 112명은 평균 101.4점을 얻었습니다.

 

- 이건 상당히 높은 수치네요.

- 5-1이 73점, 5-2까지가 아마 140점? 정도 될텐데 5-2까지도 꽤 긁었다는 소리가 됩니다.

- 한 60명 정도는 5-2까지 맞은 것으로 보입니다.

- 근데 내생각에 이 사람들은 웬만하면 4번 만점자에 포함될 것 같다. → 커트라인에 영향을 주지 않음

결론

3번을 맞춘 117명은 웬만해선 4-2까지 긁었거나, 5-1을 긁었을 것 같다. (점수 512+)

나머지 13명이 남았는데,

3번을 안맞추고 4번을 맞춘 이상한 사람들 몇 명 (한 4명 될까?),

3번을 안맞췄지만 5번을 (2) 섭테까지 긁은 이상한 사람들 몇 명,

그리고 대망의 461점 중 상위 몇 명.

이렇게 가지 않을까 싶다.

그리고 수상 기준 변경으로 인해 (2등상 2회 이상 수상자) 및 (1등상 수상자) 를 본선 진출자 수에 포함시켜 계산할지 여부에 따라서도 조금씩 바뀔 수 있을 것 같다.

---

4. 풀이

1. 수열 연산

- 체감 난이도: Gold 3

- 알고리즘: Greedy, Two-pointer (그리디..? 보다는 투포인터가 더 강함)

- 풀이

- 먼저 연산의 최소 횟수를 구하자.

- 어떤 원소가 가장 많은 +1이 필요할까? → 가장 작은 수

- 따라서, 모든 연산을 범위 [처음, 끝]으로 시행하면 K - (가장 작은 수) 번 만에 완료할 수 있다.

 

- 이제, 최소 비용을 구하자.

- 가장 작은 수를 X라 하자. 그러면 우리가 구한 연산의 최소 "횟수"는 K-X 이다.

- 수열에 등장하는 모든 X는 K-X 번의 연산이 필요하다.

- 반면, 수열에 등장하는 모든 X+1 이상의 수는 K-X-1 번 이하의 연산이 필요하다.

- 즉, X에 수행할 연산 중 한 번은, X+1 이상의 수를 포함할 필요가 없다.

ex. N=5, K=2

1

1

0

1

0

1

1

1

2

1

2

2

2

3

2

- 따라서, X에 대한 연산은 X를 모두 포함하는 최소의 구간에 대해서 수행하면 된다.

- 마찬가지로 X+1에 대한 연산은 X+1을 모두 포함하는 최소의 구간에 대해서 수행하면 된다.

- 이를 X~K까지 반복해주면 된다.

 

- 그렇다면 구간을 계속 계산해나가야 하는데, 구간은 연속해야 되기 때문에 왼쪽 끝과 오른쪽 끝 만 관리하면 된다.

- 또한 구간은 계속 같거나 커져야 함을 알 수 있다. 따라서 왼쪽 끝은 단조감소, 오른쪽 끝은 단조증가한다.

참고) 현재 보고 있는 수가 어디에 있는지 알아야 하기 때문에, 전처리로 (수, 위치) pair를 정렬해두면 편하다.

- 그러면 현재 수가 존재하는 모든 위치에 대해 현재 구간 [왼쪽, 오른쪽] 을 적절히 갱신해주고, 비용에 그 크기를 더하자.

 

- 그러나 이는 K가 너무 크기 때문에 시간 초과가 난다.

- 따라서 수열에 등장하는 수에 대해서만 확인할 필요가 있다.

- 이는 위의 (수, 위치) 를 정렬해둔 배열을 따라서 계산한다면 저절로 해결된다.

-- 대신, 예를 들어 X 다음에 X+5가 등장한다면, X에 대해서는 (구간의 크기) × 5 를 더해줘야 할 것이다.

 

- 이러면 예외처리가 조금 귀찮을 것이다.

-- 나는 K 초과의 수들은 그냥 K로 바꿔버리고, (수, 위치)를 정렬해둔 배열의 끝에 (K, N)을 추가해줘서 간단히 해결했다.

시간복잡도 $O(N \log N)$

 

2. 반 협동게임

- 체감 난이도: Gold 3 (세그 빼면)

- 알고리즘: Segment tree

- 풀이

- 우선, 빠져야 하는 아이들의 쌍은 시작부터 정해져 있다.

- 같은 반 학생들을 가장자리부터 짝지으면 된다. (홀수면 어차피 남음)

-- 왜냐하면, 같은 반이 2명 이상이면 반드시 빠져 점수에 기여하는 것이 좋고, 4명 이상이면 가장자리 2명부터 빠져야 가운데 2명이 빠질 때 거리에 손해를 보지 않기 때문에 가장자리부터 빠져야 한다.

 

- 짝을 모두 지어 줬다면, 어떤 순서로 빠지든 간에 최종 점수는 같다. (단, 포함 관계에 있는 두 짝은 큰 짝부터 빠질 때)

-- 한 3쌍 정도가 서로 겹쳐있는 예제를 그려서 해보면 바로 알 수 있다.

- 우선 아이들이 빠져나간 후 사이 공간을 좁히지 않는다고 생각하면 (거리 손해가 없으면), 각 짝의 거리 총합을 계산할 수 있기 때문에 정답이 고정되어 있다.

- 이제 거리에 손해를 보는 총합을 생각해보면 사실, 두 짝을 골랐을 때 겹쳐있을 경우의 수와 같다. (단, 포함 관계는 세지 않음: 이들끼리는 거리에 손해가 없으므로)

 

- 그럼 겹쳐있는 쌍의 수를 어떻게 셀까?

- 이를 위하여 세그먼트 트리가 필요하다.

- 짝지어준 정보를 pair로 정리해서 가지고 있자. (참고로 정렬한 순서대로 계산하면 포함 관계 이슈를 해결할 수 있다.)

- 각 pair에 대하여, 1) 그 안에 이미 빠진 명수 계산 query 2) 현재 pair를 빼고 update 해야 한다.

- 1) 쿼리는 구간합이고, 2) 쿼리는 pair의 두 위치에 대해 1씩 더해주면 된다.

- 이를 세그먼트 트리와 같은 자료구조를 통해 구현하면 문제를 해결할 수 있다.

시간복잡도 $O(N \log N)$

3. ABC

- 체감 난이도: Platinum 3~2

- 알고리즘: SCC, DP on DAG, Case work

- 풀이

1. K=-1

- 우선 SCC를 돌리자.

- 만일 어떤 component(루프) 안에 A, B, C 간선이 모두 들어있으면, 답은 무한대

- 그렇지 않으면, DP on DAG를 돌리자.

-- 당연히 SCC를 돌리면서 된 위상정렬 순서대로 돌려야 한다.

- dp[i][j] (j = 'A' or 'B' or 'C') : i번 component까지 왔을 때, j로 끝나는 최대 길이

 

- 한 component 안에서, 만일 정점이 2개 이상이어서 간선이 존재한다면, dp[i][j]를 update해줘야 한다.

-- 만일 'A'로만 이루어져 있으면, dp[i][A] = max( dp[i][C] + 1, dp[i][A] );

-- 만일 'A', 'B'로만 이루어져 있으면, 위에 덧붙여 dp[i][B] = max( max( dp[i][A] + 1, dp[i][C] + 2 ), dp[i][B] ); 도 해준다.

- i번 component에서, 다른 component를 잇는 모든 간선(next, char)에 대하여, dp[next][char] 를 update 시키자.

-- 이 때, 모든 문자 A, B, C에 대하여 dp[next][j] = max( dp[i][j], dp[next][j] ); 를 기본적으로 해줘야 한다. (현재 간선 안쓸 경우) 또한, dp[next][char] = max( dp[i][char 이전 문자] + 1, dp[next][char] ); 도 까먹지 말자.

 

참고) 어떤 component 내부의 간선 종류를 알고 싶으면, 그 component에 해당하는 모든 점에 대하여 간선을 봐주면서, 같은 component를 잇는 간선의 문자를 봐주면 된다.

 

2. K>=0

- 위와 비슷한데, 일단 각 node를 in-node 3개와 out-node 3개, 총 6개로 쪼개자. (정점이 N개 → 6N개)

- in-node와 out-node는 각각 A, B, C 타입이 있다. (그래서 6개)

- in-node는 해당 정점으로 들어오는 간선에 연결하고, out-node는 해당 정점에서 나가는 간선에 연결한다.

-- 이 때 간선의 문자와 node의 타입이 일치하는 곳에 연결하자.

- 그리고 각각의 node에서, (in-node A → out-node B), (in-node B → out-node C), (in-node C → out-node A) 3개의 간선을 잇자.

- 이렇게 그래프를 재구성하면, 그래프를 따라 이동하며 얻는 문자열은 반드시 올바르다.

 

- 답이 무한대이려면, 어떤 loop에서 한 개라도 건너뛰면 안된다.

- 따라서 SCC를 돌린 뒤, 정점이 2개 이상 존재하는 component가 존재하면 답은 무한대

- 그렇지 않으면, 모든 component는 정점 1개로 구성되어 있으며 따라서 DP on DAG를 좀 더 마음편히 돌리면 된다.

-- 이 때 만일 간선이 우리가 추가해준 dummy 간선이면 그냥 dp[i][A~C]를 다음으로 복사해주자.

-- 또한 K=-1과 달리 간선을 볼 때 모든 문자 A, B, C에 대해 볼 필요가 없고, 간선에 쓰인 문자에 해당하는 dp값만 update해주면 된다.

 

- 하지만 아직 K=0일 때만 해결된 상태이다.

- 어떤 간선을 건너뛰려면 어떻게 해야 할까? 

- 어떤 간선 ( i → j )를 건너뛰려면, 모든 문자에 대해 (i의 in-node A → j의 in-node A ) 로 dp값을 전파시키면 된다.

- 그러면 (어딘가) → i까지 최대 길이로 온 다음, ( i → j ) 간선을 건너뛰고 다시 j 부터 dp를 때리면 될 것이다.

- 따라서 모든 간선 ( i → j )에 대하여 위의 전파를 수행해준 다음, 전체 그래프에 대하여 DP on DAG를 다시 수행해주면 된다.

- 이를 K 값 만큼 반복해준 뒤 DP table의 최대값을 구하면 정답을 얻을 수 있다.

 

시간복잡도 $O( (N+M) K)$

4. 직사각형

- 체감 난이도: Platinum 2~1

- 알고리즘: Constructive (다른 말로 코포식 문제)

- 풀이 (내풀이는 아님ㅎ)

- 꽉 찬 직사각형의 조건을 단순화하자.

- a부터 b까지의 수가 정확히 한 번씩 등장하려면,

- 그 직사각형에서 최소값이 a 이고 최대값이 b이면 된다. (물론 b-a+1=넓이)

- 이걸로 $N^3$ naive를 돌리면 아주 손쉽게 62점을 얻을 수 있다.

 

- 각 점 (x,y)에 대하여, A[x][y]를 최소값으로 가지는 "꽉 찬 직사각형"의 개수를 세자.

- 이렇게 세면 중복되지 않으면서 모든 경우를 셀 수 있다.

- 먼저 1×1 크기의 직사각형에서 시작하여 점점 상하좌우로 넓혀갈 것이다.

- 직사각형을 이루는 x좌표 2개, y좌표 2개 총 4개의 변수로 관리할 수 있다.

 

- 상, 하, 좌, 우 방향 중 한 방향으로 1칸 확장할 것이다.

- 현재 W×H 크기라면, 1칸 확장할 시 상하로는 W칸, 좌우로는 H칸이 늘어날 것이다.

- 현재 최대값을 P라 하자.

- 해당 후보 중 P보다 크면서, 가장 작은 수가 속한 곳으로 확장해야만 한다.

-- 만일 그렇지 않는다면, 그 수 때문에 발목잡혀 연속한 모든 수가 존재할 수 없다.

- 그런데 그 방향에 A[x][y]보다 작은 수가 존재한다면, A[x][y]에 대한 counting을 종료한다. (더이상 불가능하므로)

- 확장할 때마다, 최대값을 계산하여 "꽉 찬 직사각형"인지 check

 

- 상, 하, 좌, 우는 합쳐서 2N칸이 있기 때문에, 위 과정은 최대 2N번 반복된다.

- 또한 칸은 총 $N^2$개 있기 때문에, 해당 알고리즘은 $2N^3$의 연산 안에 동작한다.

 

참고) 확장할 때 최소/최대를 구하기 위하여 min[i][s][e] = A[i][s] ~ A[i][e] 의 최소값. 과 같은 전처리를 해주자.

시간복잡도 $O( N^3 )$

5. 황금 카드

- 체감 난이도: 난 못품 (Diamond 1 ~ Ruby 5라고 하네요)

- 알고리즘: Mathematics, FFT (조합론, 확률론)

- 풀이

(2) N<=5,000 K<=5,000 풀이

사실 조합론 좀 치는 사람들은 뭐 바로 식을 도출하는것 같던데, 난 못함

 

- $E_k$는 결국 k번 깠을 때, (카드 1종류 나오는 경우의 수) × 1 + (카드 2종류 나오는 경우의 수) × 2 + ... 를 구하면 된다.

- 만일, 카드 3종류 나오는 경우의 수를 구한다고 하자.

- 예를 들어, 카드 (1, 4, 6)이 나오는 경우의 수를 생각해보자. 이는 $E_k$를 구할 때 3배가 되어야 한다.

- 그런데 카드 종류가 3개이기 때문에, 각각에 대해 한 번씩 더해주면 알아서 3배가 된다.

i.e.

1번 카드 → (1, 2, 3) , (1, 2, 4), ... , (1, 4, 6), (1, 4, 7), ...

4번 카드 → (1, 2, 4), (1, 3, 4), ..., (1, 4, 6), (1, 4, 7), ...

6번 카드 → (1, 2, 6), (1, 3, 6), (1, 4, 6), (1, 5, 6), ...

이렇게 각 카드종류에 대하여 "자신을 포함해 3종류 뽑을 경우의 수"를 구하여 더해주면 알아서 3배가 된다.

 

- 보통 카드번호 하나를 fix할 수 있는 것은 매우 큰 value이므로 매우 중요한 관찰이다.

- 이 관찰을 확장시켜보면, k개를 까서 카드종류가 몇 종류가 나왔든 간에 단순히 i번 카드가 나오는 모든 경우의 수를 계산하면 된다.

- 따라서 결론적으로 문제에서 요구하는 $P^k \times E_k = \sum_{i=1}^{N}(P^k - (P - p_i)^k)$ 로 손쉽게 변형된다.

- naive하게 NK에 계산할 수 있고, 만점풀이는 뭐 생성함수 뭐시기 FFT 뭐시기 하면 된다고 하네요

(2) 서브태스크에 대한 시간복잡도 $O(NK)$