leo020630의 블로그

전날 있던 Div. 2에서 2095->1943이라는 기염을 (또) 토한 터라 멘탈이 좋지는 않았다. Div. 1에서 오른 적이 거의 없던 터라 좀 무섭기도 했고.. 그래도 레이팅이 엄청 낮아져 있었기 때문인지 어떻게 오르긴 한 것 같다. A. Weird Sum (00:38, +) Div. 1에서의 흥망을 가르는 요인은 A라고 생각한다. 그리고 나는 대부분의 Div. 1에서 A만 보면 뇌가 굳는다. 이번 역시 그랬다. 스코어보드는 10분만에 초록색이 쫘르륵 깔리는데 나는 감이 하나도 안 왔다. 30분을 넘게 생각한 후에야 정해도 아닌 $O(NsqrtN)$ 시간복잡도의 풀이를 찾아서 해결할 수 있었다. 이때만 해도 엄청 망할줄 알았다. B. Integral Array (01:01, +1) 문제를 처음 봤..

오렌지를 처음 찍은 후부터 이 라운드 전까지 총 3개의 rated 라운드를 쳤다. 결과는 -81, -9, -115로 많이 좋지 않았다. 첫 라운드에서는 A에서 크게 말렸고, Div.2 C에 세그를 두개 박는 오버오버킬을 하고 나서야 해결할 수 있었지만 그 때는 이미 대회 시작 후 1시간이 지난 시간이었기 때문에 좋지 못한 결과로 대회를 마무리해야 했다.두번째 라운드는 비교적 평이하게 진행되었으나, C를 4번 틀리고도 해결하지 못한 점이 아쉬웠다. 화룡점정은 본 글에서 다루는 라운드 바로 하루 전에 진행된 컨테스트였다. Div.2 였음에도 불구하고 2솔로 대회를 마무리했다. 퍼포먼스는 무려 민트였으며, 그런 경험은 굉장히 오랜만일 뿐더러 C가 그렇게 어려운 문제도 아니었기 때문에 멘탈이 나간 주 원인이 되..

최근에 참여한 백준 대회 3개에 대해서 간략한 후기를 작성하려 한다. Good Bye, BOJ 2021 A. 2021은 무엇이 특별할까? (1 try, 00:02) 실버 하위 난이도의 구현 문제라 가볍게 구현해주었다. B. 예쁜 케이크 (1 try, 00:08) 언뜻 보았을 때 Hard한 소인수분해 알고리즘이 필요해 보여서 당황했지만, 식을 잘 들여다보니 답이 될 수 있는 경우는 $9k$ 또는 $3k+2$ 꼴이라는 것을 알 수 있었다. C. 성싶당 밀키트 (1 try, 00:18) 최근에 코드포스에서 파라메트릭 문제를 많이 보아서인지, 보자마자 파라메트릭이라는 것을 떠올릴 수 있었다. 오버플로우 처리가 약간의 issue였으나, 오버플로우가 생길 만한 범위라면 어차피 답이 되지 못해 상관없는듯 하다..

A. The Miracle and the Sleeper (00:02, +) $r%max(l,r/2+1)$이 답이다. B. Scenes From a Memory (00:12, +) 관찰을 통해 자리수를 무조건 2이하로 만들 수 있다는 것을 알 수 있다. 이를 토대로 나이브하게 구현하면 된다. C. Rings (00:43, +1) 다음과 같은 관찰이 필요하다 : 어떤 이진수의 앞이나 뒤에 0을 붙여도 주어진 조건을 만족한다. 따라서, 주어진 문자열에 0이 하나라도 포함되어 있으면 더 긴 쪽으로 연결시켜 주면 된다. 전부 1인 경우엔 $[1,n-1]$과 $[2,n]$을 호출하는 방법과, $n$이 짝수인 경우에 길이가 $n/2$인 수가 약수가 된다는 점을 이용하는 방법 등 다양한 풀이가 존재한..

