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; } }