구사과

Algorithmic Engagements 2021. Koszulki 수열을 역순으로 정렬한 후 값이 $a_k$ 이상인 수를 출력하면 됩니다. POI 2019/2020. Najmniejsza wspólna wielokrotność 최소공배수가 $R - L$ 에 대해 지수적으로 커져서 탐색해야 할 쌍이 많지 않다는 사실을 사용합니다. $R - L = 1$ 인 경우, 최소공배수는 그냥 두 수의 곱입니다. $X(X+1) = M$ 을 만족하는 $X$ 가 존재한다면, $X, X + 1$ 을 출력하면 됩니다. 이 경우는 따로 처리합니다. 이차 방정식을 풀거나 이분 탐색을 하시면 됩니다. $R - L \geq 2$ 인 경우, 최소공배수는 적어도 $L(L+1)(L+2) / 2$ 이상입니다. 고로, $L \leq 2 \..

2023년 정보화진흥원 역량강화 교육 내용을 바탕으로 작성합니다. AC로 검증 못한 풀이들이 있어 주의를 요합니다. 2차 교육 B: L과 R의 중간 지점을 기준으로, 왼쪽에 있다면 R+1에 갈 필요가 없고, 오른쪽에 있다면 L-1에 갈 필요가 없다. 따라서, L과 R 중 하나를 고려할 필요가 없다. L을 고려하지 않고 문제를 해결하고, 반대의 경우는 대칭적으로 해결한다. R이 존재하지 않을 때 한 사람이 최대로 이동하는 거리 및 그 때의 총 이동 거리를 전처리해 두면, 사람이 있는 곳과 R이 주어졌을 때의 cost를 O(1)에 구할 수 있다. 이 때, 이 cost는 monge function이고, 2023 선발고사에 나왔던 “팀 만들기”의 60점 풀이를 그대로 사용하면 해결할 수 있다. D: $S < X..

그냥 아카이빙 목적으로 짧게 씁니다. 현대모비스 본선 대회 본인은 2021년 대회에서 8등인지 9등인지 했고, 2022년 대회에서 예선 탈락을 해서, 2023년 대회 참가가 가능했다. 1번을 열었는데 딱 봐도 따져야 할게 많아 보여서 힘들어 보였다. 따져야 할 걸 안 따지는 풀이를 짜니 10.2/15점이 나왔다. 일단 뒤로 넘어간 다음에, 뒤쪽 문제에서 주는 점수 기댓값이 4.8 미만일 때 돌아오기로 했다. 2번 뭔가 잘 안 읽혀서 뇌절하다가 대충 간선 하나 빼고 dag 경로 없는지 체크? 로 환원했다. 도미네이터 트리로 "풀 수는 있다" 는 것을 알았다. 더 생각해서 간단하게 만들 수도 있겠지만, 그냥 짤만해 보여서 도미네이터 트리를 짜기로 했다. 일반 그래프의 도미네이터 트리는 굉장히 테크니컬하지만,..