구사과

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이 유일하다. 전체적으로 예년에 비해서 난이도는 어려운 편이다. 점수판을 보았을 때 ..

오랜만에 써 보는 후기 글 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)$ 을 합한 후 이 값을 곱해줘도 된다. 이렇게 되면, 모든 점에 대해서 이 점 위에 있는..

서울대학교 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 나머지가 모..

최소 스패닝 트리 (MST) 는 무방향 그래프에서만 정의되는데, 방향 그래프에서도 MST 비슷한 것을 정의하기도 합니다. Minimum Arborescence 이라고도 부르는데, 방향 그래프 $G$ 와 루트 정점 $r$이 주어졌을 때 무방향 그래프로 봤을 때 사이클이 없고 $r$ 에서 모든 정점을 도달 가능하면 이를 $r$ 을 루트로 한 Directed MST라고 합니다. 루트 정점을 무조건 정의해 줘야 함에 주의해야합니다. 이 글에서는 Chu–Liu/Edmonds' algorithm 이라고 불리는, Directed MST를 구하는 알고리즘을 간단히 소개합니다. 일반적으로 $O(VE)$ 시간 복잡도에 해결하는 방법을 사용하는데, 여기서는 $O((V + E) \log E)$ 에 문제를 해결할 것입니다. 다..

NAC 2020 F. Hopscotch 50 간단한 DP 입니다. $dp[i][j]$ 를 $(i, j)$ 셀에 도착하는 최소 비용이라고 합시다. 만약 이 셀에 1이 적혀 있으면 답은 0입니다. 아니면, 이 셀보다 적힌 숫자가 1 작은 모든 셀 $(k, l)$ 이 이 셀로 들어오는 것이 가능한 후보가 됩니다. 모든 후보 중 $dp[k][l] + |k-i| +|l-j|$ 값의 최소를 취해주면 됩니다. 이대로 구현하면 시간 복잡도는 $O(N^4)$ 입니다. Ptz Winter 2019 Day7 G. Permutant 주어진 순열이 2개 이상의 사이클을 포함하고 있다면, 답은 0이 됩니다. 주어진 순열이 “정확히 2개” 의 사이클을 포함하고 있을 때에 대해 증명하면, 두 사이클의 길이가 a / b라고 할 때, ..

(2020.11.24 01:27 - 모든 문제를 구현해서 풀이를 검증했으며, 일부 풀이를 고쳐 적었다.) (2020.11.23 01:32 - 모든 문제에 대한 풀이를 올렸다.) Result Analysis 이번 서울 리저널에서의 각 대학 별 상위 팀은 다음과 같다. 서울대학교: Let Us Win ICPC WF (World Finals 진출 확정) KAIST: Everybody (World Finals 진출 매우 유력) 고려대학교: 1_Hoeaeng_2_Hawawang (World Finals 진출 예상) 숭실대학교: 181920 (World Finals 진출 가능성 있음) 성균관대학교: we need sleep 올해 서울 리저널은 관전자 입장에서 재밌게 볼 만한 요소가 아주 많은 대회였다. 그래서 관전..

원래는 블로그 글을 좀 자세하고 정확하게 쓰려고 노력하는 편이나, 인터넷 예선은 채점해 보기도 까다롭고 하니 그냥 대충 정리해서 올리려고 한다. 완전 입풀이고, 코드를 한 줄도 안 짜보고 올리는 글이라서, 내용이 부정확할 수도 있다. (10/20 추가: 현재 C H 빼고 모두 채점이 된다. 해당 문제들에 대해 블로그에 나온 방식으로 구현해서 전부 정답을 받았다.) A 최종 정렬된 배열을 생각해 보자. 이 배열의 부분배열(연속) 중 원래 입력으로 주어진 배열의 subsequence를 만족하는 최대 길이의 부분배열을 찾으면 된다. 중복이 없으면 그냥 원래 배열에서의 index가 증가하는 최대 길이 부분배열을 찾으면 된다. 아닌게 귀찮은데.. substring 상 서로 다른 원소가 1개, 2개, 3개 이상인 ..

IOI 2020 Day 1 대회가 종료되었다. 올해 대회의 개최지는 싱가포르지만, COVID-19로 인하여 현장 대회는 취소되었다. 대회는 모두 온라인으로 진행되며, 한국 학생들은 서울에서 모여서 감독 하에 대회를 진행하고 있다. 한국 학생들의 성적은 다음과 같다. Day 1 기준이고, Day 2 점수를 감안하지 않았음을 유념하라. 최은수, 100 / 100 / 100, 300점, 1등 - 7등 송준혁, 75 / 100 / 100, 275점, 8등 - 13등 반딧불, 32 / 100 / 53, 185점, 61등 - 63등 임성재, 44 / 100 / 41, 185점, 61등 - 63등 특기할 점은 한국 학생들의 성적이 상당히 우수하다는 것이다. 최은수 학생은 300점 만점이라는 아주 훌륭한 성적으로 대회..