AOJ2165 Strange String Manipulation

問題リンク Strange String Manipulation

• 概要

N個の整数Ii(1<=i<=N)が与えられる。4つの整数パラメータをS, A, C, Mとする。
ここで、擬似乱数Riを次のようにとる。
R0 = S
Ri = (A * R_i-1 + C) MOD M (1 <= i <= N)
入力数列Iから次の数列Oを得る。
Oi = (Ii + Ri) MOD M
数列OのエントロピーHを最小にするようなパラメータS, A, Cを求めよ。複数ある場合はS, A, Cの辞書順で求めよ。
この問題では
M = 256
0 <= S, A, C <= 15
とする。
N < 256

• 解法

(S, A, C)の全組み合わせを試すだけです。一番最初のOiを求めるときにつかうRはR0ではなくR1であることに注意してください。また、エントロピーの大小比較のときに適当なEPSをつけないとWAになります。

• ソース

import java.util.Scanner;

//Strange String Manipulation
public class AOJ2165 {

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int n = sc.nextInt();
			if(n==0)break;
			double min = 1<<29;
			int S = 0, A = 0, C = 0;
			int[] I = new int[n];
			for(int i=0;i<n;i++)I[i]=sc.nextInt();
			for(int s=0;s<16;s++)for(int a=0;a<16;a++)for(int c=0;c<16;c++){
				int R = s;
				int[] O = new int[256];
				for(int i=0;i<n;i++){
					R = (a*R+c)%256;
					O[(I[i]+R)%256]++;
				}
				double H = 0;
				for(int i=0;i<256;i++)if(O[i]>0)H-=O[i]*1.0/n*Math.log(O[i]*1.0/n);
				if(H+1e-10<min){
					min = H; S = s; A = a; C = c;
				}
			}
			System.out.println(S+" "+A+" "+C);
		}
	}

	public static void main(String[] args) {
		new AOJ2165().run();
	}
}