[5/29] IOI2011 Day1

양방향 그래프로 보고, 한 간선을 이용하면 다음에 탈 간선은 자동으로 정해진다.

그러므로 간선을 정점으로 하는 그래프를 만들면, 각 정점의 outdegree는 이다.

따라서 이 그래프에는 사이클이 개만 있을 수 있다. 시작점은 처음 그래프에서 각 정점에 연결된 길들 중 가장 아름다운 길들이다.

P와 연결된 길 중 가장 아름다운 길을 라고 하자.

그러면 도착점은 를 통해 로 들어오는 경우, 다른 길로 들어오는 경우가 있다. 그런데 다른 길로 들어올 경우 무조건 로 나가게 된다. 따라서 로 나가는 경우 하나로 묶어 처리하면, 두 개의 도착점만 처리하면 된다. 두 개의 도착점을 따로 처리하자.

1) 도착점이 사이클에 속하지 않는 경우

어디서 출발하던 거리는 고정이다. 거리는  이하이므로 배열에 담아두면 쿼리당 에 처리할 수 있다.

2) 도착점이 사이클에 속하는 경우

사이클의 길이를 라고 하면, 최단거리가 (는 음이 아닌 정수)인 시작점들은 모두 가능하다.

로 나눈 나머지에 따라서 따로 전처리를 해두면, 에 쿼리를 구할 수 있다.

시간복잡도는 .

무조건 논 위에 쌀 창고가 있는 최적해가 존재한다. 논 사이에 창고가 있다면, 옆의 논으로 옮기는 것이 이득이다.

번 논부터 번 논까지 사용한다면, 창고가 번 논에 있을 때 최적해이다.

를 고정하고, 가 답이 될 수 있는지 확인하는 것은 prefix sum을 전처리해두면 에 구해진다.

에서 이 가능한지 확인하고, 가능하다면 를 1 늘린다. 불가능하다면 를 1 늘린다. 이것을 반복하면 에 의 최대값을 구할 수 있다.

이것이 가능한건 가 고정되었을 때 가 가능하다면, 보다 작은 값도 무조건 가능하기 때문이다.

시간복잡도는 .