読者です 読者をやめる 読者になる 読者になる

Topcoder SRM606

Easy

ARCのB問題みたいな感じだったけど220ptぐらいしか取れなくて人権ががが
Aさんが一つ数字を持ってる。
Bさんが一つ数字を言う→誤差の絶対値を教えてくれる
Bさんの言った数字とそれとの誤差の絶対値を与えられるから解を求める

class EllysNumberGuessing {
    public:
    int getNumber(vector<int> guesses, vector<int> answers) {
        ll a1, a2;
        a1 = guesses[0] - answers[0];
        a2 = guesses[0] + answers[0];

        for (int i = 1; i < guesses.size(); i++) {
            ll b1, b2;
            b1 = guesses[i] - answers[i];
            b2 = guesses[i] + answers[i];
            if (a1 != b1 && a1 != b2) a1 = -1;
            if (a2 != b1 && a2 != b2) a2 = -1; 
        }
        int ac = 0;
        if (0 < a1 && a1 <= 1000000000) ac+=1;
        if (0 < a2 && a2 <= 1000000000) ac+=2;
        switch (ac) {
            case 0:
                return -2;
            case 1:
                return a1;
            case 2:
                return a2;
            case 3:
                return -1;
        }
        return 0;
    }
};

Med

メモリ制限16MB←よく理由がわからなかった

ざっぱり問題概要

[0, M)の間の数がN個与えられる。(Mは2^nで表せる数)
過半数をしめる数があるか、またあるならそれはいくつかを求める
M=2^30が最大ケースなので、M要素の配列を用意して数えるのはだめだねっていうやつ
N<=50000000なので下手なことするとTLEもあるねっていう

解法

ボイヤームーアさんが考えたすごいアルゴリズムがあるらしい
僕は2^15要素の配列を用意して、下位15bitだけに注目してそれぞれの数を数える
そのなかで最大数(過半数をしめる数があれば、必ず下位15bitだけで仕分けしても最大数を取る)を持つものを上位15bitでもう一度仕分ける

typedef unsigned int uint;

const uint HZ = 1 << 15;
uint countM[HZ] = {};
class EllysPairing {
    public:
    int getMax(int M, vector<int> count, vector<int> first, vector<int> mult, vector<int> add) {
        uint mask = 0xffffffff % M;
        uint all_c = 0, N = count.size();
        for (uint d: count) {
            all_c += d;
        }
        uint c, f, m, a;
        for (uint i = 0; i < N; i++) {
            c = count[i]; f = first[i]; m = mult[i]; a = add[i];
            for (uint j = 0; j < c; j++) {
                countM[f&0x7fff]++;
                f = (f*m+a)&mask;
            }
        }
        uint NH = 1 << 20;
        for (uint i = 0; i < HZ; i++) {
            if (countM[i] > (all_c+1)/2) NH = i;
        }
        if (NH == (1<<20)) {
            return all_c/2;
        }
        fill(countM, countM+HZ, 0);
        for (uint i = 0; i < N; i++) {
            c = count[i]; f = first[i]; m = mult[i]; a = add[i];
            for (uint j = 0; j < c; j++) {
                if ((f&0x7fff) == NH) {
                    countM[(f&0x3fff8000) >> 15]++;
                }
                f = (f*m+a)&mask;
            }
        }
        uint MEL = 0;
        for (uint i = 0; i < HZ; i++) {
            MEL = max(MEL, countM[i]);
        }
        if (MEL > (all_c+1)/2) {
            return (all_c - MEL);
        } else {
            return all_c/2;
        }
        return 0;
    }
};