fuqinho@競技プログラミング

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

POJ 2836 - Rectangular Covering

概要

平面座標上の点がn個与えられる。いくつかの長方形でこれらの点を全て覆う時、長方形の面積の合計は最小でいくつか。長方形の各辺は座標軸と並行でなければならず、また1辺は1以上の整数でなければならない。(原文)

制約

  • n ≦ 15

解法

  • まず、候補になる長方形をリストアップする。n個の点から2点選んで、その2点で作られる長方形にどの点がカバーされているかをチェックする。
  • リストアップした長方形を組み合わせて全点をカバーする組み合わせを作る。
  • dp[S]を、集合Sに含まれる点がカバーされている場合の最小の合計面積として、ビットDPする。

コード

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
// Limit: 65536K  1000ms
// Used :   816K   157ms
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

const int INF = 1000000000;

struct Rect {
  int covering, area;
  Rect(int c, int a): covering(c), area(a) {}
};

bool isCovered(int p, int p1, int p2, vector<int>& x, vector<int>& y) {
  return (x[p]-x[p1])*(x[p]-x[p2]) <= 0 &&
         (y[p]-y[p1])*(y[p]-y[p2]) <= 0;
}

int solve(int n, vector<int>& x, vector<int>& y) {
  // list up rectangles
  vector<Rect> rectangles;
  for (int i = 0; i < n; i++) {
    for (int j = i+1; j < n; j++) {

      // make rectangle by i-th point and j-th point,
      // and check covering points and its area (width and height must not be 0)
      int area = max(1, abs(x[i]-x[j])) * max(1, abs(y[i]-y[j]));
      Rect rect = Rect((1 << i)|(1 << j), area);
      for (int k = 0; k < n; k++) {
        if (isCovered(k, i, j, x, y)) rect.covering |= (1 << k);
      }
      rectangles.push_back(rect);
    }
  }

  // DP for state S: which point are covered
  // dp[S]: minimum area to cover points in S
  vector<int> dp(1 << n, INF);
  dp[0] = 0;
  for (int i = 0; i < rectangles.size(); i++) {
    int covering = rectangles[i].covering;
    for (int s = 0; s < (1 << n); s++) {
      if (dp[s] != INF && (s|covering) != s) {
        dp[s|covering] = min(dp[s|covering], dp[s] + rectangles[i].area);
      }
    }
  }
  return dp[(1 << n) - 1];
}

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

  while (true) {
    int n; cin >> n;
    if (n == 0) break;

    vector<int> x(n), y(n);
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];

    int ans = solve(n, x, y);
    cout << ans << endl;
  }
}

POJ 3254 - Corn Field

概要

M行N列のマス目から、いくつかのマス目を選ぶ。隣り合うマス目を選ぶ事はできない。また、いくつかのマス目は選べないようになっている。マス目の選び方は何通りあるか。(原文)

制約

  • M ≦ 12
  • N ≦ 12

解法

  • dp(i, S)を、i行目まで埋めていて、i行目で選択したマス目が集合Sになっている時のパターン数としてビットDPする。
  • メモリ足りないのでiは偶数行と奇数行の2通り用意して使いまわす。

コード

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
// Limit: 65536K  2000ms
// Used :   712K    16ms
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

const int MOD = 100000000;

int solve(int M, int N, vector<int>& fertile) {
  vector<vector<int> > dp(2, vector<int>(1 << N));
  dp[0][0] = 1;

  for (int i = 0; i < M; i++) {
    for (int j = 0; j < (1 << N); j++) {
      for (int k = 0; k < (1 << N); k++) {
        if (j & k) continue; // check vertical neighbor
        if (k & (k << 1)) continue; // check horizontal neighbor
        if (k & ~fertile[i]) continue; // check fertility

        dp[(i+1)&1][k] += dp[i&1][j];
        dp[(i+1)&1][k] %= MOD;
      }
    }
    fill(dp[i&1].begin(), dp[i&1].end(), 0);
  }

  return accumulate(dp[M&1].begin(), dp[M&1].end(), 0LL) % MOD;
}

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

  int M, N; cin >> M >> N;
  vector<int> fertile(M);
  for (int i = 0; i < M; i++) {
    for (int j = 0; j < N; j++) {
      int f; cin >> f;
      if (f == 1) fertile[i] |= (1 << j);
    }
  }

  int ans = solve(M, N, fertile);
  cout << ans << endl;
}

