Codeforces Round 884

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

A - Subtraction Game

a + b

00:03 AC

 

B - Permutations & Primes

2와 3을 양쪽 끝에 두고 1은 가운데에 두면 된다.

00:11 AC

 

C - Particles

인덱스의 parity가 동일해야 합칠 수 있다.

배열 C를 인덱스의 parity를 기준으로 두 개의 배열로 분할하자.

각 배열에서의 답은 다음과 같이 계산할 수 있다.

• 배열이 비어 있다면 -INF
• 모든 값이 음수라면 배열의 원소 중 최댓값
• 그렇지 않다면 0 이상인 원소들의 합

00:23 AC

 

D - Row Major

N의 약수가 아닌 수 중 최솟값을 x라고 하자.

x개의 서로 다른 알파벳을 순서대로 N번 출력하면 된다.

00:29 AC

 

E - Great Grids (not solved)

관찰이 매우 중요한 문제이다.

우선 'A', 'B', 'C'를 각각 0, 1, 2로 바꾸어 생각해보자.

 

관찰 1. 인접한 두 셀의 차이(mod 3)는 1 또는 2이다.

관찰 2. A[i][j] - A[i][j + 1] ≡ A[k][j] - A[k][j + 1] (mod 3)

관찰 3. A[i][j] - A[i + 1][j] ≡ A[i][k] - A[i + 1][k] (mod 3)

 

따라서 마지막 행과 열을 제외한 모든 행과 열에 1 또는 2를 대응시킬 수 있다.

그리고 가능한 모든 대응에 대하여 이를 만족하는 great grid가 존재한다.

각 제약은 다음과 같이 해석할 수 있다.

• (x2, y2) = (x1 + 1, y1 + 1): 행 x1과 열 y1은 서로 다르다.
• (x2, y2) = (x1 + 1, y1 - 1): 행 x1과 열 y2는 동일하다.

이제 주어지는 제약에 모순이 있는지 확인하면 된다.

이는 곧 2-coloring problem이 되며 dfs 또는 Union-Find로 해결할 수 있다.

 

F1 - Min Cost Permutation (Easy Version) (not solved)

Pass

 

F2 - Min Cost Permutation (Hard Version) (not solved)

Pass

 

G - Tree Weights (not solved)

Pass

 

H - Multiple of Three Cycles (not solved)

Pass

 

끝

끝