【AOJ 2165】 Strange String Manipulation

問題

Strange String Manipulation | Aizu Online Judge

方針

• S,A,Cを総当りして, エントロピーが一番低くなる場合を探す.
• 誤差を考えて, epsを足さないと死んでしまう.

コード

#include<bits/stdc++.h>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define eps 1e-9
#define INF 1e9
#define m0(x) memset(x, 0, sizeof(x))

using namespace std;

signed main(){
  int n;
  int I[300];
  int r[300];
  int o[300];
  int freq[300];

  while(cin >> n, n){
    REP(i,1,n+1){
      cin >> I[i];
    }

    double minH = INF;
    int minS, minA, minC, idx;
    
    rep(s, 16){
      rep(a, 16){
    rep(c, 16){

      r[0] = s;      
      m0(freq);
      REP(i, 1, n+1){
        r[i] = (a * r[i-1] + c) % 256;
        idx = (I[i] + r[i]) % 256;
        freq[idx]++;
      }
      
      double sum=0;
      rep(i, 256){
        if(freq[i] == 0) continue;  
        sum += ((-1) * (freq[i]/(double)n) * (log(freq[i]/(double)n)));
      }
      if(sum + eps < minH){
        minH = sum; minA = a; minS = s; minC = c;
      }   
    }
      }
    }
    cout << minS << " " << minA << " " << minC << endl;
  }
}

参考

d.hatena.ne.jp

今週中に200を終わらせよう.