(대충 누군가의 블로그)

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

셋 티어리스트 정리 !!제가 돈 셋만 정리함 ㅅㄱSSIOI 2025 day 1, JOISC 2025, BOI 2025, CEOI 2025 day 2SIOI 2025 day 2, CTS 2024 day 1ACEOI 2025 day 1, KOI 2025, CTS 2024 day 2B CCCO 2025 day 2, Balkan OI 2023 day 1DDDDDOOOONGNordic OI 2025

정해 : 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다.다상위 국밥을 어떻게 그렇게 잘 내는지 모르겠다. 재밌는 국밥을 원..

음 망했나? 작년에는 근데 더 망한 관계로 비교적 잘 본거로 퉁치자. 끝나고 SCSC가 있는 관계로 5/17 하루 내내 서울대에 있었는데 개인적인 생각으로는 둘 다 적당히 상타치인 것 같아 기부니가 좋다. 일단 KMO가 먼저였다. 7시+-정도에 집을 나서서 7호선 타고 갔다.9시 반까지 입실인데, 8시 반에 도착한 관계로 서울대 입구에 있는 편의점에서 급하게 삼김을 먹고 달렸다. 다행히도 빨리 도착할 수 있었고, 지인 NMK명을 만났다. 뽀구미라는 분을 만나고 싶었는데 그분이 지각한 관계로 못 봤다 ㅋㅋ지금 후회하고 있는건 타임라인좀 적을걸 여기에 답이 나오는데, 그거 다 뇌피셜이다.좀 찍은건 더더욱. 1번작년 1번은 X쉬웠는데 그거만큼 쉽진 않아서 놀랐다. 그림을 그렸는데, 어 이거 값이 나오나?하고 ..

문제 요약크기가 $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 ..

BOJ 기준 11617, 21936, 16243, 18081 4문제를 5시간정도 잡고 돌았습니다. 세팅은 제가 한 건 아니고 어딘가에서 긁어왔습니다. 타임라인(00:00~) 시작일단 전체적으로 문제를 다 읽었습니다.A는 적당히 정점을 추가하면서 스투라하는 문제처럼 보였고B는 간단한 DP같았습니다.C는 전에 제가 봤던 문제더라고요 근데 풀이는 모르고 티어는 알아서 일단 읽고 (R5) 그냥 버렸습니다.D는 흠... 그리디인가? joisc 2025 exhibition 느낌이 나는데 자구 그리디인 것 같았습니다. 일단 제일 쉬워보이는 B를 잡았습니다. B (00:51)DP[i][j] : 1~i까지 결정했고, 지금 i번째 문자부터 연속된 j개 문자가 S의 prefix j개와 일치할 때, i, i+1 .. N..

그리디 관련 글들을 돌아다니다 보면, 기초적인 골드 그리디 등과 관련된 글은 많지만 다이아 이상의 고난이도 그리디 문제들에 대한 글은 없는 것 같아 적게 되었다. 사실 내가 그리디를 잘 못해서 글을 찾아보려 했는데 없어서 좀 억울했다. 위에 적혀있듯이, 이 글은 골플 난이도의 그리디는 대체로 숙지한 상태의 독자들을 위한 글이다. 그리디 하아 이거참그리디라 흠... 뭔가 쉬운 그리디는 직관적으로 보이기도 하지만, 어려운 그리디는 조건 하나 잡기도 어려운 편이다. 반례를 찾고, 이를 해결하기 위한 조건을 붙이다보면 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$는 딱히 다룰 주..