(대충 누군가의 블로그)

IGM을 달성했다. IGM을 달성하면 후기를 쓰는 게 일종의 관례인 것 같아 글을 쓴다.$($딱 여기까지 작성하고 진전이 없어서, 다른 후기글 NMK개를 흡수해 돚거해서 쓰기로 했다$)$ 소감일단 IGM을 달성해서 매우 기쁘다. 사실 별로 딱히 그렇게까진 기쁘지 않은 것 같다. 사유는 최근 정올 여름학교 모의고사 성적에 있는 것 같다. GM을 달성했을 때는 정말 기뻣는데, 그때 내가 별로 GM치고 잘하지 않는다는 사실을 깨달은 것 같다. How to Study?딱히 나만의 공부법?은 없는 것 같다. 이것도 모 블로그를 돚거해서 비슷하게 작성하기로 했다. 1. Virtual Contest로 많은 대회를 풀어보기코드포스 레이팅을 올리는 가장 효과적인 방법은 최대한 많은 코드포스 대회에 참가하는 것입니다. 코..

정해 : Lemma1 : 다음과 같은 방법으로 모든 경우를 만들 수 있음. $i = 1, 2, 3 \dots N$을 차례대로 순회하며, $P_i$를 앞으로 원하는 만큼 땡기기를 반복. $($즉, 맨 앞 친구 땡기고, 그다음친구 땡기고 .... 맨 마지막친구 땡기고$)$이를 이용하면 앞에서 뒤로 $1 \dots i$번 위치의 사람들을 처리했을 때, j명이 보이는 상태고, 지금 앞 $i$명의 사람들 배치가 state와 같을 때 최소 스왑 횟수. $($state는 $i!$ 가지 존재$)$와 같은 DP를 정의하면 $O(N! \times N^a)$ 꼴의 풀이가 가능합니다. 이때, state의 수를 줄입니다.Lemma 2. $i P_j$ 인데 최종 상태에서 $P_j$는 보이는데 $P_i$는 안보이게 되는 최적해..

정리하려고 만들었다. 매우 개인적인 생각이다. KOI갓문제가 꽤 있다. 근데 좀 그저 그런 문제도 꽤 있다. 전 세계적으로 봤을 때 상타치라고 생각한다.뭐 한국인으로 태어난 이상 안 풀어볼 수 없는 기출이니 딱히 평가하진 않겠다. IOI생략한다. 이후에 나오는 goat라는건 "IOI에 견줄 정도" 라는 뜻이다. IOI는 모든 분야 goat이다. JOIgoat of goat라고 생각한다. OI를 준비하는데 JOI를 안 푼다는 것은 말이 안 된다고 생각한다.예선 문제는 잘 모르겠고 Final, JOI open contest, JOISC은 퀄리티가 매우 좋다. 특징으로는 국밥과 애드혹을 매우 잘 내는 것 같다. 특히 국밥은 JOI가 goat다.다상위 국밥을 어떻게 그렇게 잘 내는지 모르겠다. 재밌는 국밥을 원..

문제 요약크기가 $n$인 트리 $T$가 주어진다. 모든 노드가 "부모 노드의 번호가 자신보다 작다"는 성질을 만족한다. 이제 $n+m$개의 노드를 가진 트리 $T^{\prime}$이 몇 개나 있는지를 구하려 한다. 이때 $T^{\prime}$은 다음 두 가지 조건을 만족해야 한다. 임의의 $1 \leq i, j \leq n$에 대해, $LCA(i, j)$는 $T$와 $T^{\prime}$에서 동일하다.임의의 $1 \leq i, j \leq n+m$에 대해, $T^{\prime}$에서 $LCA(i, j) \leq max(i, j) + k$이다. 풀이$T^{\prime}$에서 ${1, 2, 3 \dots n}$의 위치관계는 기존 $T$와 같아야 함을 알 수 있다. 즉, 기존 $T$에서 사이사이에 적당히 노드..

라고 쓰고 NOI 문제 정리라고 읽는다 세상에는 많은 올림피아드가 있고, 그 중 많은 올림피아드가 백준에 있고, JOI / BOI 등 goat로 평가받아 많이 사랑받는 올림피아드들이 있는 반면 NOI $($China$)$와 같이 버림받은 올림피아드도 존재합니다. $NMK$개의 올피셋을 돌다가 최근 NOI 문제들이 모두 언레인 것을 보고, 한번 NOI를 부흥시켜볼까?라는 생각이 들어 NOI를 밀어보려 합니다. 중국어 공부도 좀 하려고 합니다.문제 제목은 간zi나게 중국어로 적을 생각입니다. Day 1Day 2 1231232024 方格染色 桂花树 深搜 贸易 字符串 合并书本 2023 2022 2021 2020 2019 2018 2017 ..

