—

layout : wiki title : UCPC 2018 예선 date : 2020-04-07 20:17:47 +0900 lastmod : 2022-03-26 03:37:02 +0900 tags : [algorithm] toc : true public : true

boj15894 - 수학은 체육과목 입니다.

n*4를 출력하면 된다.

    #include <iostream>
    #define scl(n) scanf("%lld", &(n))
    using lld = long long;
    using namespace std;
    int main(){
      lld n;
      scl(n);
      printf("%lld", 4*n);
      return 0;
    }

boj15903 - 카드 합체 놀이

현재 있는 세트에서 가장 작은 2개를 더해서 다음 세트에 넣는 구조이니 priority queue를 사용해서 문제를 해결할 수 있다.

    #include <iostream>
    #include <queue>
    #include <vector>
    #include <algorithm>
    #define sci(n) scanf("%d", &(n))
    using namespace std;
    using lld = long long;

    int main() {
      int n, m;
      sci(n), sci(m);
      priority_queue<int, vector<int>, greater<int> > q;
      for(int i=0;i<n;i++){
        int t;
        sci(t);
        q.push(t);
      }
      for(int i=0;i<m;i++){
        int f = q.top(); q.pop();
        int s = q.top(); q.pop();
        q.push(f+s); q.push(f+s);
      }
      lld result = 0;
      while (!q.empty()) {
        result += q.top(); q.pop();
      }
      printf("%lld", result);
      return 0;
    }

boj15902-Split and Merge

솔직히 해설을 봤는데도 잘 이해 못하고 넘어갔었다. 지금 다시 풀어봐야겠다. (19.09.19)

먼저 생각한건

1/2/1/1/1 이라는 숫자를 2/1/2/1 로 바꾸기 위해서

1/11/1/1/1 을 11/1/11/1 이라고 생각하고

1과 1 사이 공간 마다 /가 있다면 b를 없다면 a를 할당해봤다.

babbb → abbab 로 바꾸는 방법의 경우의 수인데 이때 a가 연속되지 않게 배치하는 과정을 거쳐야한다고 생각할 수 있다.

이를 분할해서 생각해보면

ba→ ab, b→a 로 쪼개서 문제를 볼 수 있다.

사실 이게 뭔 소리인지 전혀 이해하지 못했었는데 ~~지금도 다시 이해하는데 오래걸렸다.~~

babbb 를 abbab 로 바꾸는 예제를 보면 3번째 위치에 있는 b와 5번째 마지막 b는 바뀌지도 않고 변화하는데에도 전혀 영향을 미치지 못하기 때문에 다음과 같이 문제를 재해석할수 있다.

ba 를 ab로 바꾸는 것과 b를 a로 바꾸는 2가지 문제를 동시에 푸는 경우의 수로 볼수 있다.

앞의 문제를 풀기위해 시도하는걸 w_1, 뒤의 문제를 풀기위해 시도하는걸 w_2라고 할때

답은 w_1과 w_2를 배치하는 경우의수 x w_1끼리 바뀌는 수 x w_2끼리 바뀌는 수이다.

이를 수식으로 써보면

$$\frac{\Pi_{i=0}^lD_{L_i} \times \Sigma_{i=0}^l {L_i}}{\Pi_{i=0}^lL_i!}$$

단, l 은 부분문제의 수, L_i는 각 부분문제의 길이, D_i는 길이가 i 인 부분문제의 해결하는 경우의 수

이다.

D_i 는 죽어도 식을 못찾겠어서, 문제 풀이를 참고했다.