POJ 1795 - DNA Laboratory

概要

N個の文字列が与えられる。それらの文字列を全て含む文字列のうち、最短のものを求めよ。同じ長さの解が複数ある場合は辞書順最小のものを答えよ。(原文)

制約

  • N ≦ 15

解法

  • まず、どれかの文字列に完全に含まれてしまう文字列は、あっても無くても同じなので省く。
  • 残った文字列を連結すれば、全てを含む文字列が出来る。ただし連結部分では共通部分をまとめる。
  • 状態(S, i)を、「集合Sに含まれる文字列が連結済みで、最後がi番目の文字列になっている状態」とし、それぞれの状態における最短の文字列長をビットDPで求める。
  • 最短の長さが求まるので、逆にたどって最短解にたどり着き得る状態がどれかチェックしておく。
  • 上記の情報を利用して、深さ優先探索で文字列を復元し、最適解を更新していく。

コード

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
// Limit: 30000K  5000ms
// Used :  3132K  2016ms
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cstring>
using namespace std;

const int INF = 1000000000;
const int MAX_N = 15;

int common[MAX_N][MAX_N];
int dp[1 << MAX_N][MAX_N];
bool ok[1 << MAX_N][MAX_N];

vector<string> remove_ignorable_strings(vector<string>& S) {
  vector<bool> can_remove(S.size());
  for (int i = 0; i < S.size(); i++) {
    for (int j = 0; j < S.size(); j++) {
      if (i != j) {
        if (!can_remove[i] && S[i].find(S[j]) != string::npos) {
          can_remove[j] = true;
        }
      }
    }
  }
  vector<string> res;
  for (int i = 0; i < S.size(); i++) {
    if (!can_remove[i]) res.push_back(S[i]);
  }
  return res;
}

int common_part(string& s_head, string& s_tail) {
  for (int i = 0; i < s_head.size(); i++) {
    if (s_head[i] == s_tail[0]) {
      string s = s_head.substr(i);
      if (s_tail.find(s) == 0) {
        return s.size();
      }
    }
  }
  return 0;
}

void calc_common_part(vector<string>& S) {
  memset(common, 0, sizeof(common));
  for (int i = 0; i < S.size(); i++) {
    for (int j = 0; j < S.size(); j++) {
      if (i != j) {
        common[i][j] = common_part(S[i], S[j]);
      }
    }
  }
}

void dfs(int state, int last, string cur, string& best, vector<string>& S) {
  if (state == (1 << S.size()) - 1) {
    if (cur < best) best = cur;
    return;
  }

  for (int i = 0; i < S.size(); i++) {
    if ((state & (1<<i)) == 0 && ok[state|(1<<i)][i]) {
      if (dp[state][last] + S[i].size() - common[last][i] == dp[state|(1<<i)][i]) {
        string s = cur + S[i].substr(common[last][i]);
        if (s < best) dfs(state|(1<<i), i, s, best, S);
      }
    }
  }
}

