이번에 처음으로 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....
'프로그래밍 > 알고리즘' 카테고리의 다른 글
[알고리즘] Codeforces Round #751 (Div. 2) (2) | 2022.02.04 |
---|---|
[알고리즘] Educational Codeforces Round 122 (Rated for Div. 2) (0) | 2022.02.01 |
[알고리즘] 2022 중앙대학교 CHAC (0) | 2022.01.30 |
[알고리즘] Codeforces Round #768 (Div. 2) (0) | 2022.01.29 |
[알고리즘] 이분탐색 (0) | 2021.12.23 |