BOI 2016 Swap순열 $x_1, \cdots, x_n$ 이 주어질 때, $i = 2, \cdots, n$ 에 대해 (순서대로) $x _ {[i/2]}$와 $x _ i$ 를 스왑할 수 있는 기회가 한 번씩 주어진다. 이를 적절히 사용하여 만들 수 있는 사전 순 최소 순열을 구하여라.풀이$x_i$의 후보는 $x_i, x_{2i}, x_{2i+1}$ 셋 뿐이고, 사전 순 최소를 생각하면 이 중 최소인 값이 $i$번 자리에 들어가는 것이 당연하다.(자명한 경우) $i$번 자리에 $x_i$ 또는 $x_{2i}$가 들어가는 경우, $(2i, 2i+1)$번 자리가 각각 $(x_{2i}, x_{2i+1}), (x_{i}, x_{2i+1})$로 강제된다.(비자명한 경우) 하지만 $x_{2i+1}$이 들어가는 경우..

어제 끝난 제 3회 IDTCup의 후기이다. 무려 21명이 운영진이었고, 참가자는 20명에 불과한 대회였지만 그래도 준비 과정을 적어본다. 부족한 운영 능력에도 불구하고 열심히 검수/참가해주신 분들에게 감사를 표한다. Special thanks to jhhope1. 넋두리 대회에 대한 구상이 구체적으로 나온 건 12월 전후인 것 같다. 이때는 그래도 ICPC를 다시 나가고 싶다는 생각이 있었고. 올해 휴학을 할지 말지 정해진 부분이 없었기 때문에 PS에 대한 관심이 별로 식지 않았던 때였다. 그 사이에 이렇게 급격하게 PS에 무관심해질 줄은 몰랐다. 그래서인지 막판에는 즐겁다기보단 일로 느껴져서 부담되는 부분도 있었다. 출제자들 모두 PS에 대한 관심이 떨어진 상태라, 좋은 대회를 만들자기보다는 그냥 내..

글 쓰는 법을 까먹을 것 같으니, 몇 개 되지 않는 문제들을 줏어담아보자. BOJ 20556. 둥둥섬 다리 재정비하기 20556번: 둥둥섬 다리 재정비하기 첫 줄에 섬의 수 $N$과 쿼리의 수 $Q$가 주어진다. $(1 \leq N,Q \leq 300\,000)$ 이후 $N-1$개의 줄에 걸쳐 다리들이 연결하는 두 섬 $u$와 $v$가 공백으로 구분되어 주어진다. $(1 \leq u,v \leq N)$ 이후 $Q$개의 줄 www.acmicpc.net 루트가 \(r\)로 고정되어 있다고 할 때, \(a\)개의 다리를 재정비해서 얻을 수 있는 최적의 결과는 가장 큰 \(a\)개 서브트리의 크기 합이라는 사실을 간단하게 알 수 있다. 따라서 "가장 큰 \(k\)개의 합"이 지원되는 자료구조에 서브트리들의 크기..

ICPC를 마무리하면서 2020의 PS 일정은 사실상 마무리되었다. 11/12 solve 3등으로 전체 대회를 마무리했다. 굉장히 좋은 성적을 거뒀지만, 제 역할을 못한 것 같아서 많이 아쉽다. 기대한 것도 있었고... 대회 준비 팀 구성은 작년과 같이 imeimi / jhhope1 / TAMREF로 구성된 3인팀이었다. 사실 예선 때까지만 해도 거의 기대를 하지 않았다. 학기 일정을 소화하기에도 많이 벅찼고 PS를 거의 손도 대지 않았다. 그런데 솔직히 팀원이 imeimi인데ㅋㅋㅋㅋ 월파 욕심이 안 나기 어렵다. 폼이 많이 떨어진 상태에서 예선을 봤는데 생각보다 가능성이 보여서(??) jhhope1이 실력을 좀 키우자는 이야기를 했다. 결국 내가 아는 문제들을 즈홒한테 던져주고, 즈홒은 풀이를 짜고, ..

고3 때를 포함해서 3번째 UCPC. ICPC멤버 그대로 (imeimi2000, jhhope1, TAMREF) 완전탐색 원툴 16등 도전합니다팀으로 참가했다. 최종 성적은 10 / 12 solve 5등으로, 역대 UCPC 중에서는 제일 좋은 성적이 나왔다. 팀연습이라고는 UCPC 예선밖에 없었는데 결과는 별로 나쁘지 않았다 ㅋㅋ 기억나는대로 타임라인을 재구성해본다. 약한 스포일러가 있으니 주의. 초반 (0~1시간) 내가 앞, 이멘이 중간, 즈홒이 뒤를 맡았다. A에 후원사 로고가 붙어있는 걸 발견했지만 뭔가 "제일 쉬운 문제"로 불릴 정도는 아닌 것 같아서 B랑 C를 보고 있었다. 한창 복잡한 지문을 읽고 있는데 스코어보드에 초록색 A들이 쫙 깔리기 시작했다. 정신 차리고 보니 쉬운 문제더라. 트리에서 ..

https://www.acmicpc.net/problem/10129 10129번: 작은 새 문제 경기과학고의 뒤뜰에는 일렬로 된 n개의 나무로 이루어진 숲이 있다. 그 중 첫 번째 나무 위에는 마지막 나무의 위로 올라가고 싶어하는 작은 새가 한 마리 있다. 그 새는 몸집이 매우 작기 때문에 한 번의 비행으로 날아갈 수 있는 거리에 한계가 있다. 만약 새가 i번째 나무 위에 있다면, 이 새는 한 번의 비행으로 i+1, i+2, …, i+k번째 나무 중 하나로 갈 수 있으며 그보다 멀리 떨어진 나무로는 가지 못한다. 또한, 작은 새에게 지금 있는 www.acmicpc.net 더보기 가장 먼저 드는 생각은 \(dp[i]\)를 "\(i\)번 나무에 도달하기 위해 느끼는 피로감의 횟수"로 정의하는 것이다. 점화식..