string solve(int N, vector<string>& S) {
  // 他の文字列に完全に含まれてる文字列はあっても無くても同じなので消す
  // 深さ優先探索する時の効率化のために、辞書順でソートしておく.
  S = remove_ignorable_strings(S);
  sort(S.begin(), S.end());
  N = S.size();

  // common[i][j]: S[i]の後ろにS[j]を繋げた場合の共通部分の長さ
  // 後の計算でよく使うので事前計算しておく。
  calc_common_part(S);

  // dp[S][i]: Sに含まれる文字列を繋げて最後がS[i]になっている場合の最短の長さ
  for (int i = 0; i < (1<<N); i++) {
    for (int j = 0; j < N; j++) dp[i][j] = INF;
  }
  for (int i = 0; i < N; i++) dp[(1 << i)][i] = S[i].size();

  // bit DPして各状態の最短の長さを求めておく
  for (int s = 0; s < (1 << N); s++) {
    for (int i = 0; i < N; i++) if (dp[s][i] != INF) {
      for (int j = 0; j < N; j++) if ((s & (1 << j)) == 0) {
        int next_s = (s | (1<<j));
        dp[next_s][j] = min(dp[next_s][j],
                            dp[s][i] + (int)S[j].size() - common[i][j]);
      }
    }
  }

  // 答えになる文字列の長さが求まる。残りは文字列を復元する作業
  int min_length = INF;
  for (int i = 0; i < N; i++) min_length = min(min_length, dp[(1<<N)-1][i]);

  // ok[s][i]: sに含まれる文字列を連結して最後がiになっている状態が、
  // 最適解への経路になり得る場合はtrueにする
  memset(ok, 0, sizeof(ok));
  for (int i = 0; i < N; i++) {
    if (dp[(1<<N)-1][i] == min_length) ok[(1<<N)-1][i] = true;
  }
  for (int s = (1<<N)-1; s >= 0; s--) {
    for (int i = 0; i < N; i++) if (ok[s][i]) {
      for (int j = 0; j < N; j++) if (i != j && (s & (1<<i))) {
        if (dp[s & ~(1<<i)][j] == dp[s][i] - S[i].size() + common[j][i]) {
          ok[s & ~(1<<i)][j] = true;
        }
      }
    }
  }

  // 辞書順で最も小さい解を深さ優先探索で求める
  string best = "Z";
  for (int i = 0; i < N; i++) {
    if (ok[1<<i][i]) dfs(1<<i, i, S[i], best, S);
  }
  return best;
}

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

  int T; cin >> T;
  for (int t = 0; t < T; t++) {
    int N; cin >> N;
    vector<string> S(N);
    for (int i = 0; i < N; i++) cin >> S[i];

    string ans = solve(N, S);
    cout << "Scenario #" << t+1 << ":\n" << ans << endl << endl;
  }
}

POJ 2441 - Arrange the Bulls

概要

N頭の牛とM個の家畜小屋があり、それぞれの牛には1つ以上の好きな家畜小屋がある。家畜小屋には1頭しか入れないとすると、全ての牛を好きな小屋のどれかに入れる方法は何通りあるか。(原文)

制約

  • N ≦ 20
  • M ≦ 20

解法

  • dp(i, S)を、「1番目からi番目の牛が集合Sで示される小屋を使っている場合のパターン数」としてビットDPする。
  • 集合Sは要素数の最大が20なのでintのビットで表現
  • フルにメモリ確保すると足りないので、iが偶数の時と奇数の時の2つ用意して使いまわす。

コード

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
// Limit: 65536K  4000ms
// Used : 12996K  1813ms
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

int solve(int N, int M, vector<vector<int> >& fav) {
  // dp[i][S]: the number of patterns that cow 0-i use S(set) barns
  vector<vector<int> > dp(2, vector<int>(1 << M));
  dp[0][0] = 1;

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < fav[i].size(); j++) {
      int barn_bit = (1 << fav[i][j]);
      for (int s = 0; s < (1 << M); s++) {
        if (!(s & barn_bit)) {
          dp[(i+1)&1][s|barn_bit] += dp[i&1][s];
        }
      }
    }
    fill(dp[i&1].begin(), dp[i&1].end(), 0);
  }
  return accumulate(dp[N&1].begin(), dp[N&1].end(), 0);
}

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

  // read input data
  int N, M; cin >> N >> M;
  vector<vector<int> > fav(N);
  for (int i = 0; i < N; i++) {
    int c; cin >> c;
    for (int j = 0; j < c; j++) {
      int b; cin >> b;
      fav[i].push_back(b-1); // 0-base index
    }
  }
  // solve it and print answer
  int ans = solve(N, M, fav);
  cout << ans << endl;
}

UVa 11990 - Dynamic Inversion

概要

1からNまでの数字を使った順列が与えられる。そこからQ個の数を順に削除する時、Q回のステップにおいて削除直前の転倒数を出力せよ。(原文)

制約

  • N ≦ 20,000
  • Q ≦ 10,000

