SRM 654 Div. 1 Easy: SquareScores (期待値)

解法

i文字目時点での文字cの連続長の期待値をメモしておき、最後に全部足す。

コード

public class SquareScores {

	public double calcexpectation(int[] p, String s) {
		int N = s.length();

		// expScore[i][c]:= i文字目時点でのc連続長の期待値
		double expScore[][] = new double[N][p.length];

		for (int i = 0; i < N; i++) {
			char c = s.charAt(i);
			if (c == '?') {
				// i文字目が?の時
				for (int cint = 0; cint < p.length; cint++) {
					// a-zの各文字を入れて、
					double last = (i > 0) ? expScore[i - 1][cint] : 0;
					expScore[i][cint] = (last + 1) * p[cint] / 100.0;
				}
			} else {
				// i文字目が?でないとき
				int cint = (int) c - 'a';
				double last = (i > 0) ? expScore[i - 1][cint] : 0;
				expScore[i][cint] = last + 1;
			}
		}

		double total = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < p.length; j++) {
				total += expScore[i][j];
			}
		}

		return total;
	}

}