구사과

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