Codeforces Round #803 (Div. 2)

https://codeforces.com/contest/1698

 

FG가 상당히 어려워서 아래와 같은 블로그도 등장하는...

https://codeforces.com/blog/entry/104316

개인적으로는 Div2에서 2500 이상은 안 보였으면 좋겠다. 

 

A. XOR mixup

 

일일이 다해보면 된다.

 

B. Rising Sand

 

K = 1을 제외하면 too tall의 개수는 변하지 않는다.

K = 1이면 (N - 1) / 2 개를 억지로 too tall하게 만들 수 있다.

 

C. 3SUM Closure

 

양수나 음수가 3개 이상이면 어차피 안되고, 0도 3개 이상 있는 것은 답에 영향을 끼치지 않는다.

(양수들 + 음수들 + 0 3개 이하)로 새롭게 수열을 만들어 brute-force로 답을 확인해주면 된다.

 

D. Fixed Point Guessing

 

누가봐도 이분탐색. 

선택 방법은 (구간 내에 원래 있어야 하는 숫자의 개수)가 홀수라면 답이 될 숫자가 있는 구간이다.

 

E. PermutationForces II

 

문제를 잘못 읽어서 시간을 상당히 많이 버리게 되었다.

permutation의 가짓수를 구하는 문제인데, 경우의 수가 졸라게 많다.

게다가 dp를 쓰면 1차원 dp가 아닌 이상 n^2을 넘기 마련인데 n = 2e5라 dp도 아닐거라 예상.

무언가 아름답게 num1 * num2 * ... 로 답을 구할 수 있을 거라는 희망ㅌ

 

관찰 : '미리' x(!= i) 와 y를 바꾸는 행위는 무의미하다.

-> 현재 x와 y를 바꿀 수 있다면 어차피 나중에(x번째, y번째)도 이들의 위치를 조정하는 것이 가능하기 때문

-> 따라서 i번째에는 무조건 i번을 필요한 위치에 옮긴다고 생각해도 무방하다.

 

1) 만일 i가 b에 존재한다면

-> i를 그자리(idx)로 옮겨줄 수 있는지 판단해주면 된다.

claim) a[idx] <= min(i + s, n)인 것은 그 자리로 옮길 수 있는 것과 필요충분하다.

pf) 만족한다면 그냥 swap, 만족하지 않는다면 1 ~ i - 1번째에도 어차피 못 옮겨서 그 자리에 있었을 테니 여전히 못 옮김

 

2) 만일 i가 b에 없다면

-> a[idx] <= min(i + s, n)인 '?' 중 아무거나 가져다 준다.

claim) '?' 중 아무거나 가져다 줘도 (줄 수만 있다면) 어떤 위치든 상관 없다.

pf) 어차피 어느 자리에 옮기던 간에 원래 자리에 있던 숫자 i'은 다른 자리로 옮겨질 거라서 상관 없다.

 

사실 같은? 생각으로 마지막에 코드를 짰었는데 왜 틀렸는지는 잘 모르겠다.

문제를 잘못 이해 + 숱한 고치기로 코드가 누더기가 되어 이게 뭔지...

 

F. Equal Reversal

"Hi. We didn't think F would be hard" -> 7 official solves

 

a의 맨 마지막과 제일 앞에 있는 애들은 바꿀 수가 없다.

-> 생각했던 것은 그렇다면 혹시 앞에서부터 적절히 맞춰갈 수 있지 않을까? -> wa

 

Hint : What's an invariant of the array?

-> the set of unordered pairs of adjacent elements doesn't change as a result of the operations

-> 구간 [l, r]이 뒤집히더라도 여전히 (a[l-1], a[l]), (a[r+1], a[r])과 (a[l-1],a[r]), (a[r+1], a[l])이 같기 때문이다.

 

claim) 이거만 맞으면 만들 수 있다.

https://codeforces.com/contest/1698/submission/162160016

'이렇게' 하면 된다.

물론 증명은 안했지만 정확한 아이디어를 가졌는데 왜 틀렸을까

 

G. Long Binary String

 

Editorial : GF(2)에서 생각하면 우리가 하는 짓이 P(x) * Q(x)임을 알 수 있다.

-> 어떤 자리 k에 대해서 XOR을 해주는 과정을 P(x) * (x^k)을 더하는 것으로 생각할 수 있기 때문이다.

-> P(x) * Q(x) = x^k + 1이 되는 최소의 k를 구하고 뒤에 원하는만큼 0을 더해주면 답이 된다.

P(x) * Q(x) = x^k + 1이므로 x^k = 1 (mod P(x))이다.

이제 baby-step-giant-step로 풀 수 있다.

https://codeforces.com/contest/1698/submission/162160053

 

Non-mathy : 일단 제일 왼쪽에서 operation을 박는다. (이것이 최선임은 자명하다.)

만일 이때 3개 이상의 bit가 켜진다면 두 번째 비트를 지우기 위해 s의 첫 비트를 t의 두 번째 비트에 가도록 operate

-> 이 과정은 mod 2에서의 matrix multiplication임을 알 수 있다.

 

https://codeforces.com/contest/1698/submission/162243945

이쁜 풀이지만 뭘 한거지?