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

이번에 처음으로 Div.2 에서 3솔을 하고 민트를 갔다!

당분간 3솔이 편해질때까지 버추얼만 참가할 예정...

 

A - ABC [Solved!]

이진 문자열의 부분문자열 중 길이가 2이상인 팰린드롬이 있는지 찾는 문제이다.

 

보자마자 매내처생각나서 제출하고 AC를 받았다.

끝나고 생각해보니 그냥 부분문자열 길이 2이상 3이하인 팰린드롬 찾아도 풀 수 있었다.

 

B - Roof Construction [Solved!]

$n$이 주어졌을 때 배열 $(0,1,2,..., n-1)$의 순열중 인접한 xor값의 최댓값을 최소로 하는 배열을 찾는 문제이다.

 

접근방법이 도저히 생각안나서 C풀고 온 후 남은 90분 B풀고 끝낼 생각으로 천천히 풀었다.

우선 $n=2$~$10$까지 모든 순열에 대해 xor값의 최댓값을 구했더니 아래와 같이 나왔다.

$2 \rightarrow 1$

$3,4 \rightarrow 2$

$5,6,7,8 \rightarrow 4$

$9,10 \rightarrow 8$

이렇게 사상하는 함수를 $f(n)$이라 하자. ($f(3)=2$)

그러면 $f(n)$은 $n-1$의 최상위 비트만 $1$인 $2$의 제곱수가 나올것이다.

$f(n) \le a,b < n$에 대해서 $a \oplus b < f(n)$이 성립한다. (최상위 비트가 사라지기 때문)

또한 최댓값은 $f(n)$이어야 하므로 $f(n)$은 $0$과 인접해야한다.

$a<f(n)$에서 $ a \oplus f(n) > f(n)$이다. (최상위비트가 생기기 때문)

위 조건을 만족하도록 적당히 배치시키면 된다.

 

C - Strange Test [Solved!]

$a,b$가 주어졌을 때 다음 연산들을 활용하여 $a=b$를 만드는 최소 횟수를 구하는 문제이다.

- $a:=a+1$

- $b:=b+1$

- $a:=a|b$

 

그냥 브루트포스로 해결한것 같다.

일단 $a|b=c$이면 $a, b \le c$이다.

즉 or연산 후엔 수가 커지기 때문에 한번만 사용해도 충분하다.

여러 가능한 경우의 횟수들을 구하고 그들의 최솟값을 구해서 풀었다.

* Case 1)

$a|b=b$가 될 때까지 $a$를 증가시킨다.

* Case 2)

$a|b=b$가 될 때까지 $b$를 증가시킨다.

* Case 3)

$a,b$중 작은 값을 $c$라고 하고 다른 값을 $d$라고 하자.

$ |c+1-d|, | c- a | b  |$중에서 더 작은 연산을 수행하면 된다.

(그래서 이게 왜 되죠?)

 

비트연산.... gcd....