GCJ2012 Round 1A : Password Problem

問題概要

長さBのパスワードがあって、A文字目まで打ち込んでいる。これまでに打った文字が正しいかどうか確率が与えられるので、最適手順をとったときのパスワードが通るまでの手数の期待値の最小値を求める問題。

解法

期待値DP。状態数A、遷移3つなので素直に書いてやればよい。自分の解答は色々余計なことをしていてちょっと反省点が多い。まずはシンプルに書くべきなのに…。

import std.stdio, std.algorithm;
import std.math;

int A, B;
real[] ps;

void init(){
	scanf("%d%d",&A, &B);
	ps = new real[](A);
	foreach(i; 0..A){
		double p;
		scanf("%lf", &p);
		ps[i] = p;
	}
}

real solve(){
	real ans = 0.0;
	real[] accum = new real[](A + 1);
	accum[0] = 0.0;
	foreach(i; 0..A){
		accum[i+1] = accum[i] + log(ps[i]);
	}
	
	real[] dp = new real[](A + 1);
	dp[0] = B + 1;
	real mini = dp[0];
	foreach(i; 1..A+1){
		dp[i] = min(1.0 + mini, B - i + 1.0 + (1.0-exp(accum[i])) * (B + 1.0) , 1.0 + dp[0]);
		mini = min(1.0 + mini, dp[i]);
	}
	
	return dp[A];
}

void main(){
	int T;
	scanf("%d", &T);
	foreach(c; 0..T){
		init;
		writefln("Case #%d: %.8f", c+1, solve);
	}
}