대회 문제들은 여기서 확인하실 수 있습니다. 문제별로 제가 기여한 것들과 짧은 후기를 정리해보겠습니다. 전체적인 제안 검수를 딱 하려고 보니까 문제별로 tests가 150개를 넘어가던 걸로 기억합니다. 가뜩이나 Arena가 적용되어서 참가자 수가 많아질 것 같은데 tests가 이대로 많으면 안 될 것 같다고 줄여달라고 제안을 드렸습니다. 좀 늦게 제안했는데, 왜 그 전까지는 아무도 말을 안 꺼냈는지는 잘 모르겠네요.. 😅 또, 그래프 문제들의 조건에서 "$1\le i , j\le N$인 모든 $i$, $j$에 대해서 $i$번 구역에서 $j$번 구역으로 가능 경로가 항상 존재"를 " $1 \le i < j \le N$인 모든 $i$, $j$에 대해서 $i$번 구역과 $j$번 구역을 연결하는 경로가 존재"로..

문제 링크 문제 요약 prefix와 suffix를 잡는데, prefix length + suffix length s) return true; Mp = max(Mp,p[i]); } return false; } int main() ..

강릉에 왔다! 그냥 그렇다.. Baseball Watching 어려웠다 ㅠㅠ 회차가 $9$회 이내로 제한되고, 선택의 경우가 $3$가지라는 작은 제한을 잘 이용해야 될 것 같았다. 회차마다 $3$가지 선택을 하는걸 다르게 생각하면 $N$명을 $3$개의 집합으로 분할한 거고, 결국 $9$회 걸친 합집합의 최대 크기 및 최소 크기를 구하는 문제로 바뀐다고 생각했다. 그렇게 생각해보니 $3^9\times N$에 어느 정도의 상수가 붙은 풀이가 바로 나올 수 있었는데, 간소한 차이로 못 풀 것처럼 보였다. 다른 관찰이 그다지 보이지 않아서 이걸 조금만 최적화시켜도 풀리지 않을까 생각했다. 근데 집합을 bitset으로 관리하면 or 연산이 $N/32$~$N/64$에 된다는 얘기를 들어서 내 경우에 적용해보니 함수..

좋다. 여우 신탁 오랫동안 고민한 뒤에야 맞췄다. 다양한 관찰과 접근을 시도했지만 전부 애매했다. sparse table을 이용하고 싶다는 생각도 했는데, 매번 함수가 다르기 때문에 무용지물이었다. 거꾸로 마지막 나머지들로부터 추적을 해볼까 하는 생각도 했는데, 크게 달라지는 점은 없었다. 기댓값의 선형성을 적극적으로 이용할 수 있는가도 고민해봤는데, 티어 상 그럴 것 같지도 않았고 써먹기 좋은 상황이 없었다. 사실 초반에 제수가 감소한다는 관찰을 했었는데, 이를 다시 생각해보니 쓸 만했다. 뭔가 로그 시간으로의 단축을 원했던지라 효과가 없다고 넘겼었는데, 분할 상환적으로 봤을 때 효과적이었다. 결국 풀이는 제수가 감소하는 만큼만 새 나머지로 이동시켜주면 되는 것이었다. 그러면 시간 복잡도가 분할 상환적..

교수님은 기다리지 않는다 문제 링크 쉽다. DSU를 잘 변형해서 풀면 된다. 'JOI 국가의 행사'를 풀어본게 도움이 된 것 같다. 더보기 #include using namespace std; using ii = pair; using ll = long long; #define rep(i,a,b) for (auto i = (a); i size(b)) swap(a,b), w = -w; // b에다가 a 붙여버리고 a의 값들 전부 apply for (int x : sub[a]) val[x] += w, sub[b].push_back(x); sub[a].clear(); par[a] = b; return true; } bool same(int a, int b) { return find(a) == find(b); }..

문제 링크 질문은 언제나 환영입니다. 이 문제는 두 가지 풀이법이 존재합니다. 우선 대표적인 관찰을 확인하고 각 풀이로 전개해 보겠습니다. 편의상 주어진 배열은 $A$라고 합시다. 관찰. max와 단조성 min의 단조성 배열의 임의의 위치 $k$에 대해 $\max A[i\cdots k]$는 $i$에 대해 단조 감소를 띱니다. 왜냐하면 $i_1

카카오 코딩 테스트 풀이를 작성했다. 마지막 문제 빼고는 전반적으로 내가 들었던 예전 카카오 난이도보다 낮은 것 같았다. 마지막 문제는 그래도 골드 상위는 될 것 같았다. 아니면 플래 하위까지도 가능할지도 모르겠다. 암튼... 작성하기 귀찮다. 골드 6문제 세트를 200분으로 잡고 돌았다. 35분 남기고 전부 풀어서 다행이다. 사실 점점 시간이 늦어져서 마지막 두 문제는 졸면서 푼 것 같다. 벽 부수고 이동하기 단순히 BFS 두 번 돌리고 고려하면 된다. 17분 정도 걸렸다. 더보기 #include using namespace std; using ii = pair; using ll = long long; #define rep(i,a,b) for (auto i = (a); i x or x > n or 1 ..

대회 알림이 6개나 올라와 있길래 할 만한 게 뭐가 있을지 찾아보다가 SNUPC OC Div.2 작년 결과를 보니 대회 우승/준우승 컷이 꽤 낮아서 우승/준우승을 목표로 잡고 참가했다. 대회가 끝났는데 아직 프리즈 이후 상황이 안 나와서 2등 아니면 3등인데 높은 확률로 3등이다. 아쉬운 점은 대회에 늦게 들어온 것과 C 코드를 다 짜고 실수 몇 개 고치다가 노트북 배터리가 부족해서 카페에서 집까지 뛰어서 충전기를 가져오느라 제출이 늦어진 점이다. 또, E에서 해서는 안되는 실수를 했던 점이 아쉽다. 양방향이여서 SPFA가 아니라 dfs 한 번으로 체크하고서 다익스트라를 돌리면 되는 거였는데 착각하고 인터넷에 있는 SPFA 코드를 찾아다가 넣고서 두 번이나 틀렸다. 대회 링크 질문은 언제나 환영입니다. ..