구사과

IOI 2019 Day 2 대회가 종료되었다. 한국 학생들의 성적은 다음과 같다. 김세빈, 100 / 100 / 40 / 72.30 / 66 / 57, 435.30점, Day2 27등, 전체 18등, 금메달. 윤교준, 72 / 100 / 40 / 90.97 / 66 / 57, 425.97점, Day2 16등, 전체 22등, 금메달. 임유진, 72 / 100 / 40 / 61.41 / 66 / 57, 396.41점, Day2 40등, 전체 37등, 은메달. 이온조, 38 / 100 / 64 / 50.61 / 52 / 24, 328.61점, Day2 120등, 전체 83등, 동메달. 미국의 Benjamin Qi는 작년과 같이 이번에도 Day 2에서 조금 노는 (?) 모습을 보였고 1등 성적을 받지 못하였으나..

IOI 2019 Day 1 대회가 종료되었다. 한국 학생들의 성적은 다음과 같다. Day 1 기준이고, Day 2 점수를 감안하지 않았음을 유념하라. 김세빈, 100 / 100 / 40, 240점, 8등 - 25등 윤교준, 72 / 100 / 40, 212점, 26등 - 59등 임유진, 72 / 100 / 40, 212점, 26등 - 59등 이온조, 38 / 100 / 64, 202점, 60등 올해도 미국의 Benjamin Qi가 만점인 300점을 3시간 30분만에 얻었다. 문제가 쉽지 않았음에도 불구하고 빠른 시간 안에 300점을 얻은 것이 놀라울 따름이다. 단순히 Day1에서 큰 점수차를 보여줬을 뿐만 아니라 실질적으로 다른 학생들과 실력 격차가 크다는 것을 증명했다고 생각한다. 2019년 2연속 우..

고등부 1번. 타일 타일 문제는 복잡한 알고리즘을 요구하지 않아서 풀이로 적을 내용은 길지 않으나, 구현 면에서 까다로운 점이 있는 문제이다. 고등부 1번을 풀지 못하였을 경우 다음과 같은 공부법을 추천한다. 고등부 1번 뿐만 아니라 어떠한 문제를 해결하더라도 이러한 방식으로 접근하는 것이 좋다. 먼저 컴퓨터를 일절 사용하지 않고 펜과 종이만을 사용하여 적절한 수도코드(pseudo-code)로 코딩을 완료해 놓은 후, 종이에 적힌 내용을 구현하고 정답 결과를 확인한 후, 틀렸을 경우 1번으로 반복 맞았을 경우 다른 좋은 구현을 보고 차이점 분석 Subtask 1/2 (45점) 타일을 교체하는 선택지가 없기 때문에, 문제에서 주어진 입력 하에 차량이 도착점으로 움직일 수 있는 지를 판별하면 된다. 이는 시..

중등부 1번. 신기한 수 Subtask 2 (100점) 숫자 $N$ 이 주어지면, 해당 수의 일의 자리에 적힌 수는 $N \mod 10$ 이 된다. 이후 숫자를 10으로 나눠주면, 십의 자리, 백의 자리… 에 있던 수들이 모두 일의 자리, 십의 자리로 움직인다. 고로, 이를 반복하면 $O(\log N)$ (입력에서는 최대 8번) 의 단순 연산으로 $N$의 자릿수 합을 알 수 있다. 어떠한 수 $A$ 가 어떠한 수 $B$ 로 나누어 떨어지는 것은, $A$ 를 $B$ 로 나눈 나머지가 0이라는 뜻이니, C++ 나머지 연산자를 사용하여 판별할 수 있다. 중등부 2번. 개구리 점프 Subtask 1 (19점) 어떠한 두 선분 $p, q$ 사이를 오갈 수 있다는 것은, 특정한 좌표 $x$ 가 존재해서, $p, q..

