Educational Codeforces Round 139

Dashboard - Educational Codeforces Round 139 (Rated for Div. 2) - Codeforces

A - Extremely Round

전처리

00:02 AC

 

B - Notepad#

길이가 2이며 서로 겹치지 않는 동일한 substring이 존재하는지 확인하면 된다.

00:07 AC

 

C - Hamiltonian Wall

첫 번째 열에서 3방향으로 그리디하게 탐색하여 모든 셀을 방문할 수 있는지 확인하면 된다.

00:19 WA

방문 순서가 중요한데 위 또는 아래로 이동이 불가능할 경우에만 오른쪽으로 이동해야 한다.

00:25 AC

 

D - Lucky Chains

d = y - x라고 정의하자.

gcd(x + k, y + k) = gcd(x + k, x + d + k) = gcd(x + k, d)임을 이용한다.

d가 1이면 답은 -1이 된다.

그렇지 않다면 d를 소인수분해하면서 각 소인수마다 k의 최솟값을 계산하면 된다.

00:39 AC

 

E - Decomposition (not solved)

우선 0은 별도로 처리할 수 있으므로 0은 고려하지 않는다.

sequence [x1, x2, ..., xk]에서 인접한 중복 원소를 제거한 sequence를 X라고 하자.

이때 f([x1, x2, ..., xk]) = f(X)이며 그 값은 다음과 같이 판별할 수 있다.

• X가 비어 있다면 f(X) = 0이다.
• X가 비어 있지 않다면 f(X) = 1이다.
• X가 subarray [1, 2] 또는 [2, 1]을 포함한다면 f(X) = 2이다.
• X가 subarray [1, 2, ..., 3, 2, 1] 또는 [2, 1, ..., 3, 1, 2]를 포함한다면 f(X) = 3이다.
• f(X)의 값은 3을 초과할 수 없다.

각 i에 대하여 sequence [ai .. aj]가 subarray b를 포함하게 만드는 j의 최솟값을 구해야 한다.

이는 전처리 후 이분 탐색으로 구할 수 있다.

대회 중에 코딩까지 마쳤으나 일부 논리가 잘못되어 WA를 받았다.

각 i에 대하여 decomposition의 두 번째 원소는 결정적임에 유의해야 한다.

 

정해는 dp이며 다음과 같은 점화식을 세울 수 있다.

dp[i][j][k][l][m] = 인덱스 i에서 decomposition의 상태가 (j, k, l)일 때 길이가 m이 되는 인덱스 중 최솟값

dp 풀이가 이분 탐색 풀이보다 간결하고 가독성이 높다.

 

F - MCF (not solved)

Pass

 

끝

끝