업다운 디펜스 #2

이전 글 에서 이어집니다.

[Platinum 4] BOJ 1505 - 불 켜기 [+] 18:12

BOJ 1505

$dp[y][bit_p][bit_c]=$ 현재 $y$ row에 있고 이전 행의 비트가 $bit_p$ 이고 현재 행의 비트가 $bit_c$ 일 때 끝까지 모두 켜기 위해 더 필요한 최솟값

이라고 정의하면 된다.

$O(n2^m2^m2^m)$ 이 될 것 같지만 백트랙킹이 적절히 되어 시간안에 돈다.

DP를 안 쓰고 푸는게 정해인것같다.

십자가로 조작되는 문제는 첫 행을 결정하면 그 다음 행이 항상 결정되므로 브루트포스가 됨은 알고 있었는데 인접한 9칸이 모두 조작되는 문제는 처음본것같아 그냥 DP로 풀었다.

정해는 동일하게 첫 행은 모두 브루트포스로 경우의 수를 따져보고 두 번째 행부터는 $y-1,x-1$ 칸의 전구가 꺼져있다면 항상 $y,x$ 칸을 조작하는 것으로 가능한지 검사하는 방식으로 풀리는 것 같다.

const int dy[] = {-1, -1, 0, 1, 1, 1, 0, -1, 0}, dx[] = {0, 1, 1, 1, 0, -1, -1, -1, 0}, op[] = {4, 5, 6, 7, 0, 1, 2, 3};  
int dp[8][256][256];  
const int inf = 1e9;  
void solve() {  
   memset(dp, -1, sizeof dp);  
   int Y, X;  
   cin >> Y >> X;  
   vs b(Y);  
   fv(b);  
  
   vi row_bit(Y);  
   for (int y = 0; y < Y; y++) {  
      for (int x = 0; x < X; x++) {  
         if (b[y][x] == '*') row_bit[y] |= (1 << x);  
      }  
   }  
  
   debug(row_bit);  
   // 현재 row, 이전 row의 상태, 현재 row의 상태  
   function<int(int, int, int)> fn = [&](int y, int b, int c) -> int {  
      debug(y, b, c);  
      if (y == Y) {  
         if (b == (1 << X) - 1) return 0;  
         return inf;  
      }  
      int &ret = dp[y][b][c];  
      if (~ret) return ret;  
      ret = inf;  
  
      for (int mask = 0; mask < (1 << X); mask++) {  
         int prev = b, current = c, nxt = y == Y - 1 ? 0 : row_bit[y + 1];  
  
         int add = 0;  
         for (int x = 0; x < X; x++) {  
            if (mask & (1 << x)) {  
               add++;  
               for (int d = 0; d < 9; d++) {  
                  int ny = y + dy[d];  
                  int nx = x + dx[d];  
                  if (ny >= 0 && ny < Y && nx >= 0 && nx < X) {  
                     if (ny == y - 1) {  
                        prev ^= 1 << nx;  
                     } else if (ny == y) {  
                        current ^= 1 << nx;  
                     } else {  
                        nxt ^= 1 << nx;  
                     }  
                  }  
               }  
            }  
         }  
  
         if (prev == (1 << X) - 1 || y == 0) {  
            mina(ret, add + fn(y + 1, current, nxt));  
         }  
      }  
  
      return ret;  
   };  
   int ret = fn(0, 0, row_bit[0]);  
   if (ret == inf) cout << -1;  
   else cout << ret;  
}

[Platinum 3] BOJ 14398 - 피타고라스 수 [+] 14:50

BOJ 14398

지문을 읽고 이게 뭔소리지 하고 질문 게시판에 들어가보니 역시 부실한 설명에 대한 글이 있었다.

대충 문제를 이해하고 적절히 풀었다.

Proof by AC인데, 대략 트리 DP로 풀었다.

$a^2+b^2=c^2$ 이 되는 $(a,b)$ 쌍을 모두 간선으로 이어두고 돌리면 된다.

정해에 가까운 풀이는 홀짝을 나눠서 이분매칭을 하는 것 같다.

난이도 기여의 다른 해설을 참고하자면,

$2 \nmid a,b$ 라면 $a^2+b^2$는 짝수이며 $4$의 배수가 아니기 때문에 $c$가 존재하지 않는다. $4$의 배수가 아니라는 것은 $c$가 $2$를 가지고 있을 수 없는데 그럼 짝수가 된다는 것에 모순이기 때문이다.

$\because (2n+1)^2=4n^2+4n+1 \equiv 1 \pmod 4$ 이기 때문에 $a^2+b^2 \equiv 2 \pmod 4$ 가 되기 때문이다.

$2 \mid a,b$ 라면 $gcd(a,b) > 1$ 이여서 불가능하다.

따라서 모든 $a_i$를 홀짝으로 나누고 이분매칭을 돌리면 된다.

void solve() {  
   int n;  
   cin >> n;  
   vi a(n);  
   fv(a);  
   sort(all(a));  
   vi cnt(1000001);  
   for (int i: a)cnt[i]++;  
   debug(a);  
   auto is_sq = [&](int x) {  
      int l = 0, r = 1e8, ret = -1;  
      while (l <= r) {  
         int m = l + r >> 1;  
         if (m * m <= x) ret = m, l = m + 1;  
         else r = m - 1;  
      }  
      return ret * ret == x;  
   };  
   vector<array<int, 3>> cand;  
   for (int i = 0; i < n; i++) {  
      for (int j = i + 1; j < n; j++) {  
         if (gcd(a[i], a[j]) != 1) continue;  
         int c = a[i] * a[i] + a[j] * a[j];  
         if (!is_sq(c)) continue;  
         cand.pb({c, a[i], a[j]});  
      }  
   }  
   uniq(cand);  
   debug(cand);  
   if (!sz(cand)) {  
      cout << 0;  
      return;  
   }  
   // 3 6 , 9 + 121  
  
   int ans = 0;  
  
   vvi edges(1000001);  
   for (auto &[c, x, y]: cand) {  
      edges[x].pb(y);  
      edges[y].pb(x);  
   }  
   vi vis(1000001);  
   function<int(int, int)> fn = [&](int cur, int p) -> int {  
      int ret = cnt[cur];  
      vis[cur] = 1;  
  
      int cc = 0;  
      for (int to: edges[cur]) {  
         if (to != p) {  
            cc += fn(to, cur);  
         }  
      }  
      int created = min(cnt[cur], cc);  
      ans += created;  
      ret -= created;  
  
      return ret;  
   };  
   for (int i = 1; i <= 1000000; i++) {  
      if (sz(edges[i]) && !vis[i]) {  
         fn(i, -1);  
      }  
   }  
   cout << ans;  
}