이를 곱셈의 역원을 참고해서 코딩하면

    //
    // Created by lmu on 18. 9. 26.
    //

    #define _USE_MATH_DEFINES
    #include <iostream>
    #include <cmath>
    #include <complex>
    #include <vector>
    #include <algorithm>
    #define sci(n) scanf("%d", &(n))
    #define scl(n) scanf("%lld", &(n))
    #define pri(n) printf("%d ", (n))
    #define prl(n) printf("%lld ", (n))
    #define MOD 1000000007LL
    using namespace std;
    typedef long long lld;
    typedef pair<lld, lld> pii;
    typedef vector<lld> vi;
    typedef vector<vi> vvi;
    typedef vector<pii> vpii;

    int main(){
      int L, n, m;
      vi D(6010, 0), f(6010), inv(6010), finv(6010);
      vi a, b, LS;
      int nowLength = 0;
      int ai = 0, bi =0, as = 0, bs = 0;
      int i, j;

      f[0] = f[1] = 1;
      inv[1] = 1;
      finv[0] = finv[1] = 1;
      for (i=2;i<6010;i++) {
        f[i] = (f[i-1]*i) % MOD;
        inv[i] = (MOD - (MOD / i)* inv[MOD%i] % MOD) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
      }

      sci(L), sci(n); a.resize(n);
      for (i=0;i<n;i++) scl(a[i]);
      sci(m); b.resize(m);
      for (i=0;i<m;i++) scl(b[i]);

      while (as < L || bs < L) {
        if (as == bs) {
          as += a[ai++];
          bs += b[bi++];
          nowLength += 2;
        }
        else if (as < bs) {
          as += a[ai++];
          nowLength ++;
        }
        else {
          bs += b[bi++];
          nowLength ++;
        }

        if (as == bs) {
          if (nowLength > 2)
            LS.push_back(nowLength -2);
          nowLength = 0;
        }
      }

      /* Calculate D */
      D[0] = D[1] = 1;
      for (i = 2; i <= 2 * L; i++) {
        for (j = i-2; j >= 0; j-= 2) {
          lld t = D[j] * D[i-1-j] % MOD;
          t = (t * f[i-1]) % MOD;
          t = (t * finv[j]) % MOD;
          t = (t * finv[i - 1 - j]) % MOD;
          D[i] = (D[i] + t) % MOD;
        }
      }

      lld result = 1, s = 0;
      for (auto& l : LS) {
        result = (result * finv[l]) % MOD;
        result = (result * D[l]) % MOD;
        s += l;
      }

      result = (result * f[s]) % MOD;
      printf("%lld %lld\n", s, result);

      return 0;
    }

이다. 겨우겨우 AC받았다.ㅠ

15900- 나무탈출

전형적인 위상정렬 문제다.

    #include <iostream>
    #include <vector>
    #include <queue>
    #define sci(n) scanf("%d", &(n))

    using namespace std;
    using vi = vector<int>;
    using vvi = vector<vi>;

    int main () {
      int N;
      sci(N);
      vi nodes(N+1, 0);
      vi visited(N+1, 0);
      vi indegree(N+1, 0);
      vvi edges(N+1);
      for(int i=1;i<N;i++){
        int a,b;
        sci(a), sci(b);
        edges[a].push_back(b);
        edges[b].push_back(a);
        indegree[a] ++;
        indegree[b] ++;
      }
      queue<int> q;
      int result = 0;
      visited[1] = 1;
      nodes[1] = 0;
      q.push(1);
      while(!q.empty()) {
        int f = q.front(); q.pop();
        for(int i=0;i<edges[f].size();i++){
          if(!visited[edges[f][i]]) {
            visited[edges[f][i]] = 1;
            nodes[edges[f][i]] = nodes[f] + 1;
            q.push({edges[f][i]});
          }
        }
      }
      for(int i=2;i<=N;i++){
        if(indegree[i] == 1) result += nodes[i];
      }

      printf("%s", result % 2 == 1 ? "YES" : "NO");

      return 0;
    }

15901 - 소각로

못품 ㅠ. 뭔문제인지 감도 안잡혀서 나중에 뭔 문제인지 감은 오면 풀어볼려고 풀이도 안봤다.

15899 - 트리와 색깔

