Pinely Round 2

Dashboard - Pinely Round 2 (Div. 1 + Div. 2) - Codeforces

서론

찐렌지 승급전이었다.

D번까지 풀었을 때 LGM 퍼포가 나왔고 ainta님보다도 앞서 있었다.

하지만 E번에서 엄청난 뇌절을 하였고 레이팅은 미국으로 떠나버렸다.

 

A - Channel

모든 구독자가 online인 순간이 있었다면 답은 YES이다.

a + ('+'의 개수)가 N 이상이라면 답은 MAYBE이다.

이도 저도 아니라면 답은 NO이다.

00:03 AC

 

B - Split Sort

다음과 같은 배열 B를 정의하자.

B[i] = i가 배열 P에서 등장한 인덱스

B[i] > B[i + 1]이라면 답이 1만큼 증가한다.

00:06 AC

 

C - MEX Repetition

A[N + 1] = MEX(A[1 .. N]);

K %= N + 1;

rotate(A.begin(), A.end() - K, A.end());

00:12 AC

 

D - Two-Colored Dominoes

모든 행과 열에 대하여 도미노가 놓여진 셀의 개수는 짝수여야 한다.

만약 그렇다면 각 행에 대하여 U와 D의 개수는 짝수이다.

그리고 각 열에 대하여 L과 R의 개수는 짝수이다.

 

각 행에 대하여 홀수 번째 U는 검은색으로, 짝수 번째 U는 하얀색으로 칠하면 된다.

그리고 각 열에 대하여 홀수 번째 L은 검은색으로, 짝수 번째 L은 하얀색으로 칠하면 된다.

00:19 AC

 

E - Speedrun

뇌절하기 쉬운 문제인 것 같다.

나 역시 뇌절을 너무 많이 해서 대회 중 풀이 과정은 적지 않으려고 한다.

대회 중에 짠 코드가 180 라인이고 업솔빙하면서 짠 코드가 60 라인이다.

실력이 많이 부족하였고 딱히 변명거리는 없다.

00:49 WA

01:58 WA

02:11 WA

02:25 WA

02:28 AC

 

위상 정렬 + dp를 이용하면 quest i를 완료할 수 있는 최소 시각을 구할 수 있는데 이를 dp[i]라고 하자.

그리고 선행 quest가 없는 quest를 시작 quest라고 하자.

quest i가 시작 quest라면 0 <= dp[i] < K를 만족한다.

시작 quest 일부를 다음 날에 완료하면 전체 수행 시간이 감소할 수도 있다.

이틀 뒤 또는 그 이후에 완료하는 경우는 고려하지 않아도 된다.

 

역방향으로 dp를 수행하면 다음과 같은 배열 B를 구할 수 있다.

B[i] = max(dp[{quest i를 다음 날에 완료할 때 완료 시각이 변경되는 quest}])

quest u와 v 사이에 선행 관계가 있고 dp[u] + K > dp[v]라고 가정하자.

이 경우 quest u를 다음 날에 완료하면 quest v의 완료 시각도 변경된다.

dp[u] + K <= dp[v]인 경우 quest v의 완료 시각은 변하지 않는다.

 

모든 시작 quest i에 대하여 {dp[i], B[i]} 쌍을 구성하고 이를 정렬하자.

시작 quest i를 다음 날에 완료하면 마지막 quest의 완료 시각은 max(기존 완료 시각, B[i] + K)가 된다.

첫 번째 quest와 마지막 quest의 완료 시각을 적절히 조정하면서 전체 수행 시간의 최솟값을 구하면 된다.

 

F - Divide, XOR, and Conquer (not solved)

Pass

 

G - Swaps (not solved)

Pass

 

H - Goldberg Machine 3 (not solved)

Pass

 

I - Redundant Routes (not solved)

Pass

 

끝

언젠가 다시 기회가 올 것이라고 믿는다.

찐렌지를 찍기에는 아직 많이 부족하다.

끝