아래와 같이 그래프를 구성한 후 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을 번갈아가면서 삽입하면 된다.

그렇다면 S가 부분문자열이 된다고 판단할까?
위의 문자열 생성하는 방식을 대충 보기좋게 만들면 아래와 같다.

문자열을 트리형태로 구성을 시킬 수 있다는 이야기다. 이제 전체 문자열이 트리형태로 생겼다고 치고, S가 이 트리 안으로 들어오는지를 판단해보자.
위의 생성된 트리의 규칙을 살펴보면 다음과 같다.

1. k level 에서 L 과 R 사이에 반드시 k-1 level의 문자가 들어간다. (1<k<=n)
2. k level 에 해당하는 문자들은 왼쪽에서부터 L과 R이 번갈아가면서 등장해야한다.
3. 홀수 번 째 문자는 항상 n level의 문자이다.

4. 1 level의 문자는 L이다.

   S가 위의 규칙대로 생성된 문자열의 부분문자열이 되어야 한다. 그러기 위해 S에서 leap node(n level) 에 해당하는 문자가 무엇인지 결정을 하고, 규칙 1에 의거해서 level을 하나씩 줄여나가면서, 해당 level 에 속해있는 문자들이 누구누구인지를 결정해나가서, 마지막 1 level 에 해당하는 문자가 L이 나오면 된다. n level이 될 수 있는 경우는 2가지 뿐이고, k level 문자들이 결정되면 k-1 level의 문자도 O(|S|)만에 결정되므로 시간안에 답을 구해낼 수 있다.

   간단히 예를 들어보자. n = 4 일 때 S = LLRLLRR 이 속해있는지를 판단해보자.

   S = L L R L L R R
   B = X X X X X X X
   ↓ 4 level 결정
   S = L L R L L R R
   B = 4 X 4 X 4 X 4
   ↓ 3 level 결정
   S = L L R L L R R
   B = 4 3 4 X 4 3 4
   ↓ 2 level 결정
   S = L L R L L R R
   B = 4 3 4 2 4 3 4
   ↓ 1 level 결정
   S = L L R L L R R
   B = 4 3 4 2 4 3 4

   1 level에 L과 R 둘 다 들어올 수 있는 상황이므로 L이 들어온다고 치면 부분문자열이 된다고 말할 수 있게된다.

   이제 n = 4 일 때 S = RRR 이 속해있는지를 판단해보자.

   S = R R R
   B = X X X
   ↓ 4 level 결정
   S = R R R
   B = 4 X 4 <규칙 2 위반)
   ↓ 4 level 다시 결정
   S = R R R
   B = X 4 X
   ↓ 3 level 결정
   S = R R R
   B = 3 4 X (규칙 1에 의해)
   ↓ 2 level 결정
   S = R R R
   B = 3 4 X
   (왼쪽 어딘가에 level 2에 해당하는 문자가 있을 것이다. 그 문자가 L이라고 가정을 한 채)
   ↓ 1 level 결정
   S = R R R
   B = 3 4 1

   L이 되던 R이 되던 상관없는 문자는 L로 결정하는게 포인트
   n level이 될 수 있는 2가지 경우에 대해
   첫 번 째 경우는 4 level에 해당하는 문자열이 L R L R 형태로 번갈아가면서 나타나지 않았기 때문에 실패했다.
   마지막에 1 level에 해당하는 문자가 R로 결정됐는데, 1 level의 문자는 무조건 L이여야하므로 실패. 두 경우 모두답이 안된다고 말하고 있으므로, S는 부분문자열이 아니라고 말할 수 있다.

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

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

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

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

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

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