Codeforces Round #812 (Div. 2)

https://codeforces.com/contest/1713

 

A. Traveling Salesman Problem

 

모두 x축, y축위에 존재하므로 x축 방향으로 왔다가고, y축 방향으로 왔다가는 것을 생각하면 된다.

 

B. Optimal Reduction

 

당연히 최적의 경우는 양 끝에 제일 작은 원소들이 존재해서 순서대로 온 범위에서 1씩 뺄 수 있는 것이다.

 

C. Build Permutation

 

우선 대충 항상 가능할 것이라는 감을 잡을 수 있다.

n보다 살짝 큰 sq * sq가 있다고 가정하자. 그렇다면 뒤에서부터 sq * sq - i 을 배정해주면 된다.

최대한 많이 배정해준다음에 더 이상 배정이 불가능하면 n을 바꿔주고 반복하면 된다.

 

cf) flow로도 가능하다는데 너무 비효율적이기도 하고...

 

D. Tournament Countdown

 

2번의 operation으로 3명을 떨어뜨려야 한다.연속된 a, b, c, d가 있을 때 "? a c"라는 쿼리를 통해서 b나 d를 굳이 물어보지 않고 탈락시킬 수 있다.

 

E. Cross Swapping

 

제일 앞에 있는 a[i][j]부터 더 강한 권력을 가진다.즉 a[i][j]는 flip을 원하는데 a[i][j'] (j < j')은 flip을 원하지 않더라도 i에서 flip이 일어날 것이다.a[i][j] > a[j][i]라면 -> i나 j 중에 하나만 flip이 일어나기를 바람 -> i와 j의 flip 여부가 서로 다름a[i][j] < a[j][i]라면 -> i와 j 중에 0개 혹은 2개에서 flip을 바람 -> i와 j의 flip 여부가 서로 같음서로 같지 않은 이상 어떤 일이든 간에 i와 j 간의 연관성이 생긴다. (즉 i가 결정되면 j가 결정됨)union find를 이용하여 서로 연관성이 생긴 애들을 합쳐주면 된다.만일 이미 i와 j가 같은 root를 가진다면 이 경우에는 새로운 연관관계가 생겨나면 안된다.

따라서 앞에서부터 각 flip간의 연관관계를 모두 연결해주면 된다.

마지막에 dfs를 통해서 구할 수 있다. (물론 2sat도 가능)

 

F. Lost Array

 

a -> b의 과정은 Lucas Theorem에 의해 SOS DP(=Zeta transform)라고 생각할 수 있다.

-> (n - i)가 ~(j - 1)의 subset이라면 bj가 ai를 가지므로 a를 뒤집고 zeta transform을 해주고 뒤집으면 b이다.

 

이제 이 과정을 역방향으로 해주면 된다.

https://codeforces.com/contest/1713/submission/167269929