아래와 같이 그래프를 구성한 후 MCMF 를 이용하여 해결한다.

• room[i] = course i 에 필요한 방의 갯수
• 1 <= i <= n 인 i에 대해 ( 0 노드 ) -> ( 2*i-1 노드 ) , 용량 INF, 비용 0 의 간선 추가
• ( 2i-1노드 ) -> ( 2*i 노드 ) , 용량 room[i], 비용 -1 의 간선 추가
• B[i]+clean[i][j] <= A[j] 인 i,j에 대해 ( course i 에 이용된 방이 j에도 이용 가능 ) ( 2i 노드 ) -> ( 2*j-1 노드 ) , 용량 INF, 비용 0 의 간선 추가

• ( 2*i 노드 ) -> ( 2*n+1 노드 ) , 용량 INF, 비용 0 의 간선 추가
  
  

  

  위와 같이 구성된 그래프에서 MCMF 알고리즘을 적용하였을 때 0번 노드에서 2*n+1 번 노드로 향하는 (각각의 용량이 1인) flow를 사용한 방으로 대응 시킬 수 있다.

  위 그래프에서 0 -> 1 -> 2 -> 3 -> 4 -> 5 로 용량 1 인 flow
  = Course 1 과 Course 2 에 사용된 방

  이 로 인해, "방 F 개로 모든 코스를 처리 할 수 있다" 와 "(유량 = F) 인 min cost flow 값이 -sum( room[i] ) 이다" 가 동치임을 알 수 있다.

  이를 이용해 MCMF 알고리즘을 결과 값이 -sum( room[i] ) 가 될 때까지 돌려주면 필요한 최소의 방의 갯수를 확인 할 수 있다.

N<=200 이므로 문제에서 주어진 조건대로 그래프를 구성한 뒤 Floyd 알고리즘을 사용하여 모든 정점쌍에 대한 최단경로를 구할 수 있다. 그 후, 입력받은 각 쿼리에 대해 해당하는 경로를 출력해주면 된다.

이동경로를 나타내는 문자열을 구해놓고 답을 구하려고하면 안된다. n=1000일 경우 문자열의 길이가 2^1000 -1 이기 때문이다. 따라서 문자열을 생성하는 규칙을 찾아낸 뒤, 그에 맞춰서 문자열 S가 속하게 되는지를 판단하여야 한다.

우선 level이 한단계 높아지면서 추가되는 문자열들을 보자.

문제 설명에 따르면 처음에 반시계 방향으로 직각을 만들어내고 이후 번갈아가면서 시계, 반시계, 시계... 방향으로 직각을 만들어낸다고 되어있다.

이를 이용하면, n번째 문자열로부터 n+1번째 문자열을 만드는 방법은 위의 그림처럼, n번째 문자열 사이사이에 L과 R을 번갈아가면서 삽입하면 된다.

이미지가 안나온다고 되는데 잠시 중셉좀...

map를 사용하면 각 word들과 subsequence들을 쉽게 저장할 수 있다. 기억하는 word나 subsequence를 저장할 땐 대소문자를 통일하는것에 유의하도록 하자.
각 단어들 사이에 공백을 한칸씩 두면 어떤 subsequence가 AB C 인지 A BC인지 명확하게 표시할 수 있다.

map(string,int) 를 활용하여 지난 7일간 등장한 단어들의 등장 횟수를 관리하고 top N 쿼리가 주어지면 해당 map 의 모든 원소들을 주어진 조건으로 소팅하여 처리한다.

이전에 알고스팟에 올라온 CIRCLES문제와 유사하다. 그러나 CIRCLES에서는 N개의 원의 합집합의 넓이를 구하는 것으로 끝이지만 이 문제는 N개의 도넛의 합집합의 넓이를 구해야 하기 때문에 조금 더 많은 예외처리를 필요로 한다.

우선 입력으로 주어진 도넛들에 그린 정리를 적용하기 위해 도넛의 바깥쪽 원과 안쪽 원을 두개의 폐곡선으로 떼어낸다. 그래서 바깥쪽 원은 반시계방향으로 적분, 안쪽 원은 시계방향으로 적분하면 원하는 넓이를 구할수 있게 된다.

이제 어려운 부분은 이 폐곡선들에서 적분하지 말아야 하는 구간을 찾는 것이다. 각각의 폐곡선들과 도넛의 위치관계를 정리하면 아래와 같다.

이제 구간을 잘 구했으면 구간에 속하지 않은 부분을 잘 적분하면 답을 구할 수 있다!