CCC 2017 S2. High Tide Low Tide 입력으로 들어온 수열을 정렬한 후, 만조때는 중앙값부터 감소하는 순서대로, 간조일때는 중앙값부터 증가하는 순서대로 출력합니다. $n = 2k + 1$ 이면: a[k+1] a[k+2] a[k] a[k+3] ... a[2] a[2k+1] a[1] $n = 2k$ 이면: a[k] a[k+1] a[k-1] a[k+2] ... a[1] a[2k] VKOShP 2017 A. Tourism 웬만하면 굉장히 큰 답을 찾을 수 있다는 게 핵심 포인트입니다. 만약 $S[1] = S[N]$ 이면 답은 $[1, N-1], [2, N]$ 입니다. 아니면, $S[1] = S[2] = \ldots = S[i]$ 가 만족하는 최대 $i$ 와 $S[N-j+1] = S[N-j+2..
대회 후기 일단 시작하고 나서 코딩하지 않고 이 글부터 썼다. 이 후 이 글을 따라서 코딩했는데 2번, 4번, 5번을 틀렸다. 2번은 큰 자릿수가 앞에 있다는 걸 몰랐다. 순서를 바꿔서 맞았다. 4번은 88점이 나오기에 풀이가 틀렸나 했다. 5번은 그냥 코딩 실수가 좀 있었고 고쳐서 맞았다. 698/800점을 받고 잤다. R2를 어쨌든 갈 거 같아서 고칠까 말까 하다가, 만점자가 꽤 많아서 무섭기도 하고, 블로그에 "이런 풀이를 짰는데 틀렸더라 ㅎㅎㅋㅋㅈㅅ" 라고 글을 쓰기는 뭐해서 4번을 생각해봤다. 설마 싶은 반례가 있었는데 머릿속으로는 이게 반례인지 아닌지 긴가민가했다. 짜 보다 보니까 반례인게 확실해 보였다. 고쳐서 오후 1시 반쯤 만점 1. 친구들 말이 복잡하지만 이런 뜻입니다. $N$ 개의 정..
IOI 2021 Day 2 대회가 종료되었다. 올해 대회의 개최지는 싱가포르지만, COVID-19로 인하여 현장 대회는 취소되었다. 대회는 모두 온라인으로 진행되며, 한국 학생들은 서울에서 모여서 감독 하에 대회를 진행하고 있다. 한국 학생들의 최종 성적은 다음과 같다. 메달 결과는 1금 2은 1동이다. 반딧불, 100 / 67 / 70 / 100 / 62 / 75, 474점, 7등, 금메달 송준혁, 38 / 37 / 100 / 100 / 50 / 46, 371점, 31등, 은메달 최서현, 100 / 9 / 5 / 100 / 89 / 33, 336점, 47등, 은메달 장태환, 11 / 37 / 70 / 100 / 11 / 21, 250점, 122등, 동메달 Day 1의 만점자인 Mingyang Deng이..
IOI 2021 Day 1 대회가 종료되었다. 올해 대회의 개최지는 싱가포르지만, COVID-19로 인하여 현장 대회는 취소되었다. 대회는 모두 온라인으로 진행되며, 한국 학생들은 서울에서 모여서 감독 하에 대회를 진행하고 있다. 한국 학생들의 성적은 다음과 같다. Day 1 기준이고, Day 2 점수를 감안하지 않았음을 유념하라. 반딧불, 100 / 67 / 70, 237점, 7등 - 11등 송준혁, 38 / 37 / 100, 175점, 28등 - 29등 장태환, 11 / 37 / 70, 118점, 71등 - 100등 최서현, 100 / 9 / 5, 114점, 102등 Day 1 만점자는 중국의 Mingyang Deng이 유일하다. 전체적으로 예년에 비해서 난이도는 어려운 편이다. 점수판을 보았을 때 ..
방향 그래프 $G$ 에 대해서, $G$ 의 위상 정렬 $O: V \rightarrow [n]$ 은 모든 간선 $u \rightarrow v$ 에 대해서 $O(u) < O(v)$ 가 성립하는 순열로 정의된다. $G$ 의 위상 정렬이 존재하기 위해서는 $G$ 가 사이클이 없어야 한다는 사실이 잘 알려져 있다 (Directed Acyclic Graph, DAG). 방향 그래프에 사이클이 없다면, 위상 정렬을 적용할 수 없다. 이 경우에는 그래프에 대한 강연결 컴포넌트 (SCC) 를 구해서 사이클을 하나의 정점으로 묶어주고, 이 DAG에서 위상 정렬을 적용하는 방법이 자주 사용된다. 위상 정렬과 SCC는 방향 그래프에서 사용하는 가장 기초적인 알고리즘 중 하나이며, 그 중요성에 대해서는 길게 설명하지 않겠다. ..
오랜만에 써 보는 후기 글 Qualification Round Rank 8381 / 42 points. 30점 통과로 다음 라운드 진출했다. 1번은 쉬운 문제였다. 2번은 DP로 했는데 그리디를 써도 잘 된다는 걸 나중에 알았다. 3번도 쉬운 문제 같았으나, 꼼꼼한 구현이 필요해 보였다. 어차피 3/4번 중 하나만 풀면 되어서 시도하지 않았다. 4번은 처음에 재밌는 문제라고 생각하고 짰다가 몇번 틀렸고, 알고 보니 지문을 잘못 읽었었다. 적당히 통과할 정도로만 풀고 넘어갔다. 5번은 뭐 뭔소리인지 모르겠네 알기 싫다. Round 1A 당시 육군훈련소 군사훈련으로 불참;; 인터넷 편지로 1A 3번 문제를 보내 주신 분이 두 분 계셨다. 감사합니다. (__) Round 1B Rank 641 / 59 poin..
사실 지금 쓰고 있는 글이 더 있긴 한데 일단 이 정도만 공개합니다. USACO FEB20 Silver. Triangles 일반성을 잃지 않고, 빗변이 직각 모서리의 우상향에 존재한다고 가정하자. 다른 방향들은 점들을 축에 대칭시킨 후 똑같이 해보면 된다. 직각인 점 $(x_1, y_1)$ 를 하나 고정시켰다면, 우리가 원하는 것은 이 점의 위에 있는 점 $(x_1, y_2)$ 과 오른쪽에 있는 점 $(x_2, y_1)$ 을 골라서 $(x_2 - x_1) (y_2 - y_1)$ 을 모두 합하는 것이다. 이 때 곱해지는 두 항이 독립이기 때문에, 모든 가능한 $(x_2 - x_1)$ 을 합하고, $(y_2 - y_1)$ 을 합한 후 이 값을 곱해줘도 된다. 이렇게 되면, 모든 점에 대해서 이 점 위에 있는..
Project-TCS 발표 자료 알고리즘에서 분할 정복 은 큰 문제를 부분 문제로 나누는 과정을 뜻한다. 이 때 부분 문제들이 가져야 하는 특징은, 원래 문제보다 쉬워야 하고, 부분 문제를 합칠 수 있어야 한다. 예를 들어서, Heavy Light Decomposition은 트리에서 큰 문제를 부분 문제로 나누는 과정에서 자주 등장한다. 각 문제가 쉽고 (직선), 합치는 것이 가능 (Light edge를 통해서 묶음) 하기 때문이다. 트리의 경우에는 HLD 외에도 다양한 분할 정복 기법이 존재하지만, 그래프를 분할 정복하는 것은 쉽지 않다. 일반적으로, Treewidth와 같이 그래프의 특수한 성질을 요구하는 경우가 많다. 이번에 다룰 Expander Decomposition 은, 그래프의 특수한 성질과..
서울대학교 2020 Div2 C. 넴모넴모 2020 각각의 쿼리에 대해서, $a_x > y$ 이면 답은 자명히 0입니다. 아니면, $a_j \le y$ 를 만족하는 최소 $j$ 를 찾음으로써 간단한 수식으로 문제를 해결할 수 있습니다. 이러한 $j$는 이진탐색을 사용하여 찾으면 됩니다. VKOShP 2017 D. Equal Maximums 두 구간이 공통으로 가지는 최댓값 $X$ 를 고정하고 문제를 해결해 봅시다. $X$ 의 등장 위치를 배열에 모두 마킹하면, 두 구간은 $X$ 를 하나 이상 포함하는 겹치지 않는 구간의 모습을 보입니다. 왼쪽 구간에서 가장 오른쪽에 등장하는 $X$ ($X_1$ 로 표기합니다.), 오른쪽 구간에서 가장 왼쪽에 등장하는 $X$ ($X_2$ 로 표기합니다.) 를 고릅시다. 이..
ABC 159 A. The Number of Even Pairs $N(N-1)/2+M(M-1)/2$ 를 출력하시면 됩니다. ABC 159 E. Dividing Chocolate 가로로 초콜릿을 자를 수 있는 모든 $2^{N-1}$ 개의 경우를 다 시도해 봅시다. 세로로 자를 때는 그리디 알고리즘을 사용할 수 있습니다. 왼쪽에서 오른쪽으로 순서대로 봅니다. $K$ 초과의 초콜릿이 생기지 않을 때까지 최대한 초콜릿을 자르지 않고, $K$ 초과의 초콜릿이 생기면 그 전 지점에서 잘라줍니다. 이 알고리즘은 가로로 자르는 방법이 고정되어 있을 때 최적이며, $O(NM)$ 에 구현할 수 있습니다. 고로 시간 복잡도는 $O(2^N NM)$ 입니다. ARC 110 A. Redundant Redundancy 나머지가 모..
- Total
- Today
- Yesterday