Codeforces Round #836

Dashboard - Codeforces Round #836 (Div. 2) - Codeforces

서론

역대급으로 조졌다. 원래 대회 끝나고 온라인 저지에서 놀다가 취침할 계획이었는데 포스팅하고 그냥 자련다.

 

A - SSeeeeiinngg DDoouubbllee

뒤집어서 붙이면 된다.

00:01 AC

 

B - XOR = Average

N이 홀수일 때는 바로 보이는데 짝수일 때는 도무지 처리할 방법이 보이지 않았다.

C번으로 넘어갔다가 C번도 조져서 다시 돌아왔다.

2로 도배하고 1과 3을 하나씩 추가하는 방법이 떠올랐다.

00:33 RTE

실수로 C번 소스를 제출하였다.

00:38 AC

 

C - Almost All Multiples

우선 N이 x의 배수가 아니면 답이 존재하지 않는다.

이후 풀이는 코드로 대체한다.

 

for i = x; i < N; i += x

    A[i] = i + x < N ? i + x : N;

00:13 WA

완전히 잘못된 코드이다.

(i + x)가 i의 배수가 아닐 수도 있다.

 

for i = x; i < N; i *= x

    A[i] = i * x < N ? i * x : N;

00:24 WA

역시 완전히 잘못된 코드이다.

(i * x)는 i의 배수이지만 N은 i의 배수가 아닐 수도 있다.

 

overflow 가능성이 있어서 long long 타입을 사용하였다.

하지만 로직 자체가 틀렸기 때문에 WA를 받는다.

00:29 WA

 

for i = x; i < N; i *= x

    A[i] = i * x < N && N % (i * x) == 0 ? i * x : N;

00:30 WA

이제 결과는 항상 funny permutation처럼 보인다.

WA를 받았다는 것은 사전 순으로 가장 앞서지 않는다는 것이다.

 

하지만 로직이 틀렸다.

A[i]에 N을 대입하는 순간 for 문을 중단시켜야 한다.

그렇지 않으면 결과는 permutation이 아닐 수도 있다.

for i = x; i < N; i *= x

    if i * x < N && N % (i * x) == 0 then

        A[i] = i * x;

    else

        A[i] = N;

        break;

00:33 WA

 

열 받아서 B번부터 처리하고 왔다.

x를 곱하는 것보다 2를 곱하는 것이 더 최적이다.

for i = x; i < N; i *= 2

    if 2 * i < N && N % (2 * i) == 0 then

        A[i] = 2 * i;

    else

        A[i] = N;

        break;

00:53 WA

 

가능한 상태를 전부 시도해보아야 한다.

위의 풀이에서 불가능한 경우라도 바로 N을 대입하면 안 된다.

j = 2 * i, 3 * i, 4 * i, ... 등 모두 시도해보아야 한다.

i가 커짐에 따라 가능한 j의 개수는 크게 감소하므로 시간 내에 돌아간다.

00:59 AC

 

페널티가 너무 커서 만회하려면 D번과 E번을 모두 풀어야만 하였다.

그리고 둘 다 못 풀었다.

 

D - Range = √Sum (not solved)

간단한 풀이가 전혀 떠오르지 않았다.

그래서 정말 복잡하게 짰다.

풀이는 다음과 같다.

 

N 이상의 정수 x에 대하여 다음과 같은 수열 A, B를 가정하자.

A: 1 2 3 ... (N - 1) x

B: 1 (x - N + 2) (x - N + 3) ... (x - 1) x

두 수열 모두 최댓값과 최솟값의 차이는 (x - 1)이다.

이때 수열의 모든 수에 어떠한 정수 y를 더하여도 최댓값과 최솟값의 차이는 변하지 않는다.

 

따라서 A와 B의 모든 원소에 y를 더하였을 때 sum(A) <= (x - 1)^2 <= sum(B)를 만족하는 y가 존재하는지 확인하면 된다.

