fuqinho@競技プログラミング

コンテストやオンラインジャッジで出題されたクイズを頑張って解きます

POJ 1201 - Intervals

概要

整数の組(Ai,Bi,Ci)がN組与えられる。整数の集合Zを「全てのiについてAi以上Bi以下の整数とZの共通要素がCi個以上ある」という条件を満たすように作る時、Zの要素数の最小値を求めよ。(原文)

制約

  • N ≦ 50,000
  • An,Bn,Cn ≦ 50,000

解法

  • 不等式x + d ≧ y が、グラフ上でxからyへコストdの辺を張ることに対応するのを利用して、グラフの最短経路問題に帰着する。
  • d[i]をi以下の整数でZに含まれるものの個数とすると、下記の不等式が成り立つ。
    • d[i+1] ≧ d[i]
    • d[i+1] ≦ d[i] + 1
    • d[Bi] - d[Ai-1] ≧ Ci
  • それぞれ、下記の辺を張ることに対応する
    • i+1からiにコスト0の辺を張る
    • iからi+1にコスト1の辺を張る
    • BiからAi-1にコスト-Ciの辺を張る
  • 制約より、50000から0までの最短経路の-1倍が答えになる。負の辺を含むのでベルマンフォード法で求める。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// Limit: 65536K 2000ms
// Used :  4364K 1282ms
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0;i<(n);++i)

const int INF = 1000000000;
const int MAX_N = 50000;

struct Edge {
  int from, to, cost;
  Edge(int f, int t, int c): from(f), to(t), cost(c) {}
};

// d[50000] から d[0] への最短距離を求める
int bellman_ford(vector<Edge>& edges) {
  // dist[50000]を0とすると、コスト0の辺が全体に貼られてるので、
  // 明らかにdist[i]は0以下にはなる。よって0で初期化する。
  vector<int> dist(MAX_N+1, 0);
  REP(i, MAX_N+1) {
    bool updated = false;
    REP(j, edges.size()) {
      Edge& e = edges[j];
      if (dist[e.to] > dist[e.from] + e.cost) {
        dist[e.to] = dist[e.from] + e.cost;
        updated = true;
      }
    }
    if (!updated) {
      return dist[0];
    }
  }
  return INF;
}

int solve(vector<int>& a, vector<int>& b, vector<int>& c) {
  vector<Edge> edges;
  // d[i+1] - d[i] <= 1 より、iからi+1にコスト1の辺を張る
  for (int i = 0; i < MAX_N; i++) {
    edges.push_back(Edge(i, i+1, 1));
  }
  // d[i+1] >= d[i] より、iからi+1にコスト0の辺を張る
  for (int i = 0; i < MAX_N; i++) {
    edges.push_back(Edge(i+1, i, 0));
  }
  // d[b] - d[a-1] >= c より、bからa-1にコスト-cの辺を張る
  for (int i = 0; i < a.size(); i++) {
    edges.push_back(Edge(b[i], a[i]-1, -c[i]));
  }

  int min_dist = bellman_ford(edges);
  return -min_dist;
}

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

  int n; cin >> n;
  vector<int> a(n), b(n), c(n);
  REP(i, n) cin >> a[i] >> b[i] >> c[i];

  int ans = solve(a, b, c);
  cout << ans << endl;
}

POJ 2429 - GCD & LCM Inverse

概要

最小公倍数(LCM)と最大公約数(GCD)が与えられた時、それを満たす整数のペア(a,b)を求めよ。複数あり得る場合は、a+bが最も小さくなるペアを答えよ。(原文)

制約

  • a, b < 2^63

解法

  • LCM/GCDを素因数分解して、互いに素になるように2つに分けた後でGCDを掛ければ答えの候補になる。
  • が、整数の範囲がめちゃくちゃ大きいので、素因数分解できない。
  • 乱択アルゴリズムを使って確率的に求める。
  • 素数判定はミラー-ラビン素数判定法、合成数であることが分かればポラード・ロー素因数分解法を使って約数を取り出して分解する。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
