ACM-ICPC Jakarta 2014

irc 눈팅하고 있다가 발견했는데 솔루션이 있길래 공부할 수 있겠다 싶어서 해봤다.

A. Cluster Analysis

그냥 정렬해서 쭉 한 번 보면 됨.

B. Body Building

이것도 그냥 하면 됨.

C. Electric Bike

평범한 DP.

D. Kevin’s Problem

그냥 경우의 수 세면 됨.

E. Cutting Tree

disjoint set을 써서 끊어질 것들을 먼저 다 끊은 상태에서 거꾸로 다시 연결하면서 했다.

F. Double Swords

E까진 쉽게 했는데 여기서부터 슬슬 한계가.. 일단 길이가 A_i인 검들은 무조건 필요하니까 만들고, B_j <= A_k <= C_j 이면 이 j 범위는 무시한다. [B_j, C_j]에 A가 있는지 빨리 확인하려고 segment tree를 썼다. 그리고 살아남은 [B_j, C_j]들은 정렬한 다음에 greedy하게 하면 된다.

G. Prime Switch

이 문제는 모르겠어서 풀이를 봤다. 보니까 왜 이걸 생각못했지 싶었다. sqrt(n)보다 큰 소인수는 최대 한 개 밖에 없다는 걸 못 떠울렸다. 다른 사람 코드를 보니까 비트마스크로 집합 순회를 한다. 나도 책에서 봤었는데 아직 필요할 때 안 떠오르는 것 같다. 그리고 long long에는 __builtin_popcountll을 쓰는군.

H. I Want That Cake

DP라는 건 바로 알았지만 그냥 하면 한 state당 K번 루프를 돌아서 시간초과가 된다. 이것도 잘 모르겠어서 풀이를 봤다. K번 중에 K-1번은 이전 state와 겹치기 때문에 K번 루프를 돌 필요 없이 O(1)에 된다. 이것도 생각못하다니 멍청하다.

I. Maze Mayhem

이것도 DP로 해야할 것 같긴 했지만 감이 안와서 풀이을 봤다.ㅜㅜ 나는 계속 한 칸을 한 state로 하려고만 생각했는데 한 row를 한 state로 했더라.

J. Leveling Ground

이건 쉽게 했는데 원래는 틀렸어야 하는 거였다.. sliding window로 쭉 한 번 보는 건 맞다. 근데 나는 구간에서 가장 낮은 높이를 구할 때 segment tree를 써서 lg(n)이 걸리는데 원래 의도는 이러면 TLE여야 하는 듯하다.. queue와 deque를 써서 O(1)에 할 수 있다. queue로 window를 유지하고 deque의 맨 앞에 가장 작은 원소가 오는 것이다. 그리고 매우 초보적인 정수 오버플로우 공격에 당해서 왜 틀렸나 한참 고민함 ㅠㅠ

K. Punching Robot

로봇이 10개 밖에 없으니까 포함 제외 원리에 따라 모든 경우를 세면 된다. 근데 여기까진 생각했는데 모르겠어서 답을 봤는데 Lucas’ theorem을 알아야했다. 또 하나 배움!

Leave a Reply

Your email address will not be published. Required fields are marked *