ls-al.me hello, world!

SCPC 2017 R2

생각보다 많은 삽질을 했지만 문제 내용이 알찼다. 대회 직후에 문제와 풀이를 공식적으로 공개하기를 계속해서 바래 본다.

100: Hanoi

하노이 탑 문제에서 주어진 상태가 문제를 해결하는 최적의 경로에서 등장하는지 여부를 구하면 된다. 일반적인 하노이 탑 문제와 다른 점은, A, B, C 세 개의 기둥에서 각각 A에서 B로, B에서 C로, C에서 A로만 디스크를 옮길 수 있다는 점이다. 즉, A기둥에서 C기둥으로 디스크를 옮기기 위해서는 B기둥을 한번 거쳐야 한다.

하노이 탑 문제를 푸는 것은 어렵지 않은데, 일반적인 풀이 - 개의 디스크를 A에서 B로 옮기기 위해 개의 디스크를 A에서 C로 옮기고, 번 디스크를 A에서 B로 옮기고, 개의 디스크를 다시 C에서 B로 옮기는 - 를 그대로 적용하되 필요한 경우 다른 디스크를 거쳐가도록 하면 되며 이것이 유일한 최적의 방법임을 증명하기는 어렵지 않다. 여기서 주어진 상태가 등장하는지를 구하는 것 역시 가장 아래 디스크부터 시작해 현재 디스크 무더기를 옮기고 있는 출발지와 도착지를 유추해가며 판단하면 된다. 주어진 상태가 풀이 과정에서 등장하지 않는 유일한 경우는 디스크가 경유할 필요가 없는 기둥에서 발견되는 경우이다.

#include <stdio.h>

const int N = 1000000 + 10;

char str[N];

int main() {
  int tc;
  scanf("%d", &tc);
  for (int t = 1; t <= tc; t++) {
    int n;
    scanf("%d", &n);
    scanf("%s", str);
    int from = 0, to = 1, i;
    for (i = n - 1; 0 <= i; i--) {
      int now = str[i] - 'A';
      if ((from + 1) % 3 == to) {
        if (now == from) {
          from = now;
          to = (now + 2) % 3;
        } else if (now == (from + 1) % 3) {
          from = (now + 1) % 3;
          to = now;
        } else {
          break;
        }
      } else if ((from + 2) % 3 == to) {
        if (now == from) {
          from = now;
          to = (now + 2) % 3;
        } else if (now == (from + 1) % 3) {
          from = (now + 1) % 3;
          to = (now + 2) % 3;
        }
        else {
          from = (now + 1) % 3;
          to = now;
        }
      } else {
        break;
      }
    }
    printf("Case #%d\n", t);
    if (0 <= i) {
      printf("NO\n");
    } else {
      printf("YES\n");
    }
  }
  return 0;
}

150: 오래달리기

명의 선수마다 속도, 트랙의 길이, 출발 위치가 주어질 때 모든 선수가 원형 트랙의 출발점에 도착하는 가장 빠른 자연수 시간 를 구하면 된다.

선수 의 속도, 트랙의 길이, 출발 위치를 각각 , , 라고 할 때, 모든 에 대해 다음이 성립한다:

가 서로소라고 가정하고 이를 조금 변형하면:

여기서 를 제외한 모든 항이 주어지므로 중국인의 나머지 정리를 활용해 가장 작은 자연수 를 구할 수 있다.

주의해야 할 점이 크게 두 가지가 있는데, 첫째는 모든 가 0인 경우로 들의 최소공배수를 출력해야 하는 점이며, 둘째는 주어진 중 서로소가 아닌 쌍이 있을 경우 이를 정규화해야 한다는 점이다. 후자를 해결하면서 많은 실수를 했는데, 결국 모든 를 소인수분해했다.

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

const int L = 1000;

long long nmod(long long x, long long m) {
  if (x < 0) {
    x += ((-x) / m) * m + m;
  }
  return x % m;
}

pair<long long, long long> egcd(long long a, long long b) {
  if (a == 0) {
    return make_pair(0, 1);
  }
  pair<long long, long long> t = egcd(b % a, a);
  return make_pair(t.second - (b / a) * t.first, t.first);
}

long long modinv(long long a, long long m) {
  return nmod(egcd(a, m).first, m);
}