解法

  • xを追加/削除する時に変化する転倒数は、「xより前にあるxより大きい数」と「xより後にあるxより小さい数」の合計なので、これを効率良く数えたい。
  • i番目の数A[i]を座標上の点(i, A[i])にプロットした場合を考えると、上記の数は「(i,A[i])より左下の領域にある点の数」と「(i,A[i])より右上の領域にある点の数」になる。
  • 点の数はバケット法を使って数える。領域全体はN×Nのサイズだが、これをN個の√N×√N領域に分ける。
  • (0,0)と(x,y)で作られる矩形領域は、完全に含まれているバケット内の数とはみ出し領域に分けられる。
    • バケットに含まれる方はprefix sumを使ってO(√N)。2次元BITを使うともっと早いかもしれない。
    • はみ出した方も、注目するxの幅又はyの幅は√NなのでO(√N)で数え上げられる
  • (0,0)と(x,y)で作られる領域に含まれる点の数をS(x,y)とすると右上領域はS(N,y)-S(x,y),左下はS(x,N)-S(x,y)
  • 結局、点の追加も削除も転倒数のカウントもO(√N)の定数倍になる。トータルでO((N+M)√N)。

コード

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
// Run Time: 2.080
#include <cstdio>
#include <cstring>
using namespace std;

// constants
const int MAX_N = 200000;
const int MAX_M = 100000;
const int BLOCK_SIZE = 450;
const int MAX_BLOCK = (MAX_N-1)/BLOCK_SIZE + 1;

// input data
int N, M;
int A[MAX_N];
int Q[MAX_M];

// variables
int cnt[MAX_BLOCK][MAX_BLOCK];
int prefix_sum[MAX_BLOCK][MAX_BLOCK];
int xs[MAX_N];
int ys[MAX_N];

// by行bx列のブロック内の個数が更新された場合は、
// by行内bx列以降のprefix_sumを更新する
void update_prefix_sum(int bx, int by) {
  int sum = (bx > 0 ? prefix_sum[bx-1][by] : 0);
  for (int i = bx; i < MAX_BLOCK; i++) {
    sum += cnt[i][by];
    prefix_sum[i][by] = sum;
  }
}

// 座標(x, y)に点を加える
void add(int x, int y) {
  int bx = x / BLOCK_SIZE;
  int by = y / BLOCK_SIZE;

  ys[x] = y;
  xs[y] = x;
  cnt[bx][by]++;
  update_prefix_sum(bx, by);
}

// 座標(x, y)の点を削除する
void remove(int x, int y) {
  int bx = x / BLOCK_SIZE;
  int by = y / BLOCK_SIZE;

  ys[x] = -1;
  xs[y] = -1;
  cnt[bx][by]--;
  update_prefix_sum(bx, by);
}

// 座標(0,0)と(x,y)で作られる矩形領域内の点の数を合計する
int count_sum(int x, int y) {
  int block_w = (x + 1) / BLOCK_SIZE;
  int block_h = (y + 1) / BLOCK_SIZE;

  int res = 0;
  // 丸々含まれてるブロックの分
  for (int i = 0; i < block_h; i++) {
    if (block_w > 0) res += prefix_sum[block_w-1][i];
  }
  // はみ出し領域
  for (int i = block_w * BLOCK_SIZE; i <= x; i++) {
    if (ys[i] != -1 && ys[i] < block_h * BLOCK_SIZE) res++;
  }
  for (int i = block_h * BLOCK_SIZE; i <= y; i++) {
    if (xs[i] != -1 && xs[i] <= x) res++;
  }
  return res;
}

// (x,y)の右上の領域と左下の領域の合計(=(x,y)に依存している転倒数)を返す
int count_inversion(int x, int y) {
  int res = 0;
  int intersection = count_sum(x, y);
  res += count_sum(x, N-1) - intersection;
  res += count_sum(N-1, y) - intersection;
  return res;
}

void solve() {
  memset(xs, -1, sizeof(xs));
  memset(ys, -1, sizeof(ys));
  memset(cnt, 0, sizeof(cnt));
  memset(prefix_sum, 0, sizeof(prefix_sum));

  long long inversion = 0;
  for (int i = 0; i < N; i++) {
    add(i, A[i]);
    inversion += count_inversion(i, A[i]);
  }
  for (int i = 0; i < M; i++) {
    printf("%lld\n", inversion);
    inversion -= count_inversion(xs[Q[i]], Q[i]);
    remove(xs[Q[i]], Q[i]);
  }
}

int main() {
  while (scanf("%d %d", &N, &M) == 2) {
    for (int i = 0; i < N; i++) {
      scanf("%d", &A[i]);
      A[i]--;
    }
    for (int i = 0; i < M; i++) {
      scanf("%d", &Q[i]);
      Q[i]--;
    }
    solve();
  }
}