TopCoder SRM 594 Div1

Tatsuya Yatagawa

2013-10-25

Programming Contest

今回はSRMに寝落ちして出ていない(Registrationもしてない)のですが、Easyだけ備忘録的に解説します (遅い)。

Easy (250点)

この問題はある太陽系を調べていて、現在AとBの二つの調査結果が得られているという前提。

この調査結果には惑星の大きさと太陽からの距離が記録されていて、記録順は太陽から近い順になっている。

このときに2つの調査結果から考えうる最小の惑星の数を答えるというのが問題の目的です。

重要なポイントとして、調査結果に含まれるデータは必ずしも連続した惑星のデータではなく、間に別の惑星があるかもしれないという点です。

まず、両方の調査結果をそれぞれNA倍、NB倍して、惑星同士のマッチングを考えればよいのではないか？ということに気づきます。

マッチングするときのNA、NBはマッチさせる惑星のペアについて大きさの最小公倍数をとって決定してあげます。

次にマッチングをどうやるか？という問題ですが、これは動的計画法の典型問題で計算が可能です。

具体的にどうするかというとdp[i][j]には調査結果Aのi番目の惑星までと調査結果Bのj番目の惑星までを使った時の最小の惑星の数を入れておきます。
するとdp[i][0] = i, dp[0][j] = jであって、

dp[i][j] = dp[i-1][j-1] + 1 (A[i-1] == B[j-1])
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1 (A[i-1] != B[j-1])

と更新すればよいです。

このアルゴリズムだとマッチさせる惑星の組み合わせが最大50²通り、動的計画法の部分が最大50²の計算量なので、全体では50⁴=6.25e6で時間内に計算できます。

以下が正解のコードです。


#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <utility>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <climits>
using namespace std;

#define REP(i,n) for(int i=0; i<n; i++)
#define REPP(i,s,e) for(int i=s; i<=e; i++)
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl

typedef pair<int,int> P;
typedef long long LL;
typedef vector<LL> VI;

class AstronomicalRecords {
public:
    int na, nb;
    int table[55][55];

    LL gcd(LL x, LL y) {
        if(x < y) swap(x, y);
        while(y != 0) {
            LL c = x % y;
            x = y;
            y = c;
        }
        return x;
    }

    LL lcm(LL x, LL y) {
        LL c = gcd(x, y);
        return x * y / c;
    }

    int match(VI A, VI B, LL x, LL y) {
        REP(i,na) A[i] *= x;
        REP(i,nb) B[i] *= y;

        memset(table, 0, sizeof(table));
        REP(i,na+1) table[i][0] = i;
        REP(i,nb+1) table[0][i] = i;
        for(int i=1; i<=na; i++) {
            for(int j=1; j<=nb; j++) {
                if(A[i-1] == B[j-1]) {
                    table[i][j] = table[i-1][j-1] + 1;
                } else {
                    table[i][j] = min(table[i-1][j], table[i][j-1]) + 1;
                }
            }
        }
        return table[na][nb];
    }

    int minimalPlanets(vector <int> A, vector <int> B) {
        this->na = A.size();
        this->nb = B.size();

        VI va(na);
        VI vb(nb);
        REP(i,na) va[i] = A[i];
        REP(i,nb) vb[i] = B[i];
        
        int res = INT_MAX;
        for(int i=0; i<na; i++) {
            for(int j=0; j<nb; j++) {
                LL l = lcm(va[i], vb[j]);
                LL x = l / va[i];
                LL y = l / vb[j];
                int m = match(va, vb, x, y);
                res = min(res, m);
            }
        }
        return res;
    }
}

まとめ

今回の解説はここまでです。でてないので分からないですが、問題文の調査結果は連続した惑星について書かれているとは限らないという部分を読み落としてChallengeされる人がいそう。

テストケースだとこれに該当するやつはないですし。

ともあれ、今からSRM595にいってきます。

最後までお読みいただきありがとうございました。