Codeforces Round #833

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

A - The Ultimate Square

단순 수학

00:01 AC

 

B - Diverse Substrings

diverse string의 길이는 100을 초과할 수 없으므로 완전 탐색하면 된다.

00:13 AC

 

C - Zero-Sum Prefixes

그리디 풀이는 보자마자 떠올랐는데 반례가 있다고 생각하여 시도하지 않았다.

반례가 존재할 수 없음을 증명하는 데 오랜 시간이 걸렸다.

00:43 WA

증명까지 마쳤는데 WA를 받아서 당혹스러웠다.

overflow가 원인임을 깨닫는 데 10분이 넘게 걸렸다.

00:56 AC

 

D - ConstructOR

원본 문제는 다음과 같다.

a|x와 b|x를 d로 나누어떨어지게 만드는 x를 구하시오.

 

먼저 조금 더 단순한 문제를 정의하자.

a|x를 d로 나누어떨어지게 만드는 x를 구하시오.

이는 a의 비트를 적절히 켜서 a를 d로 나누어떨어지게 만들라는 것이다.

따라서 이 문제는 아래 문제와 동일하다.

a에서 사용하지 않은 비트만을 이용하여 (k * d - a % d)를 만드시오.

 

모든 비트를 고려하는 것은 복잡하다.

a가 사용하는 비트는 하위 30 비트로 한정된다.

따라서 우리는 상위 30 비트만을 조작하여 (k * d - a % d)를 만들 것이다.

만약 만들 수 없다면 해가 존재하지 않는다.

대회 중에는 proof by ac로 증명하였지만 실제로 증명이 가능하다.

 

c와 e를 다음과 같이 정의하자.

• c = (d - a % d) % d;
• e = (1 << 30) % d;

이제 아래 방정식을 풀면 된다.

• ex % d = c

해는 확장 유클리드 알고리즘으로 구할 수 있다.

해가 존재한다면 단순한 문제의 해는 (x % d) << 30 이다.

해가 존재하지 않는다면 단순한 문제의 해도 존재하지 않는다.

 

해가 존재하려면 c는 gcd(e, d)의 배수여야 하며 그렇지 않다면 해가 존재하지 않는다.

이때 gcd(e, d)는 lsb(d)와 동일하므로 해가 존재하지 않는다는 것은 c가 lsb(d)의 배수가 아니라는 것이다.

이는 c의 비트 중 lsb(d)의 하위 비트 일부가 켜져 있다는 것이다.

이미 켜져 있는 하위 비트는 조작할 수 없으므로 단순한 문제의 해는 존재하지 않는다.

따라서 방정식의 해가 존재하지 않는다면 단순한 문제의 해도 존재하지 않는다.

 

단순한 문제를 해결하였으니 원본 문제로 돌아오자.

원본 문제는 다음과 같이 단순한 문제로 변형할 수 있다.

a|b|x를 d로 나누어떨어지게 만드는 x를 구하시오.

 

해가 존재한다면 원본 문제의 해는 a|b|x 이다.

해가 존재하지 않는다면 원본 문제의 해도 존재하지 않는다.

 

해가 존재하지 않는다는 것은 a|b의 비트 중 lsb(d)의 하위 비트 일부가 켜져 있다는 것이다.

이는 a 또는 b의 비트 중 lsb(d)의 하위 비트 일부가 켜져 있다는 것이다.

이미 켜져 있는 하위 비트는 조작할 수 없으므로 원본 문제의 해는 존재하지 않는다.

따라서 단순한 문제의 해가 존재하지 않는다면 원본 문제의 해도 존재하지 않는다.

 

01:37 AC

 

솔직히 대회 중에는 감으로 풀었는데 실제로 증명하려니 너무 힘들다.

에디토리얼은 수식이 난무해서 안 읽었다.

조금 복잡하게 증명한 듯 하지만 스스로 증명한 것에 만족한다.

 

E - Yet Another Array Counting Problem (not solved)

분할 정복 + dp 문제인데 처음 보는 유형이라 신기하였다.

a[l .. r]의 leftmost maximum의 인덱스를 lmax라고 하자.

이때 다음과 같은 제약이 발생한다.

• b[l .. (lmax - 1)]에 속하는 원소는 b[lmax]보다 작아야 한다.
• b[(lmax + 1) .. r]에 속하는 원소는 b[lmax]보다 작거나 같아야 한다.

이를 이용하여 적절히 분할 정복 + dp를 하면 된다.

leftmost maximum의 인덱스는 Segment Tree로 구할 수 있다.

dp 테이블은 다음과 같이 정의할 수 있다.

dp[l][r][x] = 구간 [l, r]에서 b[lmax]가 x 이하이면서 조건을 만족하는 경우의 수

N이 크므로 적절히 2차원으로 압축해야 한다.

 

F - Circular Xor Reversal (not solved)

Pass

 

끝

끝