https://www.acmicpc.net/problem/21268솔루션에서 Tellegen's Principle을 인용하고 있어서 지난 포스트와 연관해 작성해본다. 머리 좋은 사람들은 아마 생각하지 않고도 풀 수 있을 것 같다.Without Tellegen's principleEk=∑i=1nCi∏j=1k(Ai+Bj)E_{k} = \sum_{i = 1}^{n} C_{i} \prod_{j = 1}^{k} (A_{i} + B_{j})Ek​=∑i=1n​Ci​∏j=1k​(Ai​+Bj​)를 답이라고 하자.iii와 관련한 항들을 사부작거리다보면, Pj=∑i=1nCiAijP_{j} = \sum_{i = 1}^{n} C_{i}A_{i}^{j}Pj​=∑i=1n​Ci​Aij​를 미리 계산해두면 편할 것 같다.∑jFk,jxj=(x+B1)(x+B2)⋯(x+Bk)\sum_{j} F_{k, j}x^{j} = (x+B_1)(x+B_2)\cdots (x+B_{k})∑j​Fk,j​xj=(x+B1​)(x+B2​)⋯(x+Bk​)라고 두면, $E_{k} = \sum_{j} P..

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

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

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

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들이 쫙 깔리기 시작했다. 정신 차리고 보니 쉬운 문제더라. 트리에서 ..