SCPC 2022 풀기

1차 기간동안은 어디 밖에 있느라고 제대로 못풀었는데 어떻게든 겨우 커트라인은 넘겼고,

어제가 2차 예선이었다.

본선은 언제쯤 갈 수 있을까...

 

2차 문제 설명과 풀이는 여기에 잘 나와 있다.

https://blog.kyouko.moe/74

SCPC 2022 2차 풀이

내가 풀면서 적은 시행착오만 간략히 적어보려고 한다. 

<스포일러에 주의하세요>

 

1번.

약간 코드포스 같은 문제. 일단 수열이 나오고, 원래라면 증명해야 하지만 직관으로 풀어내는 듯한 느낌이다. 

연산 횟수가 최우선이므로, 연산 횟수만 줄일 수 있게 양 끝 구간을 잡아서 그리디하게 풀어주면 된다.

int / long long 범위 때문에 한번 틀리고 맞았다.

지금 보면 쉬운데 풀 때는 80분이나 걸렸다.

 

2번.

수열에서 숫자 쌍들을 뽑아 그 사이 거리값을 점수로 하여 최고점을 내는 문제이다.

구간에서 뽑혀 나가는 쌍들은 세그먼트 트리에 기록하여 구간 별로 몇 개가 나갔는지 logN 으로 기록하고 볼 수 있게 하면 된다...

고 생각했는데 자꾸 마지막 부분 점수에서 시간 초과가 나왔다.

직접 최대 크기 예제를 만들어 입력으로 주었을때 7초 가량이 나왔다. (제한은 3초)

분명 N logN 인데 왜 이러지 해서 해서 fread도 써보고 구간 별 실행 속도도 측정해 보는 등 별 시도를 다 해 봤다.

결국 찾아낸 문제는 내가 짠 수열에서 pair를 찾는 부분이었는데, value를 index로 하는 2차원 벡터 안에, value의 수열에서의 index들을 저장하고, 이 deque의 front와 back을 pair 매칭 하는 방식으로 짠 부분이 문제였다. ( vector<deque<int>> v2idx(N); v2idx[value].push_back(index) ).

뇌피셜이지만 입력 숫자가 많다 보니, push_back에서 시간이 많이 걸렸다. 하지만 visual studio 에서 최대 크기의 input을 받아 한 속도 측정에서는 이 부분에서 시간 차이가 유의미하지 않았는데, 아마 이건 내가 만든 최대 크기 입력 예제가 하나의 value 부분에만 push_back을 하는 것이었기 때문에 그랬던 것으로 보인다. 실제 채점에서 여러 value를 계속 바꿔가며 push_back을 한다면 캐시를 제대로 못 사용해서 오래 걸릴 수도 있을 것 같다.

{value, index}와 {value, -index} 벡터를 정렬하여 같으 위치끼리 pair를 삼는 방식으로 다시 고쳐서 시간내에 실행시켰다.

2번에만 4시간이나 소요되었다.

 

3번.

일단 그래프가 싫었고, 방향이 있는 간선인데다가, 루프까지 있는데, 중간에 0,1,2, ∞까지 규칙을 무시하고 스킵할 수 있는 예외 케이스까지 존재한다? 문제를 보자마자 끔찍해보여서 도망쳤다.

 

4번.

할만하다 싶었는데, 일단 4번이라는 문제 번호의 중압갑에 거의 쳐다보지도 않았다.

 

5번.

확률/경우의 수 문제, 링크의 풀이대로 O(NK)로 부분점수 2번까지 받았다.

마지막 부분점수까지 받으면 150점이라 욕심부리다 시간을 꽤 썼다.

이항계수, 지수 log 시간에 구하기 등 다양한 지식들을 총 동원해 봤고, 나중에는 문제에 적혀있는 "XOR 연산은 문제의 풀이와 관계 없습니다." 까지 무시한 채 등비급수의 덧셈 대신 XOR 연산을 처리하는 방법까지 진지하게 고민했었다.

결국 도저히 이건 시간을 줄일 수 없다는 결론을 내리고 약 3시간만에 도망쳤다.

 

이제 남은 시간은 약 2~3시간. 다시 3번으로 돌아와서.

일단 루프를 처리해야 한다는 생각에 DFS를 골랐고,

모든 N개의 노드에서 출발하는 DFS로 다 찾아보겠다는 방식으로 부분 점수를 받아보겠다는 생각이었다.

하지만 인간이 집중력이 가장 떨어지기 시작한는 시간... 8시간을 넘기면서 (과학적 근거 없음) 에러와 예외가 속출하더니 그냥 시간이 끝나버렸다. 4번이나 풀어볼 걸 그랬다.

 

----

 

종료된 후, 가장 궁금했던건 역시 5번을 O(NK)보다 줄이는 방법이었다.

이름조차 생소한 생성함수를 이용한다니... 이산수학의 영역에 무한대를 데려와 문제를 풀어내는, 오늘도 알고리즘의 끝없는 깊이에 놀란다...

 

전체적으로 각 문제를 푸는데 너무 오래 걸렸다는 느낌이 들었다.

각 문제의 부분 점수 1번 까지는 순식간에 끝낼 수 있어야 하지 않을까?

이제 scpc 하는 날도 얼마 안남았다...