// Limit: 65536K  2000ms
// Used :   908K   110ms 
#include <iostream>
#include <vector>
#include <map>
#include <cstdlib>
using namespace std;

typedef long long LL;

// return (a * b) % m
LL mod_mult(LL a, LL b, LL m) {
  LL res = 0;
  LL exp = a % m;
  while (b) {
    if (b & 1) {
      res += exp;
      if (res > m) res -= m;
    }
    exp <<= 1;
    if (exp > m) exp -= m;
    b >>= 1;
  }
  return res;
}

// return (a ^ b) % m
LL mod_exp(LL a, LL b, LL m) {
  LL res = 1;
  LL exp = a % m;
  while (b) {
    if (b & 1) res = mod_mult(res, exp, m);
    exp = mod_mult(exp, exp, m);
    b >>= 1;
  }
  return res;
}

// ミラー-ラビン素数判定法
bool miller_rabin(LL n, LL times) {
  if (n < 2) return false;
  if (n == 2) return true;
  if (!(n & 1)) return false;

  LL q = n-1;
  int k = 0;
  while (q % 2 == 0) {
    k++;
    q >>= 1;
  }
  // n - 1 = 2^k * q (qは奇素数)
  // nが素数であれば、下記のいずれかを満たす
  // (i) a^q ≡ 1 (mod n)
  // (ii) a^q, a^2q,..., a^(k-1)q のどれかがnを法として-1
  //
  // なので、逆に(i)(ii)いずれも満たしていない時は合成数と判定できる
  //
  for (int i = 0; i < times; i++) {
    LL a = rand() % (n-1) + 1; // 1,..,n-1からランダムに値を選ぶ
    LL x = mod_exp(a, q, n);
    // (i)をチェック
    if (x == 1) continue;
    // (ii)をチェック
    bool found = false;
    for (int j = 0; j < k; j++) {
      if (x == n-1) {
        found = true;
        break;
      }
      x = mod_mult(x, x, n);
    }
    if (found) continue;

    return false;
  }
  return true;
}

LL get_gcd(LL n, LL m) {
  if (n < m) swap(n, m);
  while (m) {
    swap(n, m);
    m %= n;
  }
  return n;
}

// ポラード・ロー素因数分解法
LL pollard_rho(LL n, int c) {
  LL x = 2;
  LL y = 2;
  LL d = 1;
  while (d == 1) {
    x = mod_mult(x, x, n) + c;
    y = mod_mult(y, y, n) + c;
    y = mod_mult(y, y, n) + c;
    d = get_gcd((x-y >= 0 ? x-y : y-x), n);
  }
  if (d == n) return pollard_rho(n, c+1);
  return d;
}

const int MAX_PRIME = 200000;
vector<int> primes;
vector<bool> is_prime;

// 小さい素数(MAX_PRIMEまで)は先に用意しとく
void init_primes() {
  is_prime = vector<bool>(MAX_PRIME + 1, true);
  is_prime[0] = is_prime[1] = false;
  for (int i = 2; i <= MAX_PRIME; i++) {
    if (is_prime[i]) {
      primes.push_back(i);
      for (int j = i*2; j <= MAX_PRIME; j+=i) {
        is_prime[j] = false;
      }
    }
  }
}

// 素数かどうか判定。大きければミラーラビンを使う
bool isPrime(LL n) {
  if (n <= MAX_PRIME) return is_prime[n];
  else return miller_rabin(n, 20);
}

// 素因数分解する。小さい数は用意した素数で試し割り、大きければポラード・ロー
void factorize(LL n, map<LL, int>& factors) {
  if (isPrime(n)) {
    factors[n]++;
  } else {
    for (int i = 0; i < primes.size(); i++) {
      int p = primes[i];
      while (n % p == 0) {
        factors[p]++;
        n /= p;
      }
    }
    if (n != 1) {
      if (isPrime(n)) {
        factors[n]++;
      } else {
        LL d = pollard_rho(n, 1);
        factorize(d, factors);
        factorize(n/d, factors);
      }
    }
  }
}