long long crt(vector<long long> &q, vector<long long> &r) {
  long long c = 1;
  for (auto x : r) {
    c *= x;
  }
  long long x = 0;
  for (auto qt = q.begin(), rt = r.begin(); qt != q.end() && rt != r.end(); qt++, rt++) {
    long long a = nmod((*qt) * modinv(c / (*rt), *rt), *rt);
    x = nmod(x + a * (c / (*rt)), c);
  }
  return x;
}

long long gcd(long long a, long long b) {
  if (a == 0) {
    return b;
  }
  return gcd(b % a, a);
}

int main() {
  vector<long long> primes;
  for (int i = 2; i <= L; i++) {
    int j;
    for (j = 0; j < primes.size() && i % primes[j] != 0; j++);
    if (j == primes.size()) {
      primes.push_back(i);
    }
  }
  int tc;
  scanf("%d", &tc);
  for (int t = 1; t <= tc; t++) {
    int n;
    scanf("%d", &n);
    map<long long, pair<long long, long long> > cnt;
    for (int i = 0; i < n; i++) {
      long long s, l, d;
      scanf("%lld %lld %lld", &s, &l, &d);
      long long g = gcd(gcd(l, d), s);
      s /= g, l /= g, d /= g;
      long long q = nmod(modinv(s, l) * (l - d), l);
      for (int p : primes) {
        long long j;
        for (j = 1; l % p == 0; l /= p, j *= p);
        if (j == 1) {
          continue;
        }
        if (cnt.find(p) == cnt.end() || cnt[p].first < j) {
          cnt[p] = make_pair(j, q % j);
        }
      }
    }
    vector<long long> q, r;
    for (auto &kv : cnt) {
      r.push_back(kv.second.first);
      q.push_back(kv.second.second);
    }
    long long v = crt(q, r);
    if (v == 0) {
      v = 1;
      for (auto x : r) {
        v *= x;
      }
    }
    printf("Case #%d\n", t);
    printf("%lld\n", v);
  }
  return 0;
}

200: Divisor

주어진 수열에 대해, 수열의 일부 구간과 자연수 가 주어질 때 의 약수들 중 수열의 수를 하나도 나누지 못하는 수의 개수를 구하는 질의가 여럿 주어진다. 정리하자면 각 질의마다 주어진 수의 약수의 집합에 주어진 구간의 수들의 약수들의 합집합을 뺀 차집합의 크기를 구하면 된다. 시간제한이 10초로 매우 넉넉하다.

풀이는 어렵지 않지만 대회 중 생각해내지 못했다. 주어진 수열에 대해 binary indexed tree를 구성하되, 각 노드가 해당 구간의 수들의 약수의 합집합을 나타내는 일종의 merge sort tree를 구성하면 된다. 다만 이 방법으로 시간은 아슬아슬하게나마 주어진 제한을 만족시킬 수 있으나 메모리가 부족할 수 있겠다는 생각을 하는데, 약수의 개수가 흔히 생각하는 것보다는 적겠지만 그 합집합을 여러차례 중복해서 유지해야 하는 만큼 결코 넉넉하지는 않을 것 같다.

250: 중심

주어진 가중치 트리 에서 의 부분트리 에 대해 에 속하는 정점에서 에 속하지 않는 정점까지의 최단거리의 최댓값을 최소화하도록 을 고르려고 한다. 쉽게 말해서 를 적절히 잘 커버하는 개의 정점을 잘 골라내서 가장 먼 정점까지의 거리를 최소화하라는 것인데, 이 연결된 부분트리리를 구성해야 하므로 의 중심에 가까운 어딘가에 위치해야 한다는 점을 유추할 수 있다. 이러한 부분트리 이라고 부른다고 한다.

다음 lemma를 이용하면 문제를 쉽게 해결할 수 있다:

증명은 귀류법을 이용하여 을 포함하지 않는 에서 가장 먼 정점까지의 거리가 에서 가장 먼 정점까지의 거리보다 멀거나 같음을 보이면 된다. 을 포함하도록 을 잡는 쪽이 항상 손해가 아니기 때문에 모든 에 대해 을 포함하는 이 항상 존재한다.

답을 계산할때는 먼저 을 구하고, 해당 정점을 기준으로 가장 먼 정점까지의 거리가 가장 먼 개의 정점을 추가로 선택하면 된다. 에 속하는 정점을 하나 정하고 시작하기 때문에 각 정점에서 가장 먼 정점까지의 거리를 만에 구할 수 있다.

