TopCoder SRM 649 Div1

Tatsuya Yatagawa
Programming Contest

こんにちはtatsyです。本日もSRMの解説いきます。

Easy (250点)

問題

ある長さNの文字列が与えられる。このSnukeさんはこの文字列のうちK個を取り除いてあなたに見せる。この際、あなたはSnukeさんが何番目の文字を消したのかを言い当てたい。確実に言い当てられる場合には”Certain”を、そうでない場合には”Uncertain”と答えよ。

解法

確実に言い当てられない場合というのは、結果が同じになるようなK文字の選び方が複数通りある場合です。

それはどういう場合かというと、文字列に同じ文字が2つ含まれていて、それぞれが位置iと位置jにあるときにabs(i – j) <= Kである場合になります。

なぜかというと、このような場合には2つの文字の間の文字を全て消して、2つの文字のどちらかを消すことで、結果が同じ文字列ができるからです。

なので、全ての文字について、その文字よりあとに初めて現れる同じ文字を探し、その位置の差がK以下になっているかどうかをチェックすればいいです。

class Decipherability {
public:
    bool ok(string s, int K) {
        int M = s.size();
        if (M == K) return true;

        for (int i = 0; i < M; i++) {
            for (int j = i + 1; j < M; j++) {
                if (s[i] == s[j]) {
                    if (j - i <= K) return false;
                }
            }
        }

        return true;
    }

    string check(string s, int K) {
        return ok(s, K) ? "Certain" : "Uncertain";
    }
};

Medium (550点)

問題

N以下の数からなる数列Aがあたえられる。このときNは2のべき乗である。今0以上N-1以下の数Bを適当に選びAの各要素とXORを取る。このとき、得られる数列をCとするときC[i] < C[j]かつi < jとなるペアの数が最大になるようにしたい。最大化したペアの数を答えよ。

解法

まず大切な考察として、もしCを計算することができるのであれば、上記の条件を満たすペアの数を計算するコストはO(NlogN)です。

これはBIT (binary indexed tree)を使えば可能で、数字を大きい順に処理していき、処理した位置でBITの値を1に変えておけば、自分より大きい数で自分より後に現れる数の個数がO(logN)で計算できるからです。

なので、結果のCを求める方法を考えます。

XORを取るとBでビットが経っている位置のビットがAの方で反転するので、どの位置のビットを反転させればいいかを考えればよさそうです。

とはいえ、ビットの選び方はN (<= 2^30)通りもあるので、全てを調べることはできません。

この問題の場合は、各ビットを反転させた時に、順序が入れ替わるかどうかは他のビットを反転させたか否かには依存しないため、各ビットを反転させるかどうかを独立に考えることができます。

なので、各ビットを反転させたときと反転させない時で、条件を満たすペアの数を数えて、もし反転させたほうが大きければ、ビットを反転させます。

それで、最後に得られた数列がCになるので、これのペアの数を求めれば終了です(実際には1回計算してるので、再計算する必要はないけど)。

#define Integer int
#define REP(i,n) for(Integer i=0; i<n; i++)
#define REPA(i,s,e) for(Integer i=s; i<=e; i++)
#define REPD(i,s,e) for(Integer i=s; i>=e; i--)
#define SIZ(a) (Integer)(a).size()
#define ALL(a) (a).begin(), (a).end()

class BIT {
private:
    int sz;
    vector<lint> nodes;

public:
    BIT(int n) : sz(n), nodes(n + 1, 0) {}

    void add(int x, lint val) {
        for(; x<=sz; x+=(x&-x)) nodes[x] += val;
    }

    lint sum(int x) { 
        lint ret = 0;
        for (; x>0; x-=(x&-x)) ret += nodes[x];
        return ret;
    }

    lint sum(int x, int y) {
        return sum(y) - sum(x-1);
    }
};

class XorSequence {
public:
    vector<lint> makeA(int N, int sz, int A0, int A1, int P, int Q, int R) {
        vector<lint> A;
        A.resize(sz);
        A[0] = A0;
        A[1] = A1;
        for (int i = 2; i < sz; i++) {
            A[i] = (A[i - 2] * P + A[i - 1] * Q + R) % N;
        }
        return A;
    }

    int pow2(int n) {
        int ret = 0;
        while (n != 1) {
            ret++;
            n /= 2;
        }
        return ret;
    }

    lint calc(const vector<lint>& A, const int b) {
        int n = A.size();

        BIT bit(n);

        for (int i = 0; i < n; i++) {
            int a = (A[i] >> b) & 0x01;
            if (a != 0) {
                bit.add(i+1, 1);
            }
        }

        lint ret = 0;
        for (int i = 0; i < n; i++) {
            int a = (A[i] >> b) & 0x01;
            if (a == 0) {
                ret += bit.sum(i+1, n);
            }
        }

        return ret;
    }

    lint countUp(const vector<lint>& A) {
        int n = A.size();
        vector<pll> v(n);
        REP(i, n) v[i] = pll(-A[i], i + 1);
        sort(ALL(v));

        lint ret = 0;
        BIT bit(n);
        REP(i, n) {
            int k = (int)v[i].second;
            ret += bit.sum(k, n);
            bit.add(k, 1);
        }
        return ret;
    }

    long long getmax(int N, int sz, int A0, int A1, int P, int Q, int R) {
        vector<lint> A = makeA(N, sz, A0, A1, P, Q, R);
        int M = pow2(N);

        vector<lint> rA(sz);
        for (int i = M-1; i>=0; i--) {
            copy(ALL(A), rA.begin());
            for (int k = 0; k < sz; k++) {
                rA[k] ^= (1ll << i);
            }
            
            lint s = countUp(A);
            lint t = countUp(rA);

            if (s < t) {
                copy(ALL(rA), A.begin());
            }
        }
        return countUp(A);
    }
};

まとめ

今回はEasyは結構簡単だったみたいで、かなりの数の人が解答していて、Challengeとかで落ちた人も少なかったですね。

Mediumは解法は完全に思いついていたのですが、デバッグが間に合わずにSubmitできませんでした。Medium正解まで今までで一番惜しかった…。

というわけで今回の解説を終わります。最後までお読みいただき、ありがとうございました。