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 같다. 대충 셋으로 짝꿍 인덱스를 찾았는데, 벡터로 해도 된다. (플래 스트릭을 아껴야 하므로.. oj.uz에 채점해두고 BOJ에 스트릭 안 채운 날 하나씩 까먹을 예정) #include "shoes.h"#include using namespace std; using ll = long long;const int..

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..

요즘 여러모로 의욕이 없다.플래티넘 스트릭 채우는 것 외에는 PS 꾸준히 하지도 않는다. 자꾸 코드포스 칠 때 졸리다.시작하기 전에 눈 비비면서 커피를 마셔도 졸음이 안 사라진다.졸려도 할 건 해야지 하면서 하긴 하는데.. 확실히 이상한 실수가 많고 발상력이 떨어진다.낮 시간 때에 버츄얼 돌릴 때에는 퍼포먼스 2000 이상이 꾸준하게 나오는데, 11시반 코포만 치면 오락가락이다. 보통 온사이트 대회에 가면 나랑 비슷한 등수대에 오렌지가 많다.코드포스는 관찰력이 중요하고 머리가 좋아야 하는데, 나는 머리가 나쁜 것 같다.영어 못하는 것도 한 몫 하는 것 같다.그냥 백준을 많이 풀어서 짬바로 버티는 타입인 것 같다. 버추얼 자주 돌리며 빡세게 연습하고 싶은데 맨날 잠만 잔다. 최근에 다른 분 블로그 보면서 ..