세그먼트 트리로 offline query 처리하면 된다.

    #include <iostream>
    #include <vector>
    #include <stack>
    #include <algorithm>
    #define scl(n) scanf("%lld", &(n))
    #define MOD 1000000007LL
    using namespace std;
    using lld = long long;
    using vi = vector<lld>;
    using vvi = vector<vi>;
    using pii = pair<lld, lld>;
    using vpii = vector<pii>;

    lld N, M, C;
    vvi edges;
    lld visited[220000];
    lld idx_tree[550000];
    vpii nodes, query, range;
    lld trav(lld now, lld t) {
      visited[now] ++;
      lld start = t;
      t++;
      for(int i=0;i<edges[now].size();i++){
        if (!visited[edges[now][i]])
          t = trav(edges[now][i], t);
      }
      range[now] = {start, t-1};
      return t;
    }

    void index_inc_up(lld n) {
      if (n==0) return;
      idx_tree[n] ++;
      index_inc_up(n>>1);
    }

    lld index_query(pii q){
      lld res = 0;
      if (q.first > q.second) return 0;
      if (q.first == q.second) return idx_tree[q.first];
      if (q.first % 2 == 1){
        res += idx_tree[q.first];
        q.first++;
      }
      if (q.second % 2 == 0){
        res += idx_tree[q.second];
        q.second--;
      }
      return res + index_query({q.first/2, q.second/2});
    }

    int main() {
      scl(N), scl(M), scl(C);
      range.resize(N+1);
      edges.resize(N+1);
      for(lld i=1;i<=N;i++) {
        lld c;
        scl(c);
        nodes.push_back({i, c});
      }

      for(lld i=1;i<N;i++) {
        lld a, b;
        scl(a), scl(b);
        edges[a].push_back(b);
        edges[b].push_back(a);
      }

      for(lld i=0;i<M;i++){
        lld v, c;
        scl(v), scl(c);
        query.push_back({v, c});
      }

      auto cmp =  [](const pii& a, const pii& b)->bool {
          if (a.second == b.second) return a.first < b.first;
          return a.second < b.second;
        };
      sort(nodes.begin(), nodes.end(), cmp);
      sort(query.begin(), query.end(), cmp);

      lld base;
      for(base=1;base<N;base<<=1);
      trav(1, base);

      lld node_loop = 0;
      lld query_loop = 0;
      lld result = 0;
      for(lld i=1;i<=N;i++){
        printf("range[%lld] : %lld %lld\n", i, range[i].first, range[i].second);
      }
      for(lld i=1;i<=C;i++){
        while (nodes[node_loop].second <= i && node_loop < N) {
          index_inc_up(range[nodes[node_loop].first].first);
          node_loop ++;
        }

        while (query[query_loop].second <= i && query_loop < M) {
          result += (index_query(range[query[query_loop].first])) %MOD;
          result %= MOD;
          query_loop ++;
        }
      }
      printf("%lld", result);
      return 0;
    }

처음으로 index tree를 구성해서 풀어봤다. 역시 주변에 잘하는 사람이 있는게 좋은 것같다.

15904-UCPC는 무엇의 약자일까?

    #include <iostream>
    using namespace std;

    int main() {
      string a;
      getline(cin, a);
      int i=0;
      char data[] ="UCPC";
      for(const auto& c:a){
        if (c==data[i]){
          i++;
        }
      }
      printf("%s",i>=4 ? "I love UCPC " : "I hate UCPC ");
      return 0;
    }

## 15897- 잘못 구현한 에라토스테네스의 체

    #include <iostream>
    #include <cmath>
    #define scl(n) scanf("%lld", &(n))
    using namespace std;
    using lld = long long;
    int main(){
      lld n;
      scl(n);
      lld result = 0;
      int i, j;

      for(i=1, j=0;i<=n;i+=j){
        j = ((n-1)/i)==0 ? 1 : ((n-1)%i)  / ((n-1)/i)+1;
        result += (1+(n-1)/i) * j;
      }

      printf("%lld", result);
      return 0;
    }

흠… 잘 점프하도록 구현했다. 원래는 휴리스틱하게 풀어서 AC을 받았었는데

15898 - 피아의 아틀리에신비한 대회의 연금술사

