Orange Cup 후기

자다 일어났더니 대회가 2시간 가량 밖에 남지 않았다. solved.ac 뱃지 기준인 100점만 넘기자는 마인드로 대충 풀었다.

 

C. ko_orange (02:45)

[2100, 2400) 구간 내에서 이분 탐색을 하는데, 쿼리의 답이 잘못 주어질 수 있다. 그냥 같은 쿼리를 두 번씩 물어봐서 첫 번째 서브태스크만 해결했다.

 

A. 오렌지컵 출제하기 (03:02)

문제를 준비 시간으로 정렬하고 작은 것부터 그리디하게 골라 나갔다. 고르면서 어떤 출제자가 L개 이상의 문제를 내야 한다면 그 문제를 뛰어 넘는다. 이렇게 하여 세 번째 서브태스크까지 해결했다.

 

이 문제를 풀고 총 점수가 88점이었기에 100점만 만들자는 생각으로 모든 문제를 한 번 훑어보면서 찍먹했다.

 

D. 오렌지 섬 여행하기 (04:14)

첫 번째 서브태스크를 해결하기 위해 직접 $n=7$까지 손으로 그려 보니, 왠지 모든 n에 대하여 오렌지를 다 먹을 수 있을 것 같았다.

만약 $n=i$일 때 오렌지를 전부 먹을 수 있는 경로가 있다고 하면, $n=i+1$일 때 인접한 두 정점 사이에 $i+1$을 잘 끼워 넣으면 된다. $i+1$이 두 정점과 서로소일 때 끼워 넣을 수 있다. 또는 맨 앞이나 맨 뒤에는 인접한 한 정점과 서로소이기만 해도 된다. 이런 조건을 만족하면서 N까지 그리디하게 끼워 넣다 보면 해결할 수 있다.

혹시 몰라서 assert를 넣은 채 제출했는데 한 번에 맞았다.

 

I. 오렌지 키우기 (04:16)

$K=0$이라면 심는 즉시 오렌지를 수확할 수 있고, 이는 오렌지를 심을 수 있는 지점에 방문하고 돌아오는 데 걸리는 시간과 같다. 따라서 오렌지를 심을 수 있는 지점 중 가장 먼 곳의 거리를 답이다. 이렇게 하면 첫 번째 서브태스크를 해결할 수 있다.