그리디 관련 글들을 돌아다니다 보면, 기초적인 골드 그리디 등과 관련된 글은 많지만 다이아 이상의 고난이도 그리디 문제들에 대한 글은 없는 것 같아 적게 되었다. 사실 내가 그리디를 잘 못해서 글을 찾아보려 했는데 없어서 좀 억울했다. 위에 적혀있듯이, 이 글은 골플 난이도의 그리디는 대체로 숙지한 상태의 독자들을 위한 글이다. 그리디 하아 이거참그리디라 흠... 뭔가 쉬운 그리디는 직관적으로 보이기도 하지만, 어려운 그리디는 조건 하나 잡기도 어려운 편이다. 반례를 찾고, 이를 해결하기 위한 조건을 붙이다보면 if문만 수두룩한 짬뽕 코드를 볼 수 있을 것이다. 내 얘기다. 해설을 막상 보게되면 깔끔한 조건이 있긴 하지만, 솔직히 저걸 인간적으로 유도할 수 있나? 라는 생각이 들기도 한다. 나 또한 이..

일반적으로, 어떤 함수가 볼록하다는 것은 $f{ \prime \prime } > 0$ 등이 성립함을 말한다.이산적으로는, $f(i+2)-f(i+1) \geq f(i+1)-f(i)$와 같이 생각할 수 있다. 이를 PS에서는 어떻게 논할 수 있을까?가 이 글의 주제이다. 이 글에서는 오목과 볼록을 구분하지 않습니다. 뭐 뒤집으면 둘이 같다 :bloblul: MCMFMCMF를 할 때, $f(i)$를 augmenting path를 찾아서 1만큼 흘리는 것을 $i$번 했을 때, 그 $i$번째에 흘린 비용이라 하자. 이때, $f(i)$가 볼록함을 증명할 수 있다. 즉, $f(i+1)-f(i) \leq f(i+2)-f(i+1)$가 성립한다. 이를 어떻게 이용할까? $OI$러의 입장으로써는 $MCMF$는 딱히 다룰 주..

일단 이 글은 생성함수함(이하 젠펑), 기댓값 등에 대한 기초 이해를 필요로 합니다.1. 더블카운팅과 기댓값의 선형성사실 둘은 같은 말인데, 기댓값의 선형성에서 전체 경우의 수를 곱하면 더블카운팅이 된다. 25441 디지털 회로문제를 요약하긴 귀찮으니 문제 요약은 하지 않도록(? 하겠다. 사실 식을 정리하면서 얻은 관찰 등이 있지만, 이를 생략하고 가자면결론은 이 문제는 기댓값으로 접근하면 쉽다는 것이다. 당연히 다음과 같은 DP 느낌으로 접근한다.- $DP[i]$ : $i$번째 노드가 1이 되는 경우의 수 이렇게 되면, $DP[i]$는$($자식 중 1개 이상이 1이 되는 경우의 수$) + ($ 2개 이상이 1이 되는 경우의 수$) \dots$가 된다. 이를 다시 정리하면,$ 1 \times ( $ 자식..

교내 동아리 입부시험을 위해 문제 출제를 하게 되어, PS문제를 2개정도 만들게 되었습니다.개인적으로 묻히기에는 꽤 좋은 문제라고 생각해 여기에 후기를 올립니다. 문제에 앞서 ...저희 동아리는 PS동아리가 아닌 관계로 정보 문제를 직접적으로 낼 순 없어서 변형을 좀 가했습니다 ㅋㅋ;;문제 스토리?등도 있지만 설명하면 너무 길어지는 관계로 간단한 요약 설명합니다. 문제 1. 구울$4N$개의 수가 원형으로 배치되어 있습니다. 각 수는 $-1, 0, +1$중 하나이며, $+1$이 정확히 $3N$개 있습니다. 최종 목표는 모든 $+1$의 위치를 찾아내야 합니다. 이를 위해 $3N-1$번의 쿼리를 이용할 수 있습니다. 하나의 쿼리는, 원 위에서 인접한 수들을 골라 그 합을 반환받을 수 있습니다. 풀이더보기먼저 ..

재밌게 푼 문제라 풀이를 적어봅니다. 풀이만 있는게 아니라 잡설도 좀 있을예정 .. 문제 요약 .. ? 은 귀찮으니 안하겠습니다 ㅋㅋ;;    제일 중요한 핵심은 이거라고 생각했습니다.어떤 정점에 대해, 서브트리중 제일 깊은 서브트리를 제외하면 나머지 서브트리에서는 Unique City가 나올 수 없다모든 방향의 Unique City를 계산하면 TLE가 나므로, 깊은 곳을 제외하면 탐색을 최대한 하지 않게 하는게 풀이의 핵심이라고 생각할 수 있습니다. 그래서 지름을 생각했습니다.  저 빨간 친구가 Unique City가 되는 정점들은, 저 빨간 정점의 서브트리 내부 외에는 존재할 수 없습니다. 그래서 서브트리 내부만 잘 계산해주는 느낌이라고 생각했는데,지름 위의 정점은 잘 처리해주기가 힘들었습니다. 저걸..