10월 29일 Eastern GP 연습

프리징이 죽어도 안풀려서 등수도 안나왔는데 후기를 씁니다.

총평: GP치고 난이도가 쉬운 셋. 대전 중반까지 난이도가 이 정도 되지 않을까 싶습니다.

~1시간: 초반 3문제를 도토리가, 2문제를 상수가 코딩했다. 중간에 G 실수가 있었다. 직후, C와 K를 도토리와 상수가 각각 코딩했다.

~2시간: 도토리가 C에서 TLE가 났고, 최대데이터에서 10초 나오는 것을 확인하고 시간복잡도를 줄여서 풀었다. 그 사이에 K, L을 상수가 코딩했다. 2시간째에 모든 문제의 풀이 개요가 나왔다.

+ 여기서 도토리 코딩큐가 과하게 밀렸는데, 내가 B, F 풀이를 넘긴 상태였고, A는 상수가 코딩할 수 없는 문제여서 이 시점에서 3문제를 도토리가 코딩할 수밖에 없었다. 

~3시간: 도토리가 F를 푸는 도중, 상수와 내가 H를 밖에서 완벽하게 계획하고 스왑하여 맞췄다. 밖에서 10분동안 F를 고쳤다.

~4시간: B를 도토리가 코딩했는데, 시간복잡도가 맞았는데도 코드가 약간 느리게 돌아서 TLE가 났다. 30분동안 상수만 줄이다가 fastio를 써서 맞췄다. 

~5시간: A를 풀었다. 학부 수업도 도움이 된다는 것을 느꼈다.

코딩큐가 과하게 밀려서 밸런스가 깨진 감이 있지만, 어차피 앞으로 있을 대부분의 팀전(GP, ICPC)은 "절대" 이런 문제셋이 나오지 않을 것 같습니다. 오히려 이런 난이도 낮은 문제셋에서 빠르게 문제 풀이가 나온 것을 긍정적으로 보는 것이 좋은 것 같습니다.

---

현재까지 GP 포인트 랭킹입니다. (ACGTeam이 낮은 이유는 ainta님이 1인팀으로 아무도 못푼 문제만 5시간동안 시도하는 것들을 했기 때문입니다.)

팀워크 미스로 풀 수 있는 2문제를 못푼 GP of Spb 때문에 포인트를 많이 까먹었지만, 다음부터 그런 일이 일어나지 않게 신경쓰기로 했습니다.

문제 스포일러 입니다.

Eastern GP 문제 중 가장 좋다고 생각한 문제 F 입니다.

수열이 M개 주어진다. M!가지의 수열 배치 방법에 대해서, 모든 substring의 모든 숫자들 gcd 총합을 10^9+7로 나눈 나머지를 구하여라.

제한) M ≤ 8만, (수열 숫자) ≤ 8만, (수열의 길이 총합) ≤ 8만, 1초, 256MB

예시 입력)

3

2 1 2

1 1

1 2

예시 출력)

74

예시 설명)

3!가지 수열이 다음과 같이 있습니다.

1 2 1 2 : 12

1 2 2 1 : 13

1 1 2 2 : 13

1 2 1 2 : 12

2 1 2 1 : 12

2 1 1 2 : 12

그래서 총합이 74 입니다.