2021 KOI 2차대회 후기

64, 52, 5 긁고 장려뜸

 

1

반지름에 대한 dp를 생각해보았지만 아무리해도 생각이 안나서 n^2 dp를 짜고 끝냈다. 반지름 r에 대한 dp를 짜면 아무리 봐줘도 r은 최대 500이니까 안터진다.

 

2

한 정점의 값을 a로 두고 사이클에 주의하며 dfs를 돌리면 끝이다. 사이클이 생길때 홀수, 짝수일때 경우를 나눌 수 있다. 사이클이 홀수이면 a가 확정되므로, 여기서 정수인지 확인하고 모든 정점의 값을 식에 맞추어 쭉 대입하면 된다. 그러고 모든 간선에 대해서 식이 성립하는지 확인하면 끝.

 

사이클이 짝수이면, 식들에서 a가 사라지기 때문에 a를 확정할 수 없으므로 항등식이 되는지 확인하면 된다.

 

그렇게 a가 확정이 안되고 끝났으면 |a - k1| + |a - k2| ... 꼴의 식의 합을 최소화하는 a는 k1, k2...의 중앙값이 된다.

 

왜 틀렸는지 글을 쓰면서 지금 알아냈는데, 사이클이 생기면 |a-k| 식을 정해주지 않고 바로 dfs를 종료해서였다. ㅠ

 

3

접미사+LCP인데 대회 끝나고 직후에 생각났다.

 

4

모르겠다.

 

 

애매하게 아는 사람의 최후. 이제 nypc하고 수능공부해야지(아마)