WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM606 Div1 Medium "EllysPairing"

問題

TopCoder Statistics - Problem Statement

この問題ではメモリが16Mbyteしか使えません!注意してください!

エリーはとても興奮していた!彼女は世界中の大学が手を組んで、ペア-プログラミングによるプロジェクトを進めていく素晴らしい構想に参加している。今、このプロジェクトの主催者は、ペア(2人チーム)を決めようとしている。

ある2人にペアを組ませる際、その2人が同じ大学か、違う大学かは問わない。しかし、同じ名前だと混乱を起こしてしまう。そこで、違う名前の大学生同士で、いかに多くのペアを作るかを考えたい。

名前はMだけ種類があり、このMは2の乗数(1, 2, 32, 131072...)である。簡単のため、名前は0~M-1の番号とする。あなたは、整数Mと、int[] count, first, mult, addが与えられる。これらの意味は次のようになる。i番目の大学は、count[i]だけ参加者がいる。1番目の人の名前はfirst[i]である。2番目の人の名前(second[i]とする)は、( first[i] * mult[i] + add[i] ) % Mである。3番目の人の名前は、( second[i] * mult[i] + add[i] ) % Mである。と、このように続いていく。(尚、Mは2の乗数なので、a % M は a & ( M - 1 )と、効率よく計算できる事に留意してください)

違う名前のペアが、最大何ペア組めるかを返せ。

制約

1 <= M <= 1073741824
1 <= 参加者の数 <= 5 * 10^7


考えたこと

ここに名前があるじゃろ? →2, 1, 1, 3, 3, 2, 2, 4, 3, 1
これを、こうして     →1, 1, 1, 2, 2, 2, 3, 3, 3, 4
こうじゃ         →1, 1, 1, 2, 2
              2, 3, 3, 3, 4
( ^ω^)答え. 5ペアじゃ

ここに名前があるじゃろ? →2, 1, 1, 3, 1, 2, 2, 4, 1, 1
これを、こうして     →1, 1, 1, 1, 1, 2, 2, 2, 3, 4
こうじゃ         →1, 1, 1, 1, 1
              2, 2, 2, 3, 4
( ^ω^)答え. 5ペアじゃ

ここに名前があるじゃろ? →2, 1, 1, 3, 1, 2, 1, 1, 1, 1
これを、こうして     →1, 1, 1, 1, 1, 1, 1, 2, 2, 3
こうじゃ         →1, 1, 1, 1, 1
              1, 1, 2, 2, 3
( ^ω^)答え. 3ペアじゃ

・参加者数をNとする
・最大ペア数は、N / 2である。
・ただし、過半数を超える名前が存在し、その数がmajorityである場合、最大ペア数はN - majorityである。
・過半数を超える名前が存在しなければ、N / 2のペアが作れることが保証される。


よって、あとは配列をマップのように使ってindex : countのようにして、過半数を超える名前があるか調べればよい。

うわっ・・・ 私のメモリ、少なすぎ・・・?

名前の種類は最大10億ぐらい。参加者の数的にint型で持っておきたいので、配列で数を数えようとすると、4byte * 10^9で40Gbyteになる。これはさすがにないな。じゃあちゃんとしたmap使おう。参加者の数は最大で5000万人いるので4byte * 5000万で200Mbyteか。むりやん・・・

Majority Vote Algorithm

過半数を得票した人を調べる効率的なアルゴリズムとして、Majority Vote Algorithmというのがあるらしい。詳細は省くが、これを使うとO(N)の計算量で、過半数を得票した可能性のある人を見つけることができる。面白いのが、あくまで可能性であって、得られた結果の候補者が、必ず過半数を取っているわけではないという所。その人が本当に過半数を得票しているかは、もう一度調べなおす必要がある。

MODとAND

MOD, %・・・めっちゃ時間かかる。コンピュータにとっては苦手な演算子
AND, &・・・めっちゃ速い。コンピュータにとっては得意な演算子


ソースコード

class EllysPairing {

    public:

    int getMax(int M, vector <int> count, vector <int> first, vector <int> mult, vector <int> add) {

        int majority = -1; // 過半数とってるかも?な名前
        int vote = 0;

        int N = count.size();
        int all = 0;

        // Majority Vote Algorithm!!
        for (int i = 0; i < N; i++) {

            long long n;
            all += count[i];

            for (int j = 0; j < count[i]; j++) {
                if (j == 0) {
                    n = first[i];
                } else {
                    n = (n * mult[i] + add[i]) & (M - 1);
                }

                if (majority == n) {
                    vote++;
                } else if (majority == -1) {
                    majority = static_cast< int >( n );
                    vote++;
                } else {
                    if (vote == 1) majority = -1;
                    vote--;
                }
            }            
        }

        // 過半数とってるか調べる
        vote = 0;
        for (int i = 0; i < N; i++) {

            long long n; 

            for (int j = 0; j < count[i]; j++) {
                
                if (j == 0) {
                    n = first[i];
                }
                else {
                    n = (n * mult[i] + add[i]) & (M - 1);
                }

                if (majority == n) {
                    vote++;
                }
            }
        }

        return min(all / 2, all - vote);

    }
};