pair<LL, LL> solve(LL a, LL b) {
  LL c = b / a;
  map<LL, int> factors;
  factorize(c, factors);

  vector<LL> mult_factors;
  for (map<LL, int>::iterator it = factors.begin(); it != factors.end(); it++) {
    LL mul = 1;
    while (it->second) {
      mul *= it->first;
      it->second --;
    }
    mult_factors.push_back(mul);
  }

  LL best_sum = 1e18, best_x = 1, best_y = c;
  for (int mask = 0; mask < (1 << mult_factors.size()); mask++) {
    LL x = 1;
    for (int i = 0; i < mult_factors.size(); i++) {
      if (mask & (1 << i)) x *= mult_factors[i];
    }
    LL y = c / x;
    if (x < y && x + y < best_sum) {
      best_sum = x + y;
      best_x = x;
      best_y = y;
    }
  }
  return make_pair(best_x * a, best_y * a);
}

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

  init_primes();
  LL a, b;
  while (cin >> a >> b) {
    pair<LL, LL> ans = solve(a, b);
    cout << ans.first << " " << ans.second << endl;
  }
}

POJ 3264 - Balanced Lineup

概要

N個の値H0,H1…とQ個のクエリが与えられる。クエリでは、区間の始点と終点が与えられるので、それぞれのクエリに対して与えられた区間内での最大値と最小値の差を答えよ。(原文)

制約

  • N ≦ 50,000
  • Q ≦ 200,000
  • Hn ≦ 1,000,000

解法

  • 区間の最小値はセグメント木を用いてRange Minimum Queryする。O(Q*logN)
  • 最大値も、符号を逆転することで同じ木を用いて求める。
  • 初期化とか効率悪いけど間に合ったしいっか・・・

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// Used: 3812K   4766MS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef vector<int> VI;
#define REP(i,n) for(int i=0;i<(n);++i)

const int MAX_N = 50000;
const int MAX_Q = 200000;
const int INF = 1000000000;

// data structure for range minimum query
struct SegTree {
  int size;
  vector<int> dat;
  SegTree(int n) {
    size = 1;
    while (size < n) size <<= 1;
    dat = vector<int>(size * 2 - 1, INF);
  }
  void update(int k, int a) {
    k += size-1;
    dat[k] = a;
    while (k > 0) {
      k = (k-1) / 2;
      dat[k] = min(dat[k*2+1], dat[k*2+2]);
    }
  }
  int query(int a, int b) {
    return query(a, b, 0, 0, size);
  }
  int query(int a, int b, int k, int l, int r) {
    if (a >= r || b <= l) return INF;
    if (a <= l && r <= b) return dat[k];
    return min(query(a, b, k*2+1, l, (l+r)/2),
               query(a, b, k*2+2, (l+r)/2, r));
  }
};

void solve(int N, int Q, VI& heights, VI& A, VI& B) {
  SegTree sgMin(N);
  REP(i, N) sgMin.update(i, heights[i]);
  SegTree sgMax(N);
  REP(i, N) sgMax.update(i, -heights[i]);

  REP(i, Q) {
    int minH = sgMin.query(A[i]-1, B[i]);
    int maxH = -sgMax.query(A[i]-1, B[i]);
    cout << maxH - minH << endl;
  }
}

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

  int N, Q; cin >> N >> Q;
  VI heights(N);
  REP(i, N) cin >> heights[i];
  VI A(Q), B(Q);
  REP(i, Q) cin >> A[i] >> B[i];

  solve(N, Q, heights, A, B);
}

CodeSprint Japan - 嫌いな数値

概要

整数Kの約数のうち、N個の整数A1,A2…のいずれの約数でも無いものの個数を求めよ (原文)

制約

  • 1 ≦ N ≦ 1,000,000
  • 1 ≦ K ≦ 10,000,000,000,000
  • 1 ≦ An ≦ 1,000,000,000,000,000,000

解法

  1. a1,a2…それぞれについて、Kとの最大公約数をユークリッドの互除法で求めて、setに突っ込んでいく。O(N*logK)
  2. Kの約数をリストアップする。試し割り+再帰で実装した。
  3. setに詰まってる数(個数は大した数にならない)の約数をリストアップする
  4. 上記(2)の個数から(3)の個数を引く

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

