BOJ가 서비스 종료를 하게 되었다.solved.ac를 주축으로 OJ들을 연결하려는 움직임이 보이고, 난이도 기여 시스템은 남게 될 것 같다.BOJ에서만 풀 수 있던 쏠쏠한 문제들을 더 이상 채점할 수 없다는 사실이 안타깝다.전역하고 PS를 다시 빡세게 할 때가 되면, 전과 같은 좋은 인프라가 남아있었으면 좋겠다. IOI 2019 — Rectangles View problem - Rectangles (IOI19_rect) :: oj.uzView problem - Rectangles (IOI19_rect)oj.uz재밌는 문제다.더보기일단 좋은 직사각형의 개수가 sparse하다는 관찰을 할 수 있다.row - col을 독립적으로 다루고 싶다는 생각도 할 수 있다.$1\times N$에 대해서, 좋은 직사각형..

싸지방에서 코포 치다가 kmp를 만났다.사회에 있을 때도 많이 안 해봐서 서툴렀던 건데, 이 참에 제대로 기록해두려고 한다. kmp는 에디터를 켜서 주어진 문자열의 모든 prefix를 적고 그 안에서 ctrl + f를 하는 느낌이다. 문자열 "ababacabababc"를 상상해보자. 윗쪽은 이럴 것이다:빨간 부분이 윗쪽에서 ctrl + f 했을 때 선택될 수 있는 영역을 나타낸다. 빨간 부분을 쭉 사용하다가, "ababab"가 나오며 흐름이 끊긴걸 확인할 수 있다.하지만 여기서 재활용을 하는데, "abab"로 이어갈 수 있기 때문이다. 근데 "abab"를 써먹을 수 있음을 amortized O(1)에 어떻게 확인할텐가?"ababa"의 뒷부분의 빨간 영역을 새로 따라가서 연장 가능함을 확인하면 된다. 그래..

https://www.acmicpc.net/problem/34532 문제가 깔끔하다. 풀이도 깔끔하다. 술ㅍ마시고 푸니까 기분이 좋다.벌써 입대가 이번 달로 다가왔다. ㅅㅂ 일단 $N$은 반드시 전체 트리의 루트가 되어야 한다.그 다음에 $N$을 포함하는 모든 구간은 $N$이 부모 정점이 되도록 잇지 않을 이유가 없다. 따라서 구성하고 있는 트리에 연결을 완료한 정점에 대해, 그 정점을 포함하는 구간을 갖는 모든 정점을 다음 잇는 정점의 대상으로 본다. 세그먼트 트리에서 구간 업데이트 + 단일 쿼리에서 구간을 갖는 모든 노드에 벡터를 대응한 후 빼낼 때마다 벡터를 비워주면 구현할 수 있다. 플래2인듯? #include using namespace std; using ll = long long; using..

https://oj.uz/problem/view/IOI19_shoes ioi에 이상한 문제도 좀 있는 것 같다.이게 왜 플래1인지 전혀 모르겠다. 그냥 가까운 짝 찾아서 매칭하는 전략이 먹히는지 $O(n^2)$에 대충 해서 넣었더니 50점 나오는걸 확인하고 바로 펜윅으로 짜서 맞혔다.그냥 내가 사용하는 swap중에 안 써도 되는게 하나도 없고, 더 좋은 매칭도 없다는게 자명하다고 생각한다.플래 5 같다. 대충 셋으로 짝꿍 인덱스를 찾았는데, 벡터로 해도 된다. #include "shoes.h"#include using namespace std; using ll = long long;const int N = 1e5 + 3;set trunk[N+N];auto *pos = trunk+N;struct BIT {..

