onjo0127의 블로그

0. 동기 평소에 내가 즐겨 보는 트위치 방송이 하나 있다. 슈퍼 마리오 메이커 2라는 게임의 '어디까지 마리오 챌린지' 매우 어려움 난이도를 주로 플레이하는 방송인데, 이게 뭔지 간략하게 설명하자면 전 세계 유저들이 만든 마리오 코스들 중에서 난이도가 가장 어려운 코스들이 무작위로 주어지면 한정된 목숨 내에서 그 코스를 클리어해야하는 컨텐츠다. 코스를 잘 클리어하면 목숨을 더 얻을 수도 있고, 여러 번 죽으면 많은 목숨을 잃을 수도 있다. 목숨이 0이 되면 게임 오버이고, 게임 오버가 되지 않는 한 무한정 코스들을 클리어하는 모드가 '어디까지 마리오 챌린지'이다. 아무튼 이 방송을 하시는 분이 1위와 점점 가까워지고 있는 상황이라 방송에서 1위랑 차이가 얼마나 나는지, 언제쯤 세계 1위가 될 수 있는지..

들어가며 SMAWK 알고리즘은 $n \times m$ 크기의 totally monotone한 행렬에서 모든 행마다 최솟값의 위치를 $O(n+m)$ 시간에 구하는 알고리즘이다. 이 글에서는 SMAWK 알고리즘에 대해 소개하고, 이를 통해 해결할 수 있는 문제들에 대해 소개한다. 단조성. $2 \times 2$ 행렬 $\left[ {\begin{array}{ccc}a & b \ c & d \ \end{array}} \right]$ 은 다음 조건이 성립하면 monotone하다고 한다. $c < d$이면 $a n$일 때 수행된다. 먼저 REDUCE가 어떻게 수행되는지 살펴보자. Reduce REDUCE에서는 행렬의 단조성을 이용하여 고려할 필요가 없는 열들을 최소 $m-n$개 이상 삭제하는 것이 목표이다. 이를..

BOJ 11744 Jump 정답 스트링 $S$를 찾기 위해서는, 일단 $Jump(Q) = n/2$인 상황을 어떻게든 만들어야 한다. $S$에서 $0$의 개수를 $a$라고 하고, $1$의 개수를 $b$라고 하면 $a+b=n$이기 때문에 $min(a, b) \le n/2 \le max(a, b)$가 성립한다. 즉, $Q=00...00, Q=10...00, Q=11...00, \cdots, Q=11...10, Q=11...11$을 모두 질문하면, $Jump(Q) = n/2$인 경우를 무조건 얻을 수 있다. 즉 $N+1$번의 질문으로 $Jump(Q_m) = n/2$를 만족하는 String $Q_m$을 찾을 수 있다. 이제 $Q_m$을 조금씩 만지면서 $Jump$값의 변화를 살피면 $S$를 알아낼 수 있을 것이다..

블로그를 너무 방치해 둔 거 같아서 최근 풀었던 문제를 모아서 올려보기로 했다. BOJ 17474 수열과 쿼리 26 Segment Tree Beats 구현하면 된다. BOJ 1763 트리 색칠 이런 유형의 문제는 Best Vertex를 고른 다음, 그 부모와 합쳐주는 방식으로 해결하는 것이 전형적이다. 그 정점을 다음에 갈 수 있다면, 무조건 그 정점으로 가는 것이 이득이기 때문에 아예 부모 정점과 합치는 것이다. 이 문제도 마찬가지로 풀릴 것 같으니, 몇 가지 변수를 추가해서 해결해 보자. $X[i]$를 그 정점을 방문하고 나서 흐르는 시간의 양이라고 하고, $B[i]$를 그 정점을 방문하고 나서 얻는 추가적인 Cost라고 두자. Exchange Argument를 사용하면 $C[i] / X[i]$가 가..

내가 치르게 되는 마지막 APIO는 코로나19의 영향으로 인해 집에서 치르게 되었다. 이틀 동안 대회를 열어 두고, 각 나라의 참가자들이 자신이 원하는 시간에 참가 버튼을 누르면 5시간 타이머가 켜지고 5시간 동안 3문제를 푸는 대회를 치르는 timeframe 방식으로 진행되었다. 대회가 끝나도 각 문제에 대한 답안 제출 시각을 확인할 수 있어서, 이걸 보면서 타임라인별로 내 생각과 문제에 대한 내용을 정리해보려고 한다. 문제는 여기서 확인할 수 있다. A. 벽 칠하기 B. 자매 도시 C. 즐거운 행로 ~43:55 대회를 시작하기 전에, 나는 다음과 같은 전략들을 세우고 지키려고 노력했다. 대회가 시작하면 모든 문제를 정독하기 구현 시간을 제외했을 때, 모든 문제를 1시간 이상 고민하기 부분점수라도 빨리..

