2023 Sogang Programming Contest Open (Master)

khj20006 2023. 11. 18. 21:44

2023 Sogang Programming Contest Open (Master)에 참가했다. 전날에 열렸던 Arena #11을 놓쳐서 이번에는 꼭 해야지 생각하며 등록을 하고 잔 것 같았는데, 일어나보니 등록이 안되어있었다. 아레나는 언제쯤 참가할 수 있을까..

00:06 AC

직전의 $L, R$ 값을 갖고 있으면서 매번 확인해주면 된다.

00:10 AC

$1, N, 2, N-1, \cdots$ 순으로 배치하면 된다.

00:23 AC

$L, R$에 해당하는 인덱스를 정렬시켜 $L$부터 $R$까지 사람에 대해 재배치하면 된다.

00:39 WA 00:39 WA 00:40 AC

$x$를 $xy$로, $xy$를 $y$로 만들어주면 주어진 조건을 항상 만족한다.

처음에 갈피를 못 잡아서 푸는 데 오래 걸렸다. 게다가 long long 실수와 '-'부호를 제대로 안 붙여줘서 두 번이나 틀렸다.

00:46 WA 00:49 AC

$dp[i]$를 다음과 같이 정의하자.

$dp[i] = \max \limits_{j, \,t_j < t_i - b_i}{dp[j]} + c_i$

가능한 $j$의 최댓값은 lower_bound로 구할 수 있고, 세그트리로 구간 최댓값을 구해줬다.

세그트리까지는 필요없을 것 같았지만 당장 생각나는 게 세그밖에 없었다.

01:02 AC

한 번의 베기로 같이 잘리게 되는 잡초들을 분리 집합으로 구한 뒤, 각 집합에서 (0,0)까지의 거리를 모두 구한다.

이 값들을 모두 두 배 곱하여 더하고 가장 큰 값만 한 번 빼주면 된다. (마지막 잡초를 벤 뒤엔 (0,0)로 돌아올 필요가 없기 때문)

01:31 AC

주어진 점들을 $X, Y$를 기준으로 봤을 때 반시계 방향으로 정렬해두고 이 순서대로 $A_1, A_2, \cdots$라고 하자.

$x$축 위의 임의의 점의 $x$좌표를 $g$라고 하고, 이 $g$가 가질 수 있는 범위를 유추해야 한다.

$A_i$와 $A_{i+1} \, (1 \le i < N)$이 이루는 직선이 $x$축과 만나는 점을 $p_i$라고 하면, $p_i$보다 크거나 작은 $g$에 대해 $(x, 0)$에서 봤을 때 동일한 순서를 얻을 수 있다는 관찰이 필요하다.

$A_i$의 $y$좌표가 $A_{i+1}$의 $y$좌표보다 작으면 $g < p_i$이어야 하고,

$A_i$의 $y$좌표가 $A_{i+1}$의 $y$좌표보다 크면 $g > p_i$이어야 한다.

둘의 $y$좌표가 같은 경우에는 $g$가 어떤 값이든 항상 동일한 순서를 얻을 수 있다.

$p_i$들을 모두 구했으면, 주어진 $x$좌표들 중 모든 조건을 만족하는 점들을 찾아주면 된다.

02:03 WA 02:08 WA 02:15 WA 02:19 WA 02:32 RTE 02:34 WA

※ "AC"가 아니라 틀린 생각일수도 있습니다!

관찰 1.

2번 연산을 반드시 2회이상 진행해야 모든 수를 동일하게 만들 수 있다. 1번 연산은 수의 위치만 바꿀 뿐이지 값을 변경하진 않기 때문이다.

관찰 2.

$M$번의 연산 중 마지막 연산은 반드시 2번 연산이어야 한다.

위의 관찰을 통해 나올 수 있는 연산의 배치는

2 1 2

2 1 1 2

1 2 1 2

이렇게 세 가지밖에 없다고 생각하고, 이대로 구현했지만 WA를 받았다. 놓친 케이스가 있는걸까.