https://www.acmicpc.net/problem/25302 문제 컨셉이 심플하니 예쁘게 생겼길래 붙잡고서 친구랑 뻘소리 좀 주고 받으면서 20분 쳐다보니 떠올랐다.2년 전에 풀었던 APIO - 2021 밀림 점프(https://mathsciforstudent.tistory.com/376)의 하위 호환 문제였다.저 문제는 자력솔은 못했지만 정말 재밌게 풀었던 문제라 잊을래야 잊을 수 없다. 히스토그램에서 자기보다 높아지는 첫 인덱스와 간선을 연결하는 식으로 트리를 구성할 수 있다.이걸 카르테시안 트리라고 부르는 것 같던데, 뭔지 모르기 때문에 그냥 히스토그램 트리라고 하겠다. 히스토그램 트리에서 업데이트가 없고, 점프를 뛸 때마다 히스토그램에서 먹고 들어가는 각각의 부분 직사각형이 고정되므로.. ..

https://www.acmicpc.net/problem/10071 말리면 한없이 말린다. 42점은 간단하게, '더 이상 연결성이 보장되지 않는 시점에 잇는다'를 구현했고, 이걸 확장해서 100점을 만들려니 환장하겠더라.residual 그래프에 $K_{i,n-i}$꼴이 발생하면 연결한다 이딴걸 해볼까? 온라인으로 단절선을 관리할 수가 있나? 이게 플래 1인가? 엄청 말렸는데, 그냥 괜찮은 construction을 만드는게 문제의 방향이었다.떠올린 다음에.. 지나간 한 두 시간을 되새기며 '이게 맞나? 정말?'이라는 말을 하며 제출했는데 맞았다. 제너레이터를 이용해 랜덤한 트리를 만들어 본 경험을 떠올리면서 발상했던 것 같다.기이한 문제.. #include "game.h"#include using name..

https://www.acmicpc.net/problem/10846 고평가 된 것으로 느껴지는 문제. 상위비트부터 최적으로 맞춰주는게 이득이라는 발상은 꽤 흔하다. 상위비트부터 보면서 두 가지 서로 다른 문제에 대해, 서로 다른 DP를 짜주면 된다.나는 소신으로 플래 5에 기여했는데, 다이아 5 기여도 꽤 많아서 정말 놀랐다. #include using namespace std; using ll = long long; using ii = pair; using vi = vector;#define rep(i,a,b) for (ll i = (a); i = (a); --i)#define all(x) (x).begin(), (x).end()#define siz(x) ll((x).size())#define Mup(..

https://www.acmicpc.net/problem/20079 ioi임 + 인터랙티브임 요소 때문에 올려치기가 좀 있는 것 같다. 단순히 계산해보면 $v\leq 5$이다.가장 별로인 종류가 거의 대부분을 차지한다.가장 별로인 종류만 무시하면서 분할정복 느낌으로 탐색을 진행한다.(가장 별로인 종류가 아닌 다른 종류들) × (log n)에 해결된다. 뭔가 잘못짠 부분이라던가.. 좀 있어야 할 것 같은데 데이터가 약한건가 뭔가.. 대충 짰는데 그냥 잘 돌더니 100점을 받았다.뭔가 철학도 재미도 없는 문제인 것 같다. 내가 구현을 잘 해서 쉬웠던 걸 수도 있을 것 같다.탐색 구간이 들어오면, $m$을 잡고서, $m$이 가장 별로인 애가 아니면, 전부 답의 후보로 하나하나 확인해도 되므로 $m_1$ ~ $..

https://www.acmicpc.net/problem/25384 대단한 문제라고 생각한다. 일단 $O(N^3)$ 솔루션은 어렵지 않게 이끌어낼 수 있다.$D(i,j,k):=i-$정사각형에서 왼쪽 변이 $c_j\dots c_i$의 색을 포함하며 오른쪽 변이 $c_k\dots c_i$의 색을 포함하는 경우의 수. 점화식은 네 가지 전이를 갖는다. ($c_i\neq c_{i+1}$임은 전제한다.)$D(i,L,R) \leftarrow^+ D(i-1,L,R)$$D(i,R,i-1) \leftarrow^+ D(i-1,L,R)$ for $c_i \neq c_L \dots c_{i-1}$$D(i,i-1,L) \leftarrow^+ D(i-1,L,R)$ for $c_i \neq c_R \dots c_{i-1}$$D(i..