A. Incremental House of Pancakes 대소 관계가 한 번 바뀐 후에는 양쪽에서 번갈아가며 가져가면 된다는 사실을 관찰하고 나면, 대소 관계가 언제 처음 바뀌는지, 언제 끝나는지를 각각 이분탐색해서 문제를 해결할 수 있다. 급하게 짜느라 식이 꼬여서 자꾸 Off by one 에러가 생겼다. 결국 45분이 되어서야 첫 제출을 했고, 틀렸다. 두 번의 제출을 더 한 끝에 56분쯤에 AC를 받을 수 있었다. A에서 1시간이나 사용했기 때문에 여기서 멘탈이 좀 나갔다. 이런 유형의 문제에서 자꾸 말리는 경향이 있는데, 빨리 풀지는 못해도 AC는 한 번에 받을 수 있게 노력해야겠다. B. Security Update Hidden까지 풀려면 케이스 노가다를 많이 해야 할 것 같아서 Visible..

https://codeforces.com/contest/1284 A. New Year and Naming 한국인이라서 문제 안 읽고 예제만 본 다음에 풀었다. ㅋㅋㅋ $A_{(y-1) \mod n} + B_{(y-1) \mod m}$을 출력하면 된다. B. New Year and Ascent Sequence Ascent가 없는 수열들을 개수를 세면 더 쉽다. 수열 자체에 Ascent가 있는 수열은 걸러내고, Ascent가 없다면 그 수열은 최댓값과 최솟값만 중요하다는 것을 알 수 있다. $\min s_i \geq \max s_j$인 (i, j) 쌍의 수를 세면 되는데, 이는 부분합 배열을 사용하면 해결할 수 있다. C. New Year and Permutation [l, l+c]를 수의 범위로 가지는 f..

JOI 2016 오렌지 출하 $D_i =$ (1~i번째 오렌지까지 어떻게 상자에 넣을지 배정했을 때 최솟값)이라고 정의하면, $O(NM)$ DP로 해결할 수 있다. 스탬프 수집 일단 JOI를 모을 수 있는 경우의 수를 구하는 방법을 생각해 보자. $J_i =$ (1~i번째 가게 중 J 스탬프를 주는 가게 수)로 정의하고, $I_i =$ (i~N번째 가게 중 I 스탬프를 주는 가게 수)로 정의하자. 그러면 경우의 수는 $S_i =$ 'O'를 만족하는 i들에 대해 $J_i*I_i$를 모두 더한 것이 된다. 가게를 추가할 때 스탬프 J를 주는 가게를 추가한다면, 입구에 설치하는 게 이득이고, 스탬프 I를 주는 가게를 추가한다면 출구에 설치하는 게 이득이다. 스탬프 O를 주는 가게를 추가한다면 $J_i*I_i$..

AGC006 A - Prefix and Suffix $O(N^2)$으로 일일이 비교해주고 |S| + |T| - (가장 길게 겹치는 길이)가 답이 된다. B - Median Pyramid Easy 어느 시점에 같은 수가 연속으로 있게 되면 그 두 수는 피라미드 끝까지 그 위치에 그대로 남아있게 됨을 관찰할 수 있다. 이걸 이용해서 (..., x-1, x, x+1 x-2, ...) 혹은 (..., x+1, x, x-1, x+2) 등의 형태를 만들어주면 피라미드의 윗줄에 x가 두 번 연속으로 존재하게 된다. C - Rabbit Exercise $x_i$에 위치한 토끼가 점프를 하면 이 토끼는 $2x_{i-1} - x_i$ 혹은 $2x_{i+1} - x_i$으로 이동하게 된다. 엄밀히 증명하진 않았지만 식의 선..

돈 셋 : IOI 2018 Day 2 ~10분 일단 모든 문제를 읽고, doll을 잡기로 결정했다. 84분 : doll 0점 doll을 계속 고민해봐도, 서브태스크 1, 2를 제외하고는 아무런 생각이 나지 않았다. 서브태스크 2의 구현마저도 엄청 복잡할 것 같았다. 그러다가 M=1인 서브태스크를 풀면 전체적인 감이 오지 않을까 하는 생각에 그걸 계속 고민했다. 스위치를 일렬로 늘어서게 하고 Y 방향을 트리거 쪽으로 오게 하는지 여부로 이진법 표현이 가능할 것 같았다. 그와 비슷한 형태를 계속 고민하다 예제가 나와서 제출했는데 0점을 받았다. 91분 : doll 2점 1시간 이상 고민했는데 소득이 없어서 일단 뭐라도 짜기로 했다. 서브태스크 1을 해결하고 2점을 받았다. 138분 : doll 20점 다시 ..