AtCoder Regular Contest 161

https://atcoder.jp/contests/arc161

 

A, B, C, D <<<<< E, F이라서 B에서 한 실수가 매우 치명적으로 들어갔다.

만일 실수가 없었으면 2800~2900 퍼포 쯤 나왔을 것

아무튼 빠르게 쉬운 문제를 풀 수 있는 사람들이 점수를 크게 딸 수 있는 기회였다. 

E, F의 난이도가 D에 비해 너무 어려웠지만 좋은 문제들인 것 같다.

또한 이렇게 크게 난이도가 벌어진 것은 C, D 가 쉬웠기 때문이지, ARC는 원래 E, F가 이것과 같거나 그 이상이다.

 

A. Make M

 

A를 모두 정렬해두고 홀수 번째에는 작은 숫자들을, 짝수 번째에는 큰 숫자들을 배정해 주는 것이 최선이다.

따라서 최선의 rearrange를 해두고 가능한지 확인해주면 된다.

 

B. Exactly Three Bits

 

1) 그냥 모든 경우의 수를 해도 되고 (C(60, 3))

2) 제일 앞 bit부터 배정이 가능한지 확인해가면서 만들어도 된다.

 

C. Dyed by Majority (Odd Tree)

 

Tree의 Leaf를 생각해보자. -> Par은 leaf가 원하는 색에 따라 저절로 결정된다.

Leaf가 아니라면 -> 만일 아직 색이 정해지지 않은 child가 있으면 모두 이 색으로 결정해주면 된다.

 

위의 과정을 Tree dp로 하면 된다.

Cur에 대해서 우선 child 중에서 색이 배정되지 않은 애들은 자신이 미래에 원하는 색으로 모두 배정해준다.

만약에 par이 어떤 색이 되더라도 자신의 원하는 색이 될 수 있다면 par에는 색을 배정하지 않는다.

만약에 불가능하다면 par에 자신이 원하는 색을 배정해준다.

-> 만일 배정해주는 과정에서 충돌이 이루어진다면 불가능한 것이고, 충돌이 없다면 그것이 답이 되는 트리가 된다.

 

D. Everywhere is Sparser than Whole (Construciton)

 

간단하게 모든 (i, i + d) 쌍을 연결시키면 된다.

직관적으로 생각하더라도 임의의 subtree에 대해서 절대로 그 밀도는 d를 넘을 수 없다.

 

pf1) 내 증명 : 밀도라는 개념보다는 (차수의 합) >= 2 * d * (정점의 개수)가 가능한지 확인히자.

d = 1일 때 : 만일 밀도가 1이 되려면 차수가 모두 2거나 2를 초과하는게 있어야 되는데 그것은 불가능하다.

d = k 일때 밀도가 k보다 strictly less이라면 모든 점의 차수가 최대 2 증가하므로 k + 1에서도 k + 1보다 strictly less

 

pf2) 에디토리얼 : 그래프를 (i, i + k)를 잇는 subgraph Gk 들로 쪼개자

-> 그렇다면 density = (G1에 의한 밀도) + (G2에 의한 밀도) + ... (Gd에 의한 밀도)가 된다.

-> G1에서 모든 subset은 밀도가 1보다 작고 나머지에서도 당연히 1 이하이기에 합은 d보다 strictly less

 

ㅡㅡㅡㅡ여기를 30분 내로 풀면 2850정도의 퍼포를 얻는다.

 

E. Not Dyed by Majority (Cubic Graph)

 

핵심 관찰 : 아주 높은 확률로 특정 color sequence는 불가능하다.

-> 따라서 랜덤하게 color sequence를 만들고, 그 color sequence를 평가하여 불가능함이 확인되면 제출하자.

 

그러면 이제는 이 color sequence가 가능한지 판단을 O(N) 내지 O(NlgN)으로 하는 것이 문제가 된다.

-> 만일 특정 정점 A가 색이 W라면, 이와 인접한 B1, B2, B3 중 2개를 고르면 반드시 색이 W인 애가 존재한다.

-> 따라서 Clause가 3N개인 2-SAT으로 치환할 수 있고, O(N)으로 이를 평가할 수 있다.

 

F. Everywhere is Sparser than Whole (Judge)

 

D에서 내가 construct한 그래프가 유일한 경우라고 생각하고 열심히 구현했는데 틀린 것 같다.

풀이가 상당히 흥미로운 문제이다.

 

1) D보다 큰 subset이 있는지 확인하기

density가 D보다 큰 subset (v, e)가 있다면 V - v = v' 랑 E - e = e'에 대해서 v' * D > e'가 성립한다.

그런 subset v는 없으므로 모든 subset v'에 대해서 연결된 간선의 집합 e'에 대해서 항상 v' * D <= e'이 성립한다는 뜻이다.

이것은 마치 v'과 e' 사이의 연결에서 홀의 결혼정리의 형태이다.

따라서 V * D와 E 사이에 Perfect matching이 가능하다

 

st -> V -> E -> en 형태의 flow graph를 만들어두고 st -> V = D, V -> E = 1, E -> en = 1이 용량인 그래프를 Dinic라 하자.

Dinic에 흐를 수 있는 총 flow가 ND이 안되면 perfect matching이 불가능하므로 D보다 큰 subset이 있다는 뜻이다.

 

2) D와 같은 subset이 있는지 확인하기

위의 Dinic에서 V1 -> E1 가 매칭이 되었다면, E1은 V1을 포함하는 간선이니 나머지 하나 정점 V2를 생각할 수 있다.

-> 여기서 V1 -> V2를 이어서 만든 그래프를 G라고 하자.

 

claim) 만일 G가 strongly connected가 아니라면 (SCC가 1개 초과라면) density가 D인 subset이 존재한다.

만일 1개 초과라면 SCC에서 나가는 edge가 없는 strongly connected proper subset이 존재한다. 

그렇다면 위의 Dinic에서 perfect matching을 시켰기에 SCC의 각 vertex에 대해 매칭된 D개의 간선이 존재한다.

이때 나가는 edge는 없으므로, 이들과 매칭된 모든 간선은 SCC 안의 다른 vertex와 연결된다.

따라서 이 SCC의 density는 반드시 D 이상이 된다. 

-> 사실 1)에서 이미 D 초과는 없음이 확인되었으므로 정확히 D인 subset이 된다.