구사과

관련 내용이 이 블로그에도 매우 잘 나와 있으니 같이 보면 좋을듯. 이 글에서는 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라고..

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 먼저 각각의 사람을 몸무게 순으로 정렬해 놓읍시다. 가장 가벼운 사람은 다른 사람과 보트를 태워 보내는 것이 합리적으로 보이니, 가장 가벼운 사람을 보낼 때는, 다른 사람 한 명을 잡아서 같이 보트를 태워 보냅니다. 같이 탈 수 있는 사람이 여럿이면 물..

후기 안 쓰려고 했으나 그냥 간단히 써보려고 한다. 11월 9일 금요일 대전에서 CMP 팀과 함께 인천공항으로 출발했다. KTX 탈 때마다 홍보하는 광명역 도심공항터미널을 이용해 보았는데, 안내도 잘 안되어 있고 버스비도 비쌌다. 서울역에서 공항철도 타고 가는게 훨씬 더 싸고 편했을 거 같다. 😠 인천공항 게이트 쪽에 일본 사람들이 있었는데 대회 후드인걸 보았을 때 누가 봐도 ICPC를 참가하는 사람들 같았다. 아마 2등한 교토대 팀이었을 것 같다. 하지만 대회 끝날 때까지 말할 기회는 없었다 :( 숙소는 기숙사라서 기대하지 않았는데, 거의 호텔급이어서 놀랐다. 매우 좋았다. 근데 수건이 2개였다. 😠 11월 10일 토요일 단체 사진을 찍고 가이드와 만났다. 한국에 관심이 많은 분이어서 기본적인 한국어는..

(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이 있는지 (……) 에 대해서는 전혀 언급하지 않습니다. 저러한 내용에 과도하게 걱정하시는 분들이 참 많은데, 별로 안 좋은 습관이라고 딱 잘라 말하겠습니다. 보통 상위권이라고 저런 거에 대단한 철학이 있지는 않습니다. 개인 성격 따라 제각기 하는 방법이 다릅니다. 본인 성격에 맞는 방법을 찾기 위해서는 시행착오 말..