다만 가 최대 이기 때문에 재귀함수를 이용해 DFS를 수행하면 stack overflow가 발생한다. 처음부터 이를 염두에 두지 못한 바람에 재귀함수를 사용하지 않는 방향으로 DFS를 구현하도록 수정하느라 코드의 가독성이 대폭 희생되었다.

#include <stdio.h>
#include <algorithm>
#include <list>
#include <tuple>
#include <stack>

const int N = 100000 + 10;

using namespace std;

long long dist[N];
long long rdist[N];
long long mdist[N];

list<pair<int, long long> > lnk[N];

void calc_dist(int now, int par) {
  stack<tuple<int, int, list<pair<int, long long> > ::iterator> > stk;
  stk.push(make_tuple(now, par, lnk[now].begin()));
  while (!stk.empty()) {
    auto &ctx = stk.top();
    int now = get<0>(ctx);
    list<pair<int, long long> > ::iterator &it = get<2>(ctx);
    if (it == lnk[now].end()) {
      dist[now] = 0;
      for (auto p : lnk[now]) {
        if (p.first == get<1>(ctx)) {
          continue;
        }
        rdist[p.first] += p.second;
        dist[now] = max(dist[now], rdist[p.first]);
      }
      rdist[now] = dist[now];
      stk.pop();
      continue;
    }
    if (it->first == get<1>(ctx)) {
      it++;
      continue;
    }
    stk.push(make_tuple(it->first, now, lnk[it->first].begin()));
    it++;
  }
}

void aggr_dist(int now, int par, long long pdist) {
  stack<tuple<int, int, long long, int, long long, int, list<pair<int, long long> > ::iterator> > stk;
  stk.push(make_tuple(now, par, pdist, now, 0, -1, lnk[now].begin()));
  while (!stk.empty()) {
    auto &ctx = stk.top();
    int now = get<0>(ctx);
    long long &v1 = get<2>(ctx), &v2 = get<4>(ctx);
    int &i1 = get<3>(ctx), &i2 = get<5>(ctx);
    list<pair<int, long long> > ::iterator &it = get<6>(ctx);
    if (it == lnk[now].begin()) {
      mdist[now] = max(dist[now], get<2>(ctx));
      for (auto p : lnk[now]) {
        if (p.first == get<1>(ctx)) {
          continue;
        }
        long long v = dist[p.first] + p.second;
        if (v1 < v) {
          v2 = v1;
          i2 = i1;
          v1 = v;
          i1 = p.first;
        } else if (i2 == -1 || v2 < v) {
          v2 = v;
          i2 = p.first;
        }
      }
    }
    if (it == lnk[now].end()) {
      stk.pop();
      continue;
    }
    if (it->first == get<1>(ctx)) {
      it++;
      continue;
    }
    if (i1 == it->first) {
      stk.push(make_tuple(it->first, now, v2 + it->second, now, 0, -1, lnk[it->first].begin()));
    } else {
      stk.push(make_tuple(it->first, now, v1 + it->second, now, 0, -1, lnk[it->first].begin()));
    }
    it++;
  }
}

int main() {
  int tc;
  scanf("%d", &tc);
  for (int t = 1; t <= tc; t++) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
      lnk[i].clear();
    }
    for (int i = 1; i < n; i++) {
      int x, y;
      long long w;
      scanf("%d %d %lld", &x, &y, &w);
      x--, y--;
      lnk[x].push_back(make_pair(y, w));
      lnk[y].push_back(make_pair(x, w));
    }
    calc_dist(0, -1);
    aggr_dist(0, -1, 0);
    int mi = 0;
    for (int i = 1; i < n; i++) {
      if (mdist[i] < mdist[mi]) {
        mi = i;
      }
    }
    calc_dist(mi, -1);
    sort(rdist, rdist + n, greater<long long>());
    int p;
    scanf("%d", &p);
    rdist[n] = 0;
    printf("Case #%d\n", t);
    printf("%lld\n", rdist[p]);
  }
  return 0;
}

300: 자석

1차원 공간에 여러 막대들이 겹쳐 있을 때, 모든 막대에 대해 자기 자신 혹은 겹쳐있는 막대 중 최소 하나 이상이 포함되도록 최소한의 막대를 고르면 된다. 겹쳐 있는 막대를 그래프로 표현하면 Mincost-Maxflow 문제가 되지만 막대가 최대 개 존재하기 때문에 제한시간을 초과하게 된다. 막대들이 1차원 공간에 있음을 이용해 적절한 DP를 수행하면 된다고 한다.