구현 빡세다 ㅠ


    #include <iostream>
    #define sci(n) scanf("%d", &(n))
    #define scc(n) scanf(" %c", &(n))
    using namespace std;
    struct cell {
      char color;
      int value;
    };
    struct ind {
      cell data[4][4];
    };
    cell now[5][5];
    int n;
    ind inds[10];
    using P_T = cell[5][5];
    P_T cal_ind[10][4][4];
    int visited[10];
    void init_now(){
      for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
          now[i][j].color = 'W';
          now[i][j].value = 0;
        }
      }
    }
    void push_ind(int x, int dir, int pos) {
      for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
          now[i][j].color = cal_ind[x][dir][pos][i][j].color=='W' ? now[i][j].color : cal_ind[x][dir][pos][i][j].color;
          now[i][j].value += cal_ind[x][dir][pos][i][j].value;
          now[i][j].value = now[i][j].value > 0 ? now[i][j].value : 0;
          now[i][j].value = now[i][j].value < 9 ? now[i][j].value : 9;
        }
      }
    }
    void init_cal_ind(){
      for(int i=0;i<n;i++){
        for(int j=0;j<4;j++){
          for(int k=0;k<4;k++){
            for(int l=0;l<5;l++){
              for(int m=0;m<5;m++){
                cal_ind[i][j][k][l][m].color = 'W';
                cal_ind[i][j][k][l][m].value = 0;
              }
            }
          }
        }
      }
    }

    int cal_value() {
      int result = 0;
      for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
          switch(now[i][j].color) {
            case 'R':
              result += 7*now[i][j].value;
              break;
            case 'B':
              result += 5*now[i][j].value;
              break;
            case 'G':
              result += 3*now[i][j].value;
              break;
            case 'Y':
              result += 2*now[i][j].value;
              break;
          }
        }
      }
      return result;
    }
    inline int getr(int r, int c, int dir){
      switch(dir) {
        case 0:
          return r;
        case 1:
          return c;
        case 2:
          return 3-r;
        case 3:
          return 3-c;
      }
      return 0;
    }
    inline int getc(int r, int c, int dir){
      switch(dir) {
        case 0:
          return c;
        case 1:
          return 3-r;
        case 2:
          return 3-c;
        case 3:
          return r;
      }
    }
    int main(){
      sci(n);
      for(int i=0;i<n;i++){
        for(int j=0;j<4;j++){
          for(int k=0;k<4;k++){
            sci(inds[i].data[j][k].value);
          }
        }
        for(int j=0;j<4;j++){
          for(int k=0;k<4;k++){
            scc(inds[i].data[j][k].color);
          }
        }
      }

      init_cal_ind();
      int rs[4] = {0, 0, 1, 1};
      int cs[4] = {0, 1, 0, 1};
      for(int i=0;i<n;i++){
        for(int j=0;j<4;j++){
          for(int k=0;k<4;k++){
            for(int dir=0;dir<4;dir++){
              for(int pos=0;pos<4;pos++){
                cal_ind[i][dir][pos][rs[pos]+ getr(j,k,dir) ][cs[pos]+ getc(j,k,dir)].color = inds[i].data[j][k].color;
                cal_ind[i][dir][pos][rs[pos]+ getr(j,k,dir) ][cs[pos]+ getc(j,k,dir)].value = inds[i].data[j][k].value;
              }
            }
          }
        }
      }

      int result = 0;
      for(int i=0;i<n;i++){
        visited[i] = 1;
        for(int j=0;j<n;j++){
          if (visited[j]) continue;
          visited[j] = 1;
          for(int k=0;k<n;k++){
            if (visited[k]) continue;
            visited[k] = 1;
            for(int id=0;id<4;id++){
              for(int jd=0;jd<4;jd++){
                for(int kd=0;kd<4;kd++){
                  for(int ip=0;ip<4;ip++){
                    for(int jp=0;jp<4;jp++){
                      for(int kp=0;kp<4;kp++){
                        init_now();
                        push_ind(i, id, ip);
                        push_ind(j, jd, jp);
                        push_ind(k, kd, kp);
                        int tmp = cal_value();
                        result = result > tmp ? result : tmp;
                      }
                    }
                  }
                }
              }
            }
            visited[k] = 0;
          }
          visited[j] = 0;
        }
        visited[i] = 0;
      }
      printf("%d", result);
      return 0;
    }