뭐 했는지만 대충 알 수 있는 수준의 짧은 요약글로 정리하려고 한다. 다 쓰면 너무 길다.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라고..
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)$ 로 계산할 수 있..
- Total
- Today
- Yesterday