UCPC 2021 예선 참여 후기

openingsound, 39dll님과 함께 팀 Wrong answer on으로 참여하였다.

 

나는 B, H 두 문제를 풀었고, 총 다섯 문제를 풀어 64등으로 마감하였다.

 

비대면으로 별다른 준비 없이 시작했지만, 대회 과정이 즐거웠고 나쁘지 않은 결과로 마무리하게 되어 만족스럽다.

 

아래는 내가 작성한 풀이와 구현이다.

 

 

B번 항체 인식

22352번: 항체 인식

처음 상태에서 DSU로 같은 집합끼리 묶는다.

 

다음 상태에서 바뀐 cell이 속한 집합에 대해 모두 같은 수로 바뀌었는지 확인한다.

 

#define sad return 0
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int 
  dir4[2][4] = {{0, -1, 0, 1}, {1, 0, -1, 0}};

int
  R, C,
  pic[33][33],
  pic2[33][33],
  root[1000];
bool
  dup[33][33];
pii
  init = {-1, -1};

// dsu
int dsfind(int tar) {
  if (tar == root[tar]) return tar;
  return root[tar] = dsfind(root[tar]);
}
void dsmerge(int a, int b) {
  a = dsfind(a), b = dsfind(b);
  if (a != b) root[a] = b;
}

// util
bool oob(int r, int c) { return (r < 1 || c < 1 || r > R || c > C); }
int rc2id(int r, int c) { --r; return r*C + c; }
pii id2rc(int i) { --i; return {1 + i/C, 1 + i%C}; }


int main() {
  ios::sync_with_stdio(0), cin.tie(0);

  cin >> R >> C;
  for (int r = 1; r <= R; ++r) for (int c = 1; c <= C; ++c) {
    cin >> pic[r][c];
    root[rc2id(r, c)] = rc2id(r, c);
  }
  for (int r = 1; r <= R; ++r) for (int c = 1; c <= C; ++c) {
    for (int i = 0; i < 4; ++i) {
      int ro = r + dir4[0][i], co = c + dir4[1][i];
      if (oob(ro, co) || pic[r][c] != pic[ro][co]) continue;
      dsmerge(rc2id(r, c), rc2id(ro, co));
    }
  }

  for (int r = 1; r <= R; ++r) {
    for (int c = 1; c <= C; ++c) {
      root[rc2id(r, c)] = dsfind(rc2id(r, c));
      // cout << setw(4) << root[rc2id(r, c)];
    } // cout << endl;
  }

  for (int r = 1; r <= R; ++r) for (int c = 1; c <= C; ++c) {
    cin >> pic2[r][c];
    if (pic2[r][c] != pic[r][c]) {
      if (init.first == -1) init = {r, c};
      else if (dsfind(rc2id(init.first, init.second)) != dsfind(rc2id(r, c))) {
        init.first = -2;
        break;
      }
    }
  }

  if (init.first < 0) {
    cout << (init.first == -1 ? "YES" : "NO");
    sad;
  }

  int f = dsfind(rc2id(init.first, init.second)), good = true;
  for (int r = 1; r <= R; ++r) for (int c = 1; c <= C; ++c) {
    if (dsfind(rc2id(r, c)) == f && pic2[init.first][init.second] != pic2[r][c]) good = false;
  }

  cout << (good ? "YES" : "NO");
  sad;
  
}

 

H번 스키장

22358번: 스키장

단순한 형태의 DAG DP이다.

 

dp[i][k] : 리프트를 k 번 탄 채 스키를 최대한 오래 타고 i 번 지점에 도착했을 때의 시간

 

#define sad return 0
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int
  N, // node
  M, // edge
  K, // lift tickets
  S, T; // base & dest

vector<pll>
  course[100010];
vector<int>
  lift[100010];

ll
  dp[100010][12];

int main() {
  ios::sync_with_stdio(0), cin.tie(0);

  cin >> N >> M >> K >> S >> T;

  for (int i = 0; i <= N; ++i) for (int j = 0; j < 12; ++j) {
    dp[i][j] = -1;
  }
  dp[S][0] = 0;

  for (int i = 0; i < M; ++i) {
    ll u, v, w;
    cin >> u >> v >> w;
    course[u].push_back({w, v});
    lift[v].push_back(u);
  }

  for (int k = 0; k <= K; ++k) {

    // slide down
    for (int i = 1; i < N; ++i) {
      // must start on S
      if (dp[i][k] == -1) continue;

      for (pll &nxt : course[i]) {
        ll w = nxt.first, v = nxt.second;
        dp[v][k] = max(dp[v][k], dp[i][k] + w);
      }
    }

    // climb up
    for (int i = N; i > 1; --i) {
      if (dp[i][k] == -1) continue;
      
      for (int &v : lift[i]) {
        dp[v][k+1] = max(dp[v][k+1], dp[i][k]);
      }
    }

  }

  /*
  for (int k = 0; k <= K; ++k) {
    for (int i = 1; i <= N; ++i) {
      cout << setw(3) << dp[i][k];
    }
    cout << endl;
  }
  */

  ll res = -1;
  for (int i = 0; i <= K; ++i) {
    res = max(res, dp[T][i]);
  }
  cout << res;

  
}