A. Strange Device Subtask 1 (10점) 문제에 적힌 대로 모든 순서쌍을 나열한 후, 정렬하여 서로 다른 순서쌍의 개수를 세자. Subtask 4/5 (20점) 고정된 $0 \le y < B$ 에 대해서 쌍이 겹칠 수 없으니, 각각 따로 문제를 해결한 후 합쳐주자. $t = qB + y$라고 하면, $x = qB + y + q$ 로 표현 가능하다. 이때, $y$ 는 상수이고, $q(B+1) + y \mod A$라는 식은 $q$가 $T = A / gcd(A, B + 1)$ 주기로 반복됨을 알 수 있다. 각각의 구간 $[L_i, R_i]$ 에 대해서, 가능한 $q$ 의 구간을 계산할 수 있다. 가능한 $q$ 의 구간을 계산했다면, 가능한 $q \mod T$ 의 구간 역시 알 수 있다. (..

Berlekamp-Massey 알고리즘은 특정한 DP의 점화식을 찾아주는 알고리즘이다. $10^{18}$ 번째 피보나치 수를 찾기 위해서 행렬 곱셈을 짜고, 타일 채우기 문제를 풀기 위해서 수많은 점화식과 씨름하던 옛 시간은 이젠 안녕. 이제는 백트래킹 짜고 하드 코딩해서 넣으면 끝난다. 이 글은 알고리즘의 구현법, 동작 원리나 증명에 대해서 거의 설명하지 않는다. 그 이유는 내가 구현법과 동작 원리, 증명을 모르기 때문이다. 알고리즘 구현은 여기에서 복붙해서 사용하면 된다. 이론적 배경지식이 상당히 깊지만, 그 활용도가 매우 높기 때문에, 일단 이해하지 말고 작동법부터 제대로 깨우친 후, 나중에 다시 돌아와서 방법을 이해하는 것을 추천한다. 1967년 이 알고리즘을 개발한 수학자 Elwyn Berlek..

뭐 했는지만 대충 알 수 있는 수준의 짧은 요약글로 정리하려고 한다. 다 쓰면 너무 길다.Day1 A: NEERC 2018 B랑 매우 비슷한 General Matching. D: 특수한 그래프에서 weighted bipartite matching을 빠르게 계산하는 문제. weighted bipartite matching은 가중치가 큰 순서대로 에지를 추가하면서, 최대 매칭을 증가시키는 것만 넣어주는 식으로 계산할 수 있다. 이렇게 가중치를 없에고 최대 매칭 문제로 환원하면, ARC076F / POI Ice Skates 에 나온 유형처럼, 홀의 결혼 정리 + Segment Tree 로 해결 가능. 사실 생략한 아이디어들이 이것저것 있는데 다 적으면 너무 길어지니 생략. E: planar graph에서 ra..

practice_ptzbf 1월 22일 연습 오후: ARC 064 CDEF ainta (guest)36:3549:3343:4434:33tncks01212:4823:389:2359:19koosaga3:3097:5631:58- 실제 연습 환경에서 한 게 아니라 변동 사항이 있을 수 있다. (아인타는 약간 늦게 합류했고, 집중할 수 있는 상황이 아니었고, 등등..)하지만 내가 문제를 못 푼 건 그래서가 아니었다. 일단 D의 풀이를 보는데 한 30분 정도를 사용했고, F를 보고 풀 수 있다고 생각하고 너무 과도하게 달려들었던 것도 참패 요인이다. F는 내가 보통 거르고 보는 약수 포배 유형이다. 풀이를 들었는데 웬만큼 잘 생각하지 않았으면 못 풀었을 문제인 것 같다. 그런데 그런 유형인지를 모르고 E를 푼 이후..

관련 내용이 이 블로그에도 매우 잘 나와 있으니 같이 보면 좋을듯. 이 글에서는 LP에 대한 정의를 안다는 것을 가정하기 때문에, 정의를 모른다면 링크한 블로그를 참고해야 한다. 직관 다음과 같은 LP 문제를 생각해 보자. $\text{Maximize: } 4x + 4y$ $\text{Subject to: } x + y \leq 3,x, y \geq 0 $ 이 문제의 답은 굉장히 자명하다. $(x+y) \leq 3$ 이라는 조건이 있으니, $4(x+y) \leq 12$ 를 만족한다. 그 외에 다른 제약 조건은 $x, y \ge 0$ 뿐이니 답은 간단히 12로 결정된다. 이를 조금 더 어려운 예시로 바꿔보자. $\text{Maximize: } 4x + y $ $\text{Subject to: } x+y \..

1월 1일 심야: Petrozavodsk Winter 2018. ITMO Contest 좋은 셋이냐 하면 그건 잘 모르겠는데... 확실히 배울 건 많은 셋이었다. 그래도 이번 신년 연습 중에서는 이게 그나마 제일 정상이었던 거 같다 (...) A는 적분 식을 찾았으나 너무 복잡해서 포기했다. 하지만 그 복잡한 적분을 노가다하는게 정해였다고 한다(...) 우웩 F는 connection 정보를 관리하는 DP를 짜면, 가능한 연결 상태가 약 3000개 ~ 4000개 정도이다. 이걸 directed graph로 모델링하면, 결국 여기서 거리가 $K$ 인 walk를 찾는 문제가 된다. 이는 Berlekamp-Massey를 사용해서 해결할 수 있다. 곧 블로그에 글을 쓸 지도 모름. H는 directed mst라고..