UCPC 2018 예선

created : 2020-04-07T11:17:47+00:00
modified : 2020-04-20T14:23:27+00:00

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

boj15903 - 카드 합체 놀이

    #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

먼저 생각한건

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;
    }

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