2014-01-30

SRM 606 Div1 450 EllysPairing

20:46 |

「数列の計算式 (X[0], X[i+1]=(A[j]*X[i]+B[j])%M) と数列の長さ」が N 組与えられる。
数列たちに含まれる全ての数を使ってペアを作る。最大何個作れるか。ペア内の数字は異なること。
1≦N≦50, Mは２の累乗, 2≦M≦2^30, 0≦A[j], B[j]≦M-1, 1≦各数列の長さ≦1,000,000
メモリ制限 16MB

サンプルからするに、出現回数が一番多いものの出現回数≦数字の数/2なら数字が異なる制約はクリアできるっぽい。
そうじゃないときはそれなりに減る。
出現回数 - 制約なしの時のペア数 - 制約なしの時ペアから余る個数だけ減る。

これでとりあえず出現回数を全部数えるコードを書いて正しそうなことを確認。

M が大きいのでどうやって絞るか
全数列を生成するのに 50,000,000 回
メモリ 16MB までなら int 3*10^6 個くらいとれるので
[0, M) を 10^9 / (3*10^6) = 333 個に分けて 333 回全数列を生成して数える→1.6*10^10→無理

.....

ある数字 Y が沢山出現するということは Y はどこかの数列で周期 4 以内くらいで出現するはず
最初の 4 項の数字だけ数えるようにしてみる
failed system test

(あとで)
最初はループしてなくて途中からループする場合があるっぽい。ぐぬぅ

TLを眺める

Div1-Mediumはこれですよ http://t.co/2fixl1Bo55
— *IRUN (@ir5) 2014, 1月 30

majorityを求めるアルゴリズムがあるらしい。ほ〜
accepted in practice

class EllysPairing {
	public:
	int getMax(int M, vector <int> count, vector <int> first, vector <int> mult, vector <int> add) {
		int N=count.size();
        int co=0;
        ll maj=-1;
        REP(i, N) {
            uint32_t v = first[i];
            REP(loop, count[i]) {
                if(v==maj) co++;
                else if(co==0) maj=v,co=1; else co--;
                v = (v * mult[i] + add[i]) & (M-1);
            }
        }
        co=0;
        REP(i, N) {
            uint32_t v = first[i];
            REP(loop, count[i]) {
                if(maj==v) co++;
                v = (v * mult[i] + add[i]) & (M-1);
            }
        }
        int total=accumulate(ALL(count), 0);
        int th = total/2;
        if(co>th) {
            int rest = (co-th) - (total-th*2);
            th-=rest;
        }
        return th;
	}
};

別解で、数字の下位 16bit だけを対象に集計(合計)したやつと上位 16bit だけを対象に集計したやつを別々に考えてそれぞれで出現回数が多かった数字が過半数候補、というのもあるらしい。

下位 16bit では最多ではないけど、全体で最大、という見逃される数はないのか？？
2つに分かれるときが一番きわどくて、
その2つの合計≦全体の半数　なら見逃されたやつ1個の個数＜その2つの合計(≦全体の半数),
その2つの合計＞全体の半数　なら　(見逃されたやつ1個の個数≦)残りの合計≦全体の半数
なので見逃されたやつの個数が全体の半数を超えることはない
おー

accepted in practice

int h[(1<<16)+1];
class EllysPairing {
	public:
	int getMax(int M, vector <int> count, vector <int> first, vector <int> mult, vector <int> add) {
		int N=count.size();
        CLEAR(h, 0);
        REP(i, N) {
            VI w;
            uint32_t v = first[i];
            REP(loop, count[i]) {
                h[v&((1<<16)-1)]++;
                v = (v * mult[i] + add[i]) & (M-1);
            }
        }
        ll lo=-1, loi=-1;
        REP(i, 1<<16) if(lo<h[i]){lo=h[i];loi=i;}
        
        CLEAR(h, 0);
        REP(i, N) {
            VI w;
            uint32_t v = first[i];
            REP(loop, count[i]) {
                h[v>>16]++;
                v = (v * mult[i] + add[i]) & (M-1);
            }
        }
        ll hi=-1, hii=-1;
        REP(i, 1<<16) if(hi<h[i]){hi=h[i];hii=i;}
        
        int maj = (hii<<16)+loi, mx=0;
        REP(i, N) {
            VI w;
            uint32_t v = first[i];
            REP(loop, count[i]) {
                if(v==maj) mx++;
                v = (v * mult[i] + add[i]) & (M-1);
            }
        }
        
        int total=accumulate(ALL(count), 0);
        int th = total/2;
        if(mx>th) {
            int rest = (mx-th) - (total-th*2);
            th-=rest;
//            cout<<"--- "<<rest<<endl;
        }
        return th;
	}
};

kojingharangの日記

2014-01-30

SRM 606 Div1 450 EllysPairing