A. There Are Two Types Of Burgers (00:04, +) 더 비싼 버거를 최대한 많이 만들어준 후 남은 빵으로 다른 버거를 만들어주는 것이 최적이다. B. Square Filling (00:08, +) 그리디하게 칠해준 후 두 배열이 같은지 확인하면 된다. C. Gas Pipeline (00:31, +) 길이가 2이상인 0을 만날때 마다 비용이 더 적은 경로로 이어주면 된다. D. Number Of Permutations (00:50, +) 전체 경우의 수인 $N!$에서 첫 배열로 정렬할 수 있는 경우와 둘째 배열로 정렬할 수 있는 경우를 빼준 후, 둘 모두로 정렬 가능한 경우를 더해주면 된다. 각 경우는 연속된 같은 수의 갯수만큼 팩토리얼을 해주면 구할 수 있다. E. XOR..

A. Simply Strange Sort (00:07, +) Div2 A답지 않은 구현 문제이다. 구현이 어렵진 않기 때문에 문제에서 하라는 것을 해주면 된다. B. Charmed by the Game (00:20, +) $|a-b|/2$의 값을 이용해 잘 탐색해주면 된다. 나는 머리가 안돌아가서 무지성으로 구현했다.. C. Deep Down Below (00:32,+) 각 동굴마다 $A_i-i$의 최대값을 저장해 준 후, 이를 기준으로 정렬한 후 파라메트릭 서치를 진행하면 된다. 이분탐색을 하지 않고도 답을 구할 수 있다 한다. D1. Up the Strip (01:06, +2) $floor(N/i)$의 값이 $O(sqrt(N)$개라는 것을 이용하면 $O(Nsqrt(n))$에 문제를 ..

A. Creating a Character (00:06, +1) $max(0,min(exp+1,(str-int+exp+1)/2)$가 답이다. B. Zmei Gorynich (00:14, +) 가장 효율이 좋은 무기를 사용하다 가장 공격력이 높은 무기로 마무리하면 된다. C. The Number Of Good Substrings (00:39, +) 관찰을 해보면, leading zero의 개수에 따라 해당되는 수가 최대 2개임을 알 수 있다. 따라서, 연속되는 0의 개수를 체크하다 1을 만났을때 가능한 수를 모두 체크하면 $O(N)$에 문제를 해결할 수 있다.

A. Dial Up (00:18, +1) *442 제자리에서 계속 더하다 처음 다른 값이 나오면 가장 가까운 곳으로 이동하고, 이후에는 나오는 값에 따라 1이나 2를 더해주면 된다. 불가능한 경우 처리는 쉬우니 생략하도록 하겠다. B. Squares (00:54, +) *1273 $1$부터 $sqrt(N)$까지는 모든 경우가 되므로 다 더해준다. 그러면 각 $x$당 가능한 $y$의 개수가 $O(sqrt(N))$개가 된다. 따라서 각 경우에 대해 구간의 길이를 곱해 더해주면 된다. C. LIS to Original Sequence (01:42, +4) *1896 다음과 같은 과정을 따른다. LIS의 원소를 $A_1..A_k$라 했을때 (1) \(i

A~B는 따로 적지 않겠다. C. One More aab aba baa (00:05, +) *178 next_permutation() 함수를 이용하면 쉽게 구현할 수 있다. D. Coprime 2 (00:37, +3) *736 에라토스테네스의 체의 메커니즘을 이용한다. 모든 $A_i$에 대해 소인수를 구해준 후, 구한 소인수들로 에라토스테네스의 체 배열을 채워주면 된다. $O(Nsqrt(N)$에 문제를 해결할 수 있다. E. Chain Contestant (00:84, +1) *1413 비트마스크 DP이다. $DP[i][j][k]$를 $i$번째까지의 원소를 이용해 집합 $j$에 해당하는 색을 사용해 끝 색을 $k$로 하는 경우의 수로 정의하면 DP 갱신을 \(O(10 2^{10})\..

A. 2048 Game (00:03, +) 2048 이하인 수들을 모두 더했을 때 2048 이상이면 가능하다. B. Knights (00:05, +) 체크무늬로 칠한 배열을 출력하면 나이트가 갈 수 있는 칸의 색이 항상 달라지므로 최적이다. C. Perfect Team (00:18, +) $min(c,m,(c+m+x)/3$이 정답이다. D. Make The Fence Great Again (01:23, +3) 한 울타리에 대해 최대 2번까지만 높여주는 것이 최적임을 알 수 있다. 따라서 $DP[i][j]$를 $i$번째 펜스를 $j$만큼 올려줬을 때의 최소 비용으로 정의하면 $O(N)$에 문제를 해결할 수 있다.