CodeTON Round 6

Dashboard - CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!) - Codeforces

서론

SCPC 후기를 쓰려다가 트로피 수령하고 쓰려고 미뤘다.

코포 이야기를 하자면, 정말 잘 봐서 또 다시 승급 기회가 생겼다.

 

A - MEXanized Array

A번 치고 조금 복잡하다.

우선 min(N, x + 1) < K이면 답은 -1이다.

그렇지 않다면 배열의 첫 K개 원소는 0, 1, 2, ..., (K - 1)로 채우자.

나머지 (N - K)개 원소는 x = K인 경우 (K - 1)로, 그렇지 않다면 x로 채우면 된다.

00:04 AC

 

B - Friendly Arrays

N이 홀수인 경우 연산을 수행하면 x는 증가하거나 변하지 않는다.

N이 짝수인 경우 연산을 수행하면 x는 감소하거나 변하지 않는다.

연산을 수행하지 않았을 때의 x를 a, 연산을 최대로 수행하였을 때의 x를 b라고 하자.

min(a, b)와 max(a, b)를 출력하면 된다.

00:11 AC

 

C - Colorful Table

2차원 배열 B의 생성 과정을 다음과 같이 생각해보자.

1. 배열 A에서 최솟값의 인덱스를 p라고 하자.
2. 배열 B의 p번 행과 p번 열에 속하는 셀 중 색칠되지 않은 셀을 A[p]번 색으로 칠한다.
3. p번 행과 p번 열에 속하는 셀은 모두 색칠되었으며 더 이상 다른 색을 칠할 수 없다.
4. A[p] = INF
5. 이 과정을 N번 반복한다.

잘 생각해보면 과정 2에서 색칠하는 범위는 (색칠되지 않은 셀이 존재하는 행 또는 열)의 최솟값부터 최댓값까지임을 알 수 있다.

배열 A를 정렬한 후 two-pointer로 색칠 가능한 범위를 잘 관리해주면 된다.

00:23 AC

 

D - Prefix Purchase

i < j and c_i >= c_j이면 i번 구매 방법은 유효하지 않다.

stack을 이용하면 유효한 구매 방법만을 남길 수 있다.

유효한 구매 방법만 남았다면 다음과 같이 그리디하게 구매하면 된다.

1. 첫 번째 구매 방법으로 최대한 구매한다.
2. 첫 번째 구매를 일부 취소하여 두 번째 방법으로 최대한 구매한다.
3. 두 번째 구매를 일부 취소하여 세 번째 방법으로 최대한 구매한다.
4. ...

00:31 WA

 

구매를 취소할 때 취소 횟수가 구매 횟수를 초과하지 않도록 주의해야 한다.

00:35 AC

 

E - Another MEX Problem

O(N^3) 풀이는 금방 생각나지만 제한을 보면 O(N^2)으로 풀어야 한다.

MEX의 성질을 잘 이용하면 O(N^2)으로 커팅이 가능할 것처럼 보였다.

 

우선 O(N^3) 알고리즘은 다음과 같다.

for i = 1; i <= N; ++i

    mex = 0;

    for j = i; j <= N; ++j

        update_mex();

        for k = 0; k < 8192; ++k

            if dp[i - 1][k] then

                dp[j][k ^ mex] = true;

 

2차원 dp 배열을 bitset의 배열로 선언하고 mex가 실제로 업데이트되는 순간에만 dp 배열을 업데이트하도록 하였다.

00:51 TLE

 

bitset의 크기를 8192로 고정하지 않고 N의 값에 따라서 적절한 크기의 bitset를 사용하도록 하였다.

00:58 TLE

 

단순한 방법으로는 뚫리지 않는다는 것을 인지하고 더 많은 최적화를 추가하였다.

1. A[i]가 MEX(A[i .. N])보다 크다면 A[i .. j] 구간은 시도하지 않는다.
2. A[i] = A[j]인 j를 만났다면 이후 구간은 더 이상 시도하지 않는다.
3. MEX(A[i .. j]) = MEX(A[i .. N])이라면 이후 구간은 더 이상 시도하지 않는다.

01:12 AC

Proof by AC, 시간 복잡도 증명은 나도 모르고 알고 싶지도 않다.

 

F - Lazy Numbers (not solved)

Pass

 

G - MEXanization (not solved)

26095번의 강화 버전이다.

남은 시간 동안 붙잡았는데 풀 수 없었다.

에디토리얼을 보니 다행히 내가 풀 수 없는 문제였다.

 

H - Standard Graph Problem (not solved)

Pass

 

끝

그는 과연 찐렌지에 갈 수 있을 것인가.

일요일에 발표됩니다.

끝