2021 ICPC Sinchon Summer Algorithm Camp Contest 후기

5등까지 상품이 나가는데, 시작하고서 가벼운 마음으로 대충 문제 훑어보다가 5~10분 정도 날렸다. 만약에 바로 A번 잡고 풀었다면 3솔도 할 수 있었는데 아쉬웠다.

 

A. permutation making (00:14)

최대한 누적합이 같게 만들어줘야 한다. 누적합을 N으로 나머지 연산을 하므로, N의 배수들은 모두 똑같이 0으로 취급된다. 따라서 누적합이 N의 배수가 나오도록 N, 1, N-1, 2, N-2, ... 이렇게 배치해주면 된다. 그러면 홀수 번째 원소들은 모두 같고, 짝수 번째 원소들은 다 다르므로 조건을 만족한다.

 

D. 신촌 수열과 쿼리 (01:16)

2번 쿼리를 살펴보면, 구간 [l, i]에서 모든 원소가 j 이상이 되도록 l을 최대한 감소시키고, 구간 [i, r]에서 모든 원소가 j 이상이 되도록 r을 최대한 증가시키면 된다. 최솟값 세그트리를 사용해서 구간 [l, i] 또는 구간 [i, r]에 j보다 작은 원소가 있는지 O(logN) 안에 찾을 수 있다. 이분 탐색을 한 번씩 사용해서 조건을 만족하는 동안 l의 최솟값 그리고 r의 최댓값을 각각 구할 수 있다. 이렇게 하여 O(log log N) 안에 2번 쿼리를 해결할 수 있다.

1번 쿼리는 그냥 세그트리에 update해주면 된다.

문제를 잘못 읽어서 굉장히 헤멨다. 2번 쿼리의 구간에 i가 포함되어야 한다는 조건을 놓쳐서 머지소트트리+금광세그를 짜야 하나 고민했다.

 

G. 신촌방위본부 (업솔빙)

나무가 불에 타는 조건은, 내분점 공식과 동일하다. 즉, 미사일이 떨어진 좌표를 이어서 만든 도형의 내부(모서리에 걸친 점도 포함)에 있는 모든 나무가 불에 탄다는 뜻이다. 미사일이 떨어진 좌표들의 볼록껍질을 구하고 볼록다각형의 넓이를 구한다. 볼록다각형이 격자점 위에 있으므로 픽의 정리를 이용하면 다각형 내부에 있는 점의 개수를 구할 수 있다. 여기서 볼록다각형의 내부에 있는 보호막의 개수만큼 빼면 답이 된다.

미사일의 수가 2개 이하인 경우는 볼록다각형이 만들어지지 않으므로 예외처리를 해줘야하는데, 다 짜고 이 예외처리 부분을 짜다가 대회가 끝났다. 딱 3분만 더 있었다면 맞을 수 있었는데 매우 아쉽다.