ICPC 2017 인터넷 예선 업솔빙 후기

첫 팀연습이다 ~ ! 한 명은 작년에 함께 했던 친구이며 ICPC에 매년 나오는 쌩구현 문제를 담당하고, 한 분은 올해 새로 영입했으며 수학(!!)을 매우 잘하신다. 올해 팀 구성 꽤 좋당!! 나는 음료수 서빙해야지 오예 셋이 합쳐서 총 6문제를 풀었으며, 마지막에 각자 EFG를 잡고 있었는데, 다들 학기 중에 코딩을 쉬던 상태라 삽질을 많이 해서, 더 잘할 수도 있었을 것 같다.

 

인터넷 예선이라 그런지 전형적인 문제가 많았다. EFGL도 플래이니만큼 굉장히 풀만했던 문제인 것 같으며, 팀연습 후 개인 업솔빙을 통해 FGL을 풀어보았다. 플래 중에서는 #D Grashoppper Route, #E Jerry and Tom, #G Map Labeling이 굉장히 좋은 문제라고 생각한다. 내가 푼 문제에 대해서만 간단히 풀이 스케치를 하겠다.

 

 

#A Closest Pair (골5, 연습 중 해결)

a[i]를 기준으로 대응되는 b의 lower_bound의 인덱스와 그 전 인덱스만 처리해주면 된다.
물론 투포인터로 슥슥해주는 게 조금 더 빠르지만, 나는 STL의 노예 ~ 구현 시렁

 

#B Cycle Mean (다1)

다1 못 품ㅋ

 

#C Flow Graph Complexity (플3)

친구가 풀었다. 친구 자력 플래 너무 믿음직하고 ~
ICPC에 항상 한 문제씩 나오는 파싱 + 구현 문제이며 이건 업솔빙 하고 싶지 않았다.

 

#D Grasshopper Route (플2, 연습 중 해결)

자력 플2 기분 좋고 ~
약간 짤게 많은데, 우선 다음과 같은 함수가 필요하다.

자신의 서브 트리를 생각하고 그 위에서 전위순회와 후위순회를 반복한다. 다음 노드에 방문 표시를 하고 (아직 방문하지 않는다/후위순회), 그 다음 노드에서 함수를 재귀호출한다. 방문 표시를 한 노드는 자신의 자식들의 재귀호출이 끝나면 방문한다.

자세한 건 코드를 보자.

void route(int a){
    if(vst[a]==1) return;
    vst[a]=1; ans.push_back(a);
    for(int i=0;i<G[a].size();i++){
        int nhop = G[a][i];
        if(vst[nhop]) continue;
        vst[nhop]=1;
        for(int j=0;j<G[nhop].size();j++){
            int nxt = G[nhop][j];
            if(vst[nxt]) continue;
            route(nxt);
        }
        ans.push_back(nhop);
    }
}

s에서 t로 가는 경로에 있는 각 노드에서 저 함수를 실행시키면 되며, 부모노드는 다음 노드로 보면 된다. 이는 잠깐 방문표시를 해둠으로 구현할 수 있다. 예외적으로 t는 t에 연결된 다음 노드에서 저 함수를 실행시켜야 한다. t를 마지막에 방문해야하기 때문이다.

저 함수를 어느 지점에서 실행시키느냐에 따라서, 거리가 4 이상이 될 수 있기 때문에 살짝 주의해서 짜야한다.

 

#E Jerry and Tom (플3)
각 쥐가 나갈 수 있는 구멍은 Naive하게 선분교차 판별해주면 되고, 탈출 가능성은 간단히 플로우 모델링하면 된다.

두 과정이 독립이기에 시간복잡도도 그리 크지 않다.

케이스 처리하는 게 많아보인다. 개인 업솔빙은 친구만 했다 ㅎㅅㅎ;;

 

#F Leftmost Segment (플1, 개인 업솔빙)

누가봐도 CHT

연습 중 20분 남은 시점에서 내가 잡았는데, 아무생각 없이 직선을 정렬 안하고 넣다가 틀렸다.

double로 짜야한다는 점과 기울기가 같은 직선이 입력으로 들어올 수 있다는 사실도 주의하자.

 

#G Map Labeling (플4, 개인 업솔빙)
순수 DP 플4이니만큼, 구현 구조 짜는 거나 반례 처리가 은근 어려운 편인 것 같다.

dp[i][0] = i번째 label의 우측 끝이 feature의 끝에 붙어있는 경우

dp[i][1] = 바로 붙어있는 건 아닌데, 선형 커넥터로 연결된 경우

이렇게 나누어서 dp[i][0]을 기준으로 dp[i+1]~dp[n]을 갱신해주면 된다.  $O(N^{2})$

갱신할 때는, 라벨을 그냥 바로바로 이어붙이며 선형커넥터를 사용 가능하면 dp[j][1]을 갱신해주다가, 우측 끝 공간이 남는 경우에는 dp[j][0]도 갱신하면 된다. 자세한 건 코드를 보자.

for(int i=1;i<=n;i++) dp[i][0]=n-1, dp[i][1]=INF;
for(int i=1;i<=n;i++){
    int now=arr[i].x, cnt=0;
    for(int j=i+1;j<=n;j++){
        if(now<=arr[j].x && now+arr[j].length>arr[j].x) cnt++;
        dp[j][1]=min(dp[j][1],dp[i][0]-cnt);
        now += arr[j].length;
        if(now<=arr[j].x){
            dp[j][0]=min(dp[j][0],dp[i][0]-cnt-1);
        }
    }
}

#H MultiMax (실5)

실버 ~ 친구가 풀었다

 

#I Pizza Boxes (실2)

실버 ~ 친구가 풀었다

 

#J Pseudoknot (다2)

다2 못 품 ㅋ

 

#K 등록 (브5)

브론즈 ~ 그 유명한 등록

 

#L Telescope (플2, 개인 업솔빙)

누가봐도 FFT 기본형 슥슥
이미 스포 당했어서 연습 중에는 안 건드렸다

 

---

다이아에 도전하는 일도 중요하다고 생각하지만, 다12는 선넘 ...

종강했으니 다5파밍을 하고 나면 ICPC 전에는 풀 수 있게 되지 않을까?

 

---

우리팀 좀 많이 틀리지만, 첫 연습치고 솔브수 괜찮은 것 같다.
팀연습을 통해서는 팀 합6문제를 풀었으며, 개인 업솔빙 이후, 내가 푼 문제는 총 8문제(브실포함)이다.

모두가 업솔빙한 문제를 or 연산하면 무려 10문제 .. ! 플래 한가득 세트라 가능한 일인 것 같다 ㅎㅅㅎ ~

 

여튼 새로운 팀원도 좋고, 각 팀원 성향이 크게 다른 점이 마음에 든다. 서로 나눠서 문제 푸는 과정이 너무 재밌다.