long long gcd(long long a, long long b) {
  if (a < b) swap(a, b);
  while (b) {
    swap(a, b);
    b %= a;
  }
  return a;
}

void expand_factors(long long n, set<long long>& out) {
  if (out.find(n) == out.end()) {
    out.insert(n);
    for (long long i = 2; i * i <= n; i++) {
      if (n % i == 0) {
        expand_factors(i, out);
        expand_factors(n / i, out);
      }
    }
  }
}

int solve(long long K, vector<long long>& A) {
  // A_divs: set of gcd(An, K)
  set<long long> A_divs;
  for (int i = 0; i < A.size(); i++) {
    A_divs.insert(gcd(A[i], K));
  }

  // factors: all factors of K
  set<long long> factors;
  factors.insert(1);
  expand_factors(K, factors);

  // toremove: all factors of A-divs
  set<long long> toremve;
  toremve.insert(1);
  for (set<long long>::iterator it = A_divs.begin(); it != A_divs.end(); it++) {
    expand_factors(*it, toremve);
  }

  return factors.size() - toremve.size();
}

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

  // read input data
  int N;
  long long K;
  cin >> N >> K;
  vector<long long> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }

  // solve and print answer
  int ans = solve(K, A);
  cout << ans << endl;
}

CodeSprint Japan - マトリックス

概要

N個の都市がN-1本の道路によって全域木の形で結ばれている。与えられたK個の都市が互いに切断されている状態になるように、道路を壊したい。その最小コストを求めよ。i番目の道路を壊すコストはTiで与えられる。(原文)

制約

  • 2 ≦ N ≦ 100,000
  • 2 ≦ K ≦ N
  • 1 ≦ Tn ≦ 1,000,000

解法

  • 「壊す道路のコスト最小」⇔「繋がってる道路のコスト最大」なので、クラスカル法を逆向きに用いて道路を繋げて全域木を作る。
  • ただし、K個の都市は互いに繋げてはいけないので、最初から繋がっていたことにしておく。
  • 道全体のコストから繋げた道路のコストを引いたものが求める答え

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Structure for Union-Find
class DisjointSet {
public:
  DisjointSet(int n) {
    rank = vector<int>(n, 0);
    par = vector<int>(n);
    for (int i = 0; i < n; i++) par[i] = i;
  }
  int find(int x) {
    if (x == par[x]) return x;
    else return par[x] = find(par[x]);
  }
  void unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rank[rx] < rank[ry]) par[rx] = ry;
    else {
      par[ry] = rx;
      if (rank[rx] == rank[ry]) rank[rx]++;
    }
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
private:
  vector<int> par;
  vector<int> rank;
};

long long solve(int N, int K, vector<pair<int, pair<int, int> > >& edges,
                vector<int>& machine) {
  DisjointSet ds(N);

  // pre-connect cities with machines to avoid connection at following operation
  for (int i = 1; i < K; i++) {
    ds.unite(machine[0], machine[i]);
  }

  // find max sum of costs for connectable roads by inverted Kruscal's algorithm
  sort(edges.rbegin(), edges.rend());
  long long connected_cost = 0;
  long long total_cost = 0;
  for (int i = 0; i < edges.size(); i++) {
    int cost = edges[i].first;
    int city1 = edges[i].second.first;
    int city2 = edges[i].second.second;
    if (!ds.same(city1, city2)) {
      connected_cost += cost;
      ds.unite(city1, city2);
    }
    total_cost += cost;
  }

  return total_cost - connected_cost;
}

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

  // read input data
  int N, K;
  cin >> N >> K;
  vector<pair<int, pair<int, int> > > edges(N-1);
  for (int i = 0; i < N-1; i++) {
    cin >> edges[i].second.first >> edges[i].second.second >> edges[i].first;
  }
  vector<int> machine(K);
  for (int i = 0; i < K; i++) cin >> machine[i];

  // solve it and print answer
  long long ans = solve(N, K, edges, machine);
  cout << ans << endl;
}