조건을 만족하는 y가 존재하지 않는다면 다른 x에 대하여 반복하여 시도한다.

y가 존재한다면 수열 A에서 원소를 적절히 증가시켜 문제를 해결할 수 있다.

01:58 WA

01:59 WA

 

그리고 대회가 끝났다.

30초 후에 overflow 문제임을 발견하였다.

다른 곳에는 long long 도배해놓고 N은 int로 선언하였다.

시스텟 끝나고 제출하니 AC

 

굉장히 많이 풀렸길래 다른 사람들 풀이를 봤더니 정말 간단한 풀이가 존재한다.

항상 최댓값과 최솟값의 차이를 2N으로 만들 수 있다.

이를 발견하면 쉽게 푸는 것이고 안 보이면 고생하는 것이다.

나는 고생만 하다가 WA by overflow

 

E - Tick, Tock (not solved)

2022/12/21 업솔빙하였다.

주어지는 정보로 정점의 개수가 M개인 유향 그래프를 구성할 수 있다.

각 열을 하나의 정점으로 보면 된다.

 

그래프를 구성하는 가장 큰 목적은 주어지는 정보에 모순이 있는지 확인하는 것이다.

두 번째 예제를 보면 두 행의 정보가 서로 모순되는 것을 확인할 수 있다.

이 경우 clock grid는 solvable하지 않다.

그래프를 구성한 후 dfs를 돌려 이를 확인할 수 있다.

 

clock grid의 i번째 행 j번째 열을 cij라고 하자.

어떤 행 i에 대하여 cij와 cik가 empty cell이 아니라면 다음과 같은 간선을 추가한다.

ej = (j, k, (cik - cij + H) % H)

ek = (k, j, (cij - cik + H) % H)

제한이 크기 때문에 모든 (j, k) 쌍에 대하여 간선을 구성할 수는 없다.

다행히 인접한 쌍만 고려하더라도 동일한 결과를 얻을 수 있다.

 

모순이 없다면 이제 경우의 수를 세야 한다.

잘 관찰해보면 동일한 연결 요소 내에서 empty cell의 값은 유일하게 결정됨을 확인할 수 있다.

세 번째 예제를 보면 c41 = 420과 c44 = 999에 의하여 첫 번째 열과 네 번째 열은 동일한 연결 요소에 속하게 된다.

이때 c11 = 1이므로 c14 = 1 + (999 - 420) = 580으로 결정된다.

마찬가지로 c24 = 1000이므로 c21 = 1000 - (999 - 420) = 421로 결정된다.

 

또한 서로 다른 연결 요소를 합치는 경우의 수는 H이다.

다음 입력에 대하여 생각해보자.

4 4 4

0 1 -1 -1

1 2 -1 -1

-1 -1 2 3

-1 -1 3 0

하나의 empty cell의 값이 결정되면 나머지 empty cell의 값 또한 결정됨을 알 수 있다.

이때 하나의 empty cell의 값을 결정하는 경우의 수는 H이다.

따라서 두 연결 요소를 합치는 경우의 수는 H가 된다.

 

아직 고려할 부분이 남아 있다.

각 행에 대하여 non-empty cell이 존재한다면 empty cell의 값은 자동으로 결정된다.

하지만 모든 cell이 empty cell이라면 이야기가 달라진다.

하나의 empty cell의 값이 결정되어야만 나머지 empty cell의 값이 결정된다.

따라서 empty 행에서 clock을 배치하는 경우의 수는 H가 된다.

 

모든 사실을 종합하면 다음과 같다.

• 주어지는 정보에 모순이 있다면 답은 0이다.
• 그렇지 않다면 답은 H^(연결 요소의 개수 + empty 행의 개수 - 1)이다.

행과 열을 바꾸어서 생각해도 결과는 동일하다.

 

F - Decent Division (not solved)

Pass

 

끝

블루로 가자. 저 깊은 심해로 가자.

덕분에 오늘 밤 코포는 퍼플 복귀전이다.

퍼플 딱 대