TopCoder SRM 829 : Div1 Medium QuestionOrder

450ptなので易しめ。
https://community.topcoder.com/stat?c=problem_statement&pm=17589&rd=19218

問題

N問の問題を任意の順で解くことを考える。
各問題iを解ける確率はP[i]である。
各問題iを解けたとき、取得得点にA[i]を加える。解けなかったとき、取得得点が0にリセットされる。

問題を解く順を最適化したとき、最終的な得点の期待値の最大値を答えよ。

解法

問題iとjどちらを先に解くかで、得点の期待値を考える。

• iを先に解くとP[j]*(A[j]+A[i]*P[i])
• jを先に解くとP[i]*(A[i]+A[j]*P[j])

よって上記値の大小から、iとjどちらを先に解くと良いかがわかる。

const ll mo=1000000007;

class QuestionOrder {
	public:
	int maxExpProfit(vector <int> A, vector <int> P) {
		int N=A.size();
		int i,j;
		FOR(i,N) {
			FOR(j,N-1) {
				if(A[j]*P[j]*100+A[j+1]*P[j]*P[j+1]>A[j+1]*P[j+1]*100+A[j]*P[j]*P[j+1]) {
					swap(A[j],A[j+1]);
					swap(P[j],P[j+1]);
				}
			}
		}
		ll ret=0;
		ll m=1;
		FOR(i,N) {
			ret=(ret+A[i]*m)*P[i]%mo;
			m=m*100%mo;
		}
		return ret;
	}
}

まとめ

100を掛ける位置を誤って1WA。