問題

問題URL: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2165
ソースコード: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1358719
言語はC++

問題文日本語訳

線形合同法は擬似乱数を発生させる手法で、擬似乱数Rを以下のように発生させる

R(0) = S
R(i) = ((A・R(i-1) + C) mod M  (for i >= i)

S, A, C, M はパラメータであり、この問題においては、0 <= S, A, C <= 15, m = 256 とする。

入力I (Iは0以上M-1以下の整数) に対して、Rを利用して以下の式でOを得る

O(i) = (I(i) + R(i)) mod M (for i >= 1)

あなたの仕事は、S, A, C を求めるプログラムを書くことである。 O(i)のエントロピーを最小化するようなS, A, Cを求めよ。エントロピーHは以下の式で求められる（式略）

　入力

入力は複数のデータセットからなる。それぞれのデータセットは以下のように与えられる

N
I(1) I(2) ... I(N)

Nは256以下で、それぞれのIは空白で区切られる。

出力

それぞれのデータセットに対して、S, A, C を空白区切りで1行で出力せよ。

入出力や式については問題原文を参照してください。

解放

S, A, C を 0から15まで変化させてみてすべて試すだけである。 O(S * A * C * N) 程度になるが、数字が小さいので余裕で間に合う

ただし、エントロピーの大小を比較する時、Doubleの誤差を考慮しないと Wrong Answer になるようなので注意が必要。

ソースコード

int main(int argc, const char * argv[]){
    while(true){
        int n, I[256], m = 256;
        
        cin >> n;
        if(!n) break;
        
        REP(i,n) cin >> I[i];
        
        int as = 0, aa = 0, ac = 0;
        double ah = 10000.0;
        REP(s,16) REP(a,16) REP(c,16){
            int cnt[256];
            REP(i, 256) cnt[i] = 0;
            
            int r = s;
            REP(i,n){
                r = (a * r + c) % m;
                int o = (I[i] + r) % m;
                cnt[o]++;
            }
            
            double h = 0.0;
            REP(i,m){
                if(cnt[i]){
                    h -= (double)cnt[i] / n * log((double)cnt[i] / (double)n);
                }
            }
            
            if(h + ESP< ah){
                ah = h;
                as = s;
                aa = a;
                ac = c;
            }
        }
        cout << as << " " <<  aa << " " << ac << endl;
    }
}