Atcoder Grand Contest 013

http://agc013.contest.atcoder.jp/

A. Sorted Arrays

단순 구현인데 코딩이 의외로 쉽지 않았다.

B. Hamiltonish Path

신기한 문제. path 어디에나 붙여도 되는 줄 알고 진짜 해밀턴 경로 문젠줄 알아서 좀 해멨다. 그런 경로를 아무거나 찾으면 되는 것이니 path 끝에 붙일 수 있는 정점이 있다면 무조건 붙여보는 식으로 풀면 된다. dfs로 쉽게 구현 가능.

C. Ants on a Circle

부딪힐 때 서로 방향을 바꾼다고 생각하지 않고, 서로의 번호만 바꿔서 가던 길 그대로 간다고 생각하면 복잡하지 않다. 이건 워낙 유명한 유형이니까 뭐...

그렇게 하면 전체 개미의 위치는 아주 쉽게 알 수 있다. 하지만 무슨 개미가 어떤 위치에 있는지는 어떻게 알까. 각각의 개미에 대해서, 해당 직선 경로를 따라가는 개미가 마지막으로 가지는 번호를 알면 된다. 그런데 결국 원 상에서의 개미들의 번호 순서는 어떻게 부딪히던 동일하게 유지되므로, 몇 마리의 개미들과 충돌하는 지를 계산하면 그 직선 경로를 따라가는 개미가 마지막으로 가지는 번호를 알 수 있다. 디테일한 설명은 생략함.

몇 마리의 개미들과 충돌하는 지를 계산하는 것이 남았는데, 원 한바퀴 돈거는 한꺼번에 계산하고 나머지는 이진 탐색을 쓰면 O(NlgN) 에 풀 수 있다. inchworm 쓰면 O(N)도 될 거 같은데 귀찮을듯

D. Piling Up

일단 거꾸로 생각해서 초록색 G개 빨간색 N-G개 있는 박스에서 원소 하나를 넣고, 초록색 빨간색 빼고, 원소 하나를 넣고... 이런 식으로 한다고 생각해보자. 원소를 뽑는 경우의 수가 2^(2M) 가지가 있는데, 그 중 초록색과 빨간색의 개수가 0 미만으로 떨어지지 않는 경우를 모두 세야 한다. 

단순히 생각하면 DP[X, G] -> "현재 2 * X 개의 원소를 뽑았고 그 과정에서 G개의 초록색 카드가 있음" 과 같이 정의를 해서 경우의 수를 세면 되지만, 문제는 중복된 원소들을 셀 수 있다는 것이다. 예를 들어서 N이 1000개 정도고 M = 2라고 생각해보면 998개 997개 996개.... 등 한 천번 정도는 똑같은 뽑기 경우의 수를 셀 것이다.

이런 중복 카운팅은 놀랍게도 엄청 간단하게 셀 수 있는데, 방법은 초록색 카드가 0개로 떨어졌던 sequence들만 세는 것이다. 만약에 한번도 0번 이하로 떨어지지 않았던 sequence가 있다면, 초기 초록색의 개수를 1씩 줄여도 똑같은 sequence를 만들 수 있다. 초록색 카드가 0개로 떨어진 sequence들은 중복해서 세지는 경우가 없다. 그래서 개이득. 그냥 여전히 simple dp다. 시간 복잡도는 O(NM).

E. Placing Squares

엄청 신기한 문제이다. 각각의 placement에 대해서 모든 (분할 길이)^2의 곱들을 더해야 하는데, 이 곱들을 조합적으로 다르게 해석할 수 있다. 각각의 분할 위치에 정확히 두개의 공이 들어가는 경우의 수라고 하면, i번 segment에 몇개의 공을 넣을 것인지, 또한 i / i+1번 segment를 분할할 것인지 아닐 것인지로 DP를 세울 수 있다. 이게 O(N) 풀이. 분할이 불가능한 segment (=mark된 segment) 에서는 약간 다르게 처리해야 한다.

그런데 문제를 보면 알 수 있다시피 절대다수의 segment가 분할이 가능하다. 그렇지 않은 것은 많아야 M개이다. 또한, segment가 분할이 가능하던 안 가능하던 각각의 변환을 3x3 행렬곱 연산으로 해석할 수 있다. 고로 O(M) 번의 행렬 지수승을 처리할 수 있으면 되고 이는 O(lgN)에 가능함. O(MlgN).

F. Two Faced Cards

http://koosaga.com/150 로 미룸.

총평

너무 심하게 수학 셋인거 같다.