[알고리즘] Codeforces Round #770 (Div. 2)

이번 코드포스의 결과는 굉장히 참담했다.

그래서 다시 그린으로 내려왔다.

멸망

A - Reverse and Concatenate [Solved!]

문자열이 주어졌을 때 다음 연산을 $k$번 하여 만들 수 있는 서로 다른 문자열의 수를 구하는 문제이다.

연산은 다음중 하나를 수행한다.

- 문자열을 뒤집어 원래 문자열 앞에 이어 붙인다.

- 문자열을 뒤집어 원래 문자열 뒤에 이어 붙인다.

 

우선 연산을 한 번이라도 수행하면 문자열은 팰린드롬이 된다.

또한 팰린드롬은 뒤집어서 어디에 이어 붙여도 같은 문자열이 된다.

결국 주어진 문자열이 팰린드롬인지 확인하는 문제로 환원된다.

다만 팰린드롬에 상관없이 $k=0$일 때는 답이 1이다.

A번부터 뇌절을 심하게 해서 4번틀리고 AC를 받았다. (발상이 상당히 힘들었다.)

 

B - Fortune Telling

배열 $a$가 주어지고 정수 $x,y$도 주어질 때 시작 값을 $x, x+3$으로 하여 각각 배열의 원소를 순서대로 다음 연산을 수행했을 때 $y$가 나오는 게 무엇인지를 찾는 문제이다.

연산은 다음 중 하나를 수행한다.

- 현재 숫자에 $a_i$를 더한다.

- 현재 숫자에 $a_i$를 xor한다.

둘 중 하나는 $y$를 만들 수 있음이 보장된다.

 

우선 $x, x+3$을 보면 둘중 하나는 홀수고 나머지 하나는 짝수가 된다.

또한 문제의 마지막 줄을 보면 둘 중 하나만 제대로 확인하면 나머지 하나는 확인을 안해도 된다.

일단 $\oplus, +$연산들은 LSB의 변화를 같게 한다.

즉 마지막 비트만 놓고 보면 두 연산 모두 xor연산이 된다는 뜻이다.

마지막 비트는 홀수 짝수를 정하는 비트이니까 이제 정확한 값은 안 구해도 되고 홀짝 여부만 판정하면 된다.

그럼 $x$에 $a$원소들을 모두 xor하거나 더해서 $x'$을 만들어 $y$와 홀짝이 같은지 확인하면 된다.

같은 경우 Alice승, 다른 경우 Bob승이다.

 

일단 문제 풀 때는 전혀 감도 못 잡았고 시도는 해봤으나 정해와 완전 다르게 접근했다.

Editorial 보니까 "와 이렇게 푸는 문제야?" 하는 소리가 절로 나왔다.

xor과 더하기의 공통점을 알게 된 문제였다. (코포풀면서 비트연산 연습이 많이 된다.)

문제의 여론이 좋지 않다.

 

C - OKEA

크기가 $n \times k$인 배열 $a$에 $1$~$nk$를 넣을 건데 $a_{i,1} = i$여야 하고 모든$i$와 $1\le l \le r \le k$에 대해 $a_{i,l}, a_{i,l+1},\dots, a_{i,r}$의 평균이 정수가 되도록 배치할 수 있는지 묻는 문제이다.

 

일단 $n=1$이나 $k=1$일 때는 가능한 배치가 존재하는 게 자명하다.

또한 임의의 평균이 정수라는 것은 등차수열이어야 한다.

$n \ge 2, k \ge 2$에서 공차가 홀수라면 $2, 3$같이 2개의 평균이 정수가 안되기 때문에 짝수여야만 한다.

그럼 경우가 4가지 생기는데 각 경우마다 필요한 홀수와 짝수의 개수를 구해보자.

* Case 1) $n, k$ 모두 홀수

필요한 홀수의 개수 : $(k-1)\frac{n+1}{2}$

필요한 짝수의 개수 : $(k-1)\frac{n-1}{2}$

 

* Case 2) $n, k$ 모두 짝수

필요한 홀수의 개수 : $(k-1)\frac{n}{2}$

필요한 짝수의 개수 : $(k-1)\frac{n}{2}$

 

* Case 3) $n$ 홀수, $k$ 짝수

필요한 홀수의 개수 : $(k-1)\frac{n+1}{2}$

필요한 짝수의 개수 : $(k-1)\frac{n-1}{2}$

 

* Case 4) $n$ 짝수, $k$ 홀수

필요한 홀수의 개수 : $(k-1)\frac{n}{2}$

필요한 짝수의 개수 : $(k-1)\frac{n}{2}$

 

확인해보면 $n$의 홀짝 여부에 따라 필요한 수의 개수가 달라진다.

$n$이 홀수일 때 홀수가 짝수보다 $\frac{k-1}{2}$개 더 필요하다.

일단 Case 3은 유리수개가 더 필요하게 돼서 모순

배치할 수 있는 홀수와 짝수의 개수의 차이는 많아야 1개인데 $k-1 \ge 2$이므로 모순

따라서 $n$이 짝수일 때만 올바르게 배치가 가능하다.