USACO 2016 February Gold 업솔빙

한동안 유사코 골드 라운드 후기가 안 올라온 것은, 세 문제 다 푼 라운드가 없어서(...)이다.

solved.ac 기준으로 플5/플5/골1로 이루어진 실력에 적합한(?) 세트를 찾아서 오랜만에 다 풀어보았다.

이번 라운드는 공식 솔루션을 거의 보지 않았다. 공식 테케는 좀 참고했지만 꽤나 뿌듯하다 >__<!

 

공식 테스트케이스와 영어로 된 솔루션은 이 링크에 있다.

http://www.usaco.org/index.php?page=feb16results

---

#11993 Circular Barn (Gold)

와 자력플5!! 간단한 풀이를 적으려고 하다가 어느 순간 길어져서 게시글을 분리했다.

---

#11994 Circular Barn Revisited

dp~ 제한이 작으니 적당히 DP하면 된다.

dp [N: i번 방에서 시작해서] [N: 마지막 문이 j에 있고] [K: 지금까지 k개의 문을 배치함] 이렇게 테이블을 잡고

각 칸을 O(N)에 채워주면 된다. (총 시간복잡도 N^3K)

k, i, j, nxt door 순으로 반복문을 돌리자. upd라는 변수는 j+1부터 k까지 cost를 의미한다.

for (int k = 0; k < K; k++)
  for (int i = 1; i <= N; i++)
    for (int j = i - 1; j < i + N; j++) {
      ll cnt = 0, upd = 0;
      for (int n = j + 1; n < i + N; n++) {
        upd += cnt;
        cnt += ipt[n];
        dp[i][n][k + 1] = min(dp[i][n][k + 1], dp[i][j][k] + upd);
      }
    }

+ dp table은 무한대로 초기화하고 dp[i][i-1][0] 만 0으로 초기화하자.

---

#11995 Fenced In (Gold)

재밌는 문제였다. 보자마자 MST 기본형이라는 걸 깨달을 수 있는데 구현이 좀 막막할 수도 있다. (생각보다 간단하다.)

문제는 맞왜TLE인데, 보통 그래프에서 MST를 짜듯이 priority_queue<edge> E; 와 같은 자료구조를 이용해서 간선을 정렬해주면 NM log(NM) 이라서 8700만 정도의 연산횟수를 가지고, NMlogNM만 해야하는 건 아니기에, 시간초과를 받았다.

간선의 길이에 따라 양끝 정점이 어떤 것이 될 수 있는지 판단할 수 있으므로, 아래와 같은 동작을 구현하면 된다.

 

1. y방향 길이와 x방향 길이를 정렬
2. 병합정렬(Merge Sort)하듯이 둘을 적당히 돌아가며 작은 간선을 찾아, 해당하는 정점들을 Union

---

번외로, Fenced In은 Platinum 버전도 있는데, 다른 조건은 같은데 N과 M의 제한이 25,000으로 늘어난다.

Union Find Tree와 관련된 코드를 싹 다 지우고 두 줄 추가해주면 맞는다.

간단히 적자면, Gold에서 해당하는 정점들을 Union 하는 부분을 다음과 같이 바꾸면 된다.

1. 사이클이 생겼는지에 대한 여부를 이미 병합한 x축의 개수와 y축의 개수로 판단
2. 사이클이 생기지 않았다면, 정점을 다 Union
3. 사이클이 생겼다면, 다른 축에서 병합되어 버린 개수를 고려하여 Union

Union연산을 Union Find Tree를 쓰지 않아도, 합쳐야 하는 정점의 개수 * 간선의 길이로 O(1)에 가능하다.

 

자세한 건 코드를 보자.

 while (cy <= n + 1 || cx <= m + 1) {
   if (cy <= n + 1 && (cx == m + 2 || yl[cy].val <= xl[cx].val)) {
     if (cy == 1 || cx <= 2) ans += yl[cy].val * m;
     else ans += yl[cy].val * (m - (cx - 2 LL));
     cy++;
   }
   if (cx <= m + 1 && (cy == n + 2 || xl[cx].val <= yl[cy].val)) {
     if (cx == 1 || cy <= 2) ans += xl[cx].val * n;
     else ans += xl[cx].val * (n - (cy - 2 LL));
     cx++;
   }
 }