Sunday, September 22, 2013

acmicpc.net - 2013 인터넷 예선 대비 대회 7


이번에는 명우랑 역할분담이 잘되어서 릴레이 식으로 잘 푼 것 같다ㅎㅎ

Link : http://www.acmicpc.net/contest/view/14

A. 삼각 그래프 - Accepted
위상정렬 + dp이지만 그래프 특성상 위상정렬을 별도로 할 필요없음.

B. 피파 월드컵 - Accepted
2^x꼴로 만들어주면 된다.

C. 아즈텍 피라미드 - Accepted
계차수열임을 알면 쉽게 풀 수 있다.

D. 나이트 이야기 - Later Solved
그리디하게 100*100 안으로 넣은 다음에 bfs를 통해 구한 값을 이용해서 나이트의 최소 이동 횟수를 알 수 있다. 그 다음에는 bitmask dp를 통해서 풀면 됨. 종료 3분 후, Accepted 받음.

E. 정규형 - Accepted
명우가 혼자 풀었는데 특별히 어렵지는 않은 문제인 것 같다.

F. 월드 오브 큐브 - Not Solved
문제 보고 어려운 것 같아서 안 품.

G. 최대 공통 증가 수열 - Accepted
"D[n][m] : S가 1~n까지, A가 1~m까지일 때의 최대 길이"라고 정의하고 dp로 풀면된다.
O(N^3)을 떠올리기 쉽지만, 전처리를 통해서 O(N^2)으로 풀 수 있다.

H. 병원 - Accepted
문제 이해하기가 힘든 문제. O(VE)에 명우가 품.

I. 사탕 줍기 대회 - Accepted
어떤 k번째 행에서 i번째를 선택하면 i-1번째와 i+1번째를 선택하지 못하는 경우의 최대합을 구하는 함수를 dp(k)라 하자. 모든 행에 대해서 dp(k)를 수행하고 그 값들로 새로운 행을 만들어서 다시 dp(k)를 수행하면 된다.

J. 거의 최단 경로 - Accepted
별로 어렵지 않은 문제. 명우가 품.

No comments:

Post a Comment