오전 셋

카이스트 연습대회를 풀었다.

A. Aztec Diamond

무조건 바꾸는게 이득인 경우가 있고, 그걸 다 해주면 된다고 한다.

D. Dev, !!

SCC를 해주고, 2-SAT을 해주면 된다고 한다. 가는 길에 별을 먹을 수 있음에 유의하자.

F. Faster Sorting

전처리하고 그냥 다 돌면 O(\Sigma n/k) = O(nlogn)이라서 된다.

I. Impossible Design

IMO문제라고 한다.

0양옆에 수가 정해지면 조건을 만족하는 수열이 유일하게 결정되는데, 그게 맞는지 보면 된다고 한다. 어렵군.

오후 셋

Baltic OI 2018 2문제, BOI vim을 돌았다.

  1. alternating

전선이 포함 관계를 가지는 구간은 지워버리고, 각 구간에 1개 이하의 전선이 있으면 안되고, 모든 점에서 2개 이상이면 : 전선의 수가 짝수이면 무조건 가능하고, 홀수이면 해봐야 안다.

  1. vim

이상한 DP를 세우면 된다. e를 미리 없애놓고, 한 지점에서 h를 많아야 1번밖에 안한다는 성질을 이용한다.

  1. path

2^5의 Bitmask를 해도 좋고, 각 점마다 k^2가지의 경우를 다 세고, 경로를 세주어도 된다.