SCPC 2022 예선 1라운드 후기

SCPC를 대학교 4학년동안 처음 참가해봤습니다. 그전에 들었던 얘기로 솔브드 티어로 골드~플레정도로 나온다고 들었는데 요구하는 아이디어들이 생각보다 어렵더라고요..

간신히 2솔했습니다. 다른 문제들의 서브태스크들을 긁어보려했는데 잘안됐습니다. ㅜ

 

1번문제는 단순 정렬문제라 쉽게 풀수 있었습니다. 솔브드 티어로 치면 실버2~실버1정도인것 같습니다. 어떤 좌표가 가야할 최종 좌표는 정해져있으므로 정렬후 목표인 좌표와 현재좌표를 단순히 빼면 되는 문제였습니다.

 

2번문제는 아이디어가 필요한 문제였습니다.  수열을 똑같은 합을 가진 K개의 그룹으로 나누는 경우의수를 찾는 문제였습니다. 따라서 수열의 총합/K가 그룹의 합이 될것입니다. 수열의 총합/K로 그룹의 합을 구하지

못하는 경우가 있는데요. 바로 수열의 총합이 0일때입니다. 이를 따로 생각하여 문제를 풀어야 합니다.

먼저 수열의 총합/K로 그룹의 합을 나눌 수 있는 경우 그룹을 나눌 수 있는 곳은 누적합을 통해 찾을 수 있습니다.

누적합이  수열의 총합/K로 나누어 떨어지는 경우  그룹을 나눌 수 있는 곳이 될것입니다.  또한 나눈 것의 몫은 수열을 똑같은 합으로 나눴을때 몇번째 그룹인지를 알려줍니다. 몫이 K일경우는 굳이 나눌 필요가 없으므로 (맨끝그룹이기에 K-1까지 나눌경우 알아서 나눠짐) 1~K-1까지의 그룹의 가짓수를 구하면되는데 

몫이 임의의 A인 A번째 그룹이 등장할때 몫이 A-1인 A-1번째 그룹의 가짓수를 더하면 됩니다. 

 

수열의 총합/K가 0인경우는 생각해보면 누적합이 0인곳 어디든지 K-1번 나눌 수 있습니다.

누적합이 0인곳이 T번 등장했다했을때 T개의 0사이 T-1번중에 K-1번 나눌수 있는것입니다. 

즉 T-1 C K -1조합이 됩니다. (T-1)! % mod / ((C)! % mod *(K-1) % mod) 식이 됩니다.

모듈러 나눗셈을 페르마의 소정리인 (A % mod / B % mod)%mod = (A% mod * (B^mod-2)%mod )%mod 를 이용하여 구하면 됩니다. 

 

나머지 문제들은 코드그라운드에 올라오면 다시 풀어봐야겠군요.. 2솔로 2라운드를 갈수 있을지 모르겠습니다 작년까지는 1솔+a 로 2라운드 진출 할 수 있었다 하는데 이번에는 작년보다 참여자가 적다고 하더군요... 2라운드 갈 수 있을런지 ㅜㅜ