구사과

Topcoder SRM 744 Easy는 그대로는 매우 귀찮으나, 2차원 부분합을 구할 때 쓰는 포함 배제 테크닉을 활용하면 조금 덜 귀찮아진다. 물론 그래도 귀찮다. 난 문제를 잘못 읽어서 망했다. Medium은 행과 열에 대해서 해당 행 / 열을 뒤집었는가? 를 나타내는 $n+m$ 개의 boolean 변수를 잡으면, 주어진 조건은 $X_i + X_j$ 의 홀짝성에 대한 제약조건으로 바뀐다. 이를 일종의 이분 그래프라고 생각하고 풀어주면 된다... 라는 류의 문제를 한 두 번 본게 아니어서 그냥 아무 생각 없이 코드를 짰으나 문제에 함정이 있다는 것을 늦게 깨달았다. 고치니까 150점. Hard는 큰 트리에서 특정한 형태의 선형 계획법 (LP) 를 돌리는 문제이다. small-to-large 트릭을 활..

방학동안 삼성전자 소프트웨어 멤버쉽에서 팀연습을 계속 진행하고 있다. 아래는 그 기록이다.12월 23일아침: Atcoder Regular Contest 077 C D E F koosaga 3:04 17:04 26:24 - tncks0121 4:51 21:30 45:37 - alex9801 24:20 34:13 47:11 - 점심: GP of Xian매우 말려서 루즈한 분위기로 계속 진행했는데 끝나고 나니까 등수가 기대 이상으로 높았다. 대체 왜 높을까.. * A는 풀이가 궁금한데 아무도 안 적어 준다.* B는 NEERC 2018 I와 비슷한 유형의 카운팅 문제이다. 수학 못하는 팀이라 대회 때는 아무도 안 잡았다 (그건 잘 한거 같다.) 나중에 NEERC 업솔브 할 일 있으면 비슷한 유형으로 풀어보면 좋..

난이도 순입니다. 1. ARC 051. Sum of Three Integer $A, B$ 를 정하면, $C = S - A - B$ 로 자동으로 정해집니다. 고로 모든 $A, B$ 를 이중 루프로 순회하고, $0 \leq C \leq K$ 를 확인하면 됩니다. $A, B$의 가짓수가 각각 $K+1$개이니 시간 복잡도는 $O(K^2)$입니다. 포함배제 원리를 사용한 $O(1)$ 풀이도 있지만, 이 문제에서는 필요 없습니다. 2. POI 1997. Canoes 먼저 각각의 사람을 몸무게 순으로 정렬해 놓읍시다. 가장 가벼운 사람은 다른 사람과 보트를 태워 보내는 것이 합리적으로 보이니, 가장 가벼운 사람을 보낼 때는, 다른 사람 한 명을 잡아서 같이 보트를 태워 보냅니다. 같이 탈 수 있는 사람이 여럿이면 물..

(2018.11.10: H를 제외한 모든 풀이를 작성하였다.)(2019.07.05: I 문제를 Chordal Graph로 푸는 방법에 대한 간단한 부연설명을 추가하였다.) Result Analysis 이번 서울 리저널에서의 각 대학 별 상위 팀은 다음과 같다. 서울대학교: 789 (순위 외: 2018 WF 은메달) 도쿄대학교: Gifted Infants (순위 외: 2018 WF 금메달) KAIST: Deobureo Minkyu Party (리저널 1등) 국립 타이완 대학교: waynedisonitau123 (리저널 2등) 한양대학교: FailedSystemTest (리저널 3등) 시상식을 대회 후에 진행해서 엄청나게 김이 빠졌지만... 올해 리저널은 작년에 비해서 흥미로운 결과가 여럿 있었다. 서울대학..

리저널 전 연습 기록을 간단하게 적는다. 정말 간단하고 부실하게 적을 예정이다. 10/23 화요일 NEERC Southern Subregional 2018을 돌았다. 12/13으로 만족스러웠다. H는 처음 보고 복잡하게 생각했으나 알고 보니 쉬운 문제였다. J는 재밌는 냅색 문제였다. I는 쉬운 매칭인데 우리가 무식해서 엄청 돌아갔다. L은 못 풀겠어서 답이 2 이하라고 찍고 gaussian elimination을 돌렸다. 다행이도 맞았다. 알고보니 내가 옛날에 풀었던 POI (Two Parties) 였는데 대회 중에는 전혀 눈치 못챘다. 일찍 슥삭할 수도 있었는데 매우 아쉬웠다. M은 모르겠다. 10/24 수요일 기하 연습을 했다. A는 제한을 보고 당연히 N^3일 줄 알았는데 안 적혀있는 T가 매우 ..

최근 카이스트 대회 기출 문제가 run.kaist.ac.kr/contest 에 전부 올라와 있습니다. 테스트 데이터나 풀이를 전부 공개하였으니 많은 관심 부탁드립니다! 맨 아래 과거 기출 문제 / Past Problemset 섹션에 모두 올라와 있습니다. KAIST Contest 2018. Fractions 편의상, $A = C = 1$ 이라고 가정합시다. 이렇게 될 경우 $x, y$의 상한만이 존재하고 하한은 존재하지 않습니다. 이 가정을 하더라도 문제를 여전히 해결할 수 있는데, 만약에 위 문제를 해결하는 함수 $f(B, D)$ 가 존재한다면, 우리가 출력해야 하는 답은 포함-배제의 원리를 사용하여 $f(B, D) - f(A-1, D) - f(B, C-1) + f(A-1, C-1)$ 로 계산할 수 있..

(2018.11.07: ICPC 대회 난이도에 별점을 매겼습니다. 사실 제일 중요한 건 난이도인거 같아서 마음에 좀 걸렸는데, 이렇게 하면 조금 더 가시성이 있지 않을까 싶네요.) 공부하기 싫어서, 제가 평소에 어떻게 연습하는 지에 대해서 간략히 글을 씁니다. 이 글은 연습 방법론, 예를 들어 하루에 몇 시간씩 하는지 / 풀이는 언제 보는지 / 뭐 먹고 사는지 (...) / Secret Tip이 있는지 (……) 에 대해서는 전혀 언급하지 않습니다. 저러한 내용에 과도하게 걱정하시는 분들이 참 많은데, 별로 안 좋은 습관이라고 딱 잘라 말하겠습니다. 보통 상위권이라고 저런 거에 대단한 철학이 있지는 않습니다. 개인 성격 따라 제각기 하는 방법이 다릅니다. 본인 성격에 맞는 방법을 찾기 위해서는 시행착오 말..

pre Scoreboard 지끈..뭐라 뭐라 더 쓰고 싶으나, 내 블로그가 불편한 이야기를 쓰기에 적합한 장소는 아니라고 생각이 든다. Problems / Solution Sketch 이번에는 문제 난이도가 비슷한 문제들이 많아서, 사람들이 느끼는 난이도에 이견이 매우 클 수 있다고 생각했다. 마음 같으면 스코어보드 읽고 많이 푼 순서대로 정렬하고 싶으나, 스코어보드가 공개되지 않은 상황이라 그냥 블로그 주인장 마음대로 정렬한다. I. Registration B. Farm 양의 수 $i$를 1부터 $N-1$ 사이의 정수로 고정하면, 염소의 수는 $N - i$ 마리이다. 그러면 그들이 먹는 음식의 양도 계산할 수 있다. 음식의 양을 $w$ 로 가지는 양의 수의 개수를 세어 주고, 유일하면 그 수를 출력하면..

https://beta.atcoder.jp/contests/arc103/tasks/arc103_d일단 일반성을 잃지 않고 $D_1 1$ 번 노드의 부모는 $i$번 보다 작은 번호를 가진다. 이 부분의 증명은 생략한다. Centroid의 성질을 생각해 보면 그렇게 어렵지 않다.고로 루트 (centroid) 를 기준으로 하나 하나 노드를 붙여나가는 식의 풀이가 될 것이라고 생각할 수 있으나, 생각처럼 잘 안된다. 어떠한 노드를 추가할 때 무슨 노드를 부모로 삼을 지가 명확하지 않다.여기서 발상을 전환시켜서, 위 과정을 반대 방향으로 해 보자. $N$번..

(2024.09.02 - Meetings의 풀이를 작성하여 첨부하였다.)(2018.09.22 - 원문 작성)IOI 2018 Day 2가 종료되었다. 한국 학생들의 최종 성적은 다음과 같다.노영훈, 100 / 37 / 49 / 100 / 51 / 36, Day2 13등, 종합 12등. 금메달.강태규, 100 / 25 / 49 / 100 / 69 / 19, Day2 11등, 종합 17등. 금메달.김세빈, 100 / 37 / 49 / 63 / 51 / 60, Day2 20등, 종합 18등. 금메달.윤교준, 100 / 5 / 49 / 86 / 51 / 4, Day2 38등, 종합 59등. 은메달.IOI Statistics를 보았을 때, 평균 성적과 만점자를 통틀어 봐도 최근 10년 대회 중에서 이보다 어려운 하..