C

문제 설명:

원 안에 2*n 개의 점이 있다. k개의 이어진 점의 쌍들이 주어지는데, 그 외의 점들을 임의로 2개씩 이어서 교차하는 횟수가 가장 많게 하라.

문제 해설:

먼저 알아야 하는 것은, 두 chords가 교차하지 않은 경우, 잇는 방법을 바꾸어 다른 chords과의 관계에 영향을 주지 않고 교차하게 할 수 있다는 것이다. 연결할 수 있는 점의 개수는 2*(n-k)개이다. 시계 방향대로 1,2,…,2(n-k)번이라고 했을 때, 1과 1+(n-k)번 점을 잇고, 2와 2+(n-k)점을 잇는 식으로 연결하는 것이 최적이다.
만약 그렇게 하지 않을 때를 생각해 보자. a와 b를 연결한 chords가 있다고 할 때 (a<b, b != a+n-k), 편의상 a를 1이라고 하면, 모든 점들은 {2,… , b-1}, {b+1,…, 2(n-k)} 인 두 그룹으로 나눠지게 된다. 둘 중 한 그룹은 적어도 n-k개의 점들을 가지고 있고, 두 그룹은 개수가 다르기 때문에 더 많은 그룹은 그 안에서 점이 서로 연결될 수밖에 없으므로 a-b와 교차하지 않기 때문에 최적의 연결이 아니다. 따라서 i와 i+(n-k)점을 잇는 것이 최선이다.

D

문제 설명:

배열 a 가 주어지고,임의의 b[i]-b[j]로 모든 a의 원소를 만들 수 있는 b가 존재하는지 찾는 문제이다.

문제 해설: b배열의 원소들을 vertex, a배열의 원소들을 edge로 하는 그래프가 있다고 생각해 보자. Vertex가 n개, edge가 n개가 있다면 필연적으로 사이클이 존재할 것이다. 이 사이클이 존재할수 있는지 체크하는 것이 이 문제의 핵심이다. 사이클만 존재한다면 그 사이클에 조건에 맞게끔 붙여 나가면 되기 때문이다.
사진을 보면, b0-b1-b2의 사이클이 존재하면, a4는 b3-b0=a4인 b3을 임의로 그래프에 추가하기만 하면 성립하기 때문이다.
사이클이 존재하는지 파악하는 방법은 아래의 식이 성립하는지 확인하면 되는데,
(m= 사이클의 길이, s_i=부호(-1,1 중에 하나) )
쉽게 말하면 s_i를 (-1,0,1)로 확장하고, 전체 탐색으로 모든 부호가 0일 때를 제외하고 합이 0인 경우이 존재하는지 알아보면 된다.