TopCoder SRM 643 Div1

Tatsuya Yatagawa
Programming Contest

こんにちはtatsyです。いつものようにSRMの解説をします。

Easy (250点)

問題

数字N(最大10^18)が与えられるので、これを素因数分解し、その素因数を小さい順に重複を含めて配列として返したい。このときヒントとして、答えの配列の偶数版目の要素(配列番号は0から始まる)が与えられる。

解法

まず、いつも通り単純に考えると、普通にエラトステネスのふるいみたいなことをして、素因数を列挙することが出来そうです。が、当然ながら計算量が大きすぎます。

今回の問題では素因数の一部が与えられているので、それで最初にNを割ってあげて、その商に対して素因数を列挙すれば、少し計算量が少なく出来そうです。

ところが、この場合ですと、例えばN=2×(すごく大きい素数)のときに、すごく大きい素数をエラトステネスのふるいで処理しないといけないので、結局計算量があまり減らせません。

ここで大切なポイントは、素因数がM個あるときに、少なくとも2番目に大きい素因数が与えられているということです。

ということは、2番目に大きい素因数より小さな素因数を全て見つけることができれば、それで割った余りは当然素因数になります。

したがって、2×(すごく大きい素数)の場合には、Nを割った次点で商であるすごく大きい素数が素因数であることが分かるわけです。

この考え方を使うと、エラトステネスのふるいにかけなくてはならない数字は10^6程度になります。

エラトステネスの古いの計算量はO(NloglogN)なので、これで十分間に合います。というわけで正解のコードは以下のようになります。

typedef long long lint;

#define Integer int
#define REP(i,n) for(Integer i=0; i<n; i++)
#define ALL(a) (a).begin(), (a).end()

class TheKingsFactorization {
public:
    vector<long long> getVector(long long N, vector<long long> pr) {
        REP(i, pr.size()) {
            N /= pr[i];
        }

        lint ma = pr[pr.size() - 1];
        for (lint i = 2; i*i <= N && i<=ma; i++) {
            while (N % i == 0) {
                N /= i;
                pr.push_back(i);
            }
        }
        if (N != 1) pr.push_back(N);
        sort(ALL(pr));
        return pr;
    }
};

Medium (500点)

問題

2列にN人ずつ並んだ兵士がいる。各兵士の今の気持ちはH(Happy)かS(Sad)で与えられている。ある兵士Xが別の兵士Yに話しかけると、兵士Yは兵士Xと同じ気持ちになる。今、以下の操作を何回か繰り返して、全兵士の気持ちがHになるようにしたい。

  1. ある兵士Xを選んで、彼と隣あう兵士Yに話しかけさせる
  2. 片方の列の連続した何人かの兵士を選んで、その兵士たちに別の列の兵士に話しかけさせる
  3. 前から何番目かの2人の兵士を選んで、彼らの前後どちらかにいる2人の兵士にそれぞれ話しかけさせる

このとき、必要な操作の最小回数を答えよ。

解法

ちょっと違うかもですが、アルゴリズム的にはPKU 1141 Blacket Sequenceと似ている問題だと思いました。

この類の問題はある区間[s, e)を処理するのに必要な操作回数をメモ化しておき、深さ優先探索するというのが王道のような気がします。

なので、その方針に従いメモ化深さ優先探索のコードを考えます。

単純には区間[s, e)を処理する回数を単にメモ化して深さ優先探索すればよいのですが、今回のケースは列が2列あるので、上の列をそろえたいのか、下の列をそろえたいのか、両方をそろえたいのかをマスクとして持ちます。

なのでメモ化の配列はmemo[左端][右端][マスク]となります。

あとは、これを上記の操作にあうように深さ優先で更新すればいいです。

typedef long long lint;

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

const int INF = 1 << 20;
int memo[211][211][3];

class TheKingsArmyDiv1 {
public:
    vector<string> state;

    int dfs(int s, int e, int f) {
        if (s >= e) return 0;

        int& res = memo[s][e][f];
        if (res == -1) {
            if (f < 2) {
                bool ok = true;
                for (int i = s; i < e; i++) {
                    ok &= state[f][i] != 'S';
                }
                if (ok) return res = 0;
            }

            res = INF;
            if (s + 1 < e) {
                int ll = min(dfs(s + 1, e, f), dfs(s + 1, e, 2)) + 1;
                int rr = min(dfs(s, e - 1, f), dfs(s, e - 1, 2)) + 1;
                res = min(res, min(ll, rr));

                for (int i = s + 1; i < e; i++) {
                    int ll = min(dfs(s, i, f), dfs(s, i, 2));
                    int rr = min(dfs(i, e, f), dfs(i, e, 2));
                    res = min(res, ll + rr);
                }
            }

            if (f == 2) {
                res = min(res, dfs(s, e, 0) + dfs(s, e, 1));
                res = min(res, min(dfs(s, e, 0), dfs(s, e, 1)) + 1);
            }
        }
        return res;
    }

    int getNumber(vector<string> _state) {
        this->state = _state;
        memset(memo, -1, sizeof(memo));
        int ans = dfs(0, state[0].size(), 2);
        return ans >= INF ? -1 : ans;
    }
};

まとめ

今回はEasyの問題がチャレンジ祭りになりそうな予感を醸し出しまくっていて怖かったのですが、それなりに良い順位で正解できたので良かったです。

というわけで今回の解説を終わります。

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