TopCoder SRM 831 : Div1 Easy Div2 Hard RerollCheater

前回の大ポカをだいぶ取り戻した。
https://community.topcoder.com/stat?c=problem_statement&pm=17624

問題

N個の20面ダイスを転がした結果が与えられる。
この後、最大K回まで、1つダイスを選び、転がしなおすことができるとする。
ただし、各回で出る目は確定しているとする。

K回以内で任意回数転がし直した状態で終了できるとき、ダイスの目の総和最大値と、それを達成するダイスの選び方を答えよ。

解法

目が最小のダイスを選び、転がしなおせばよい。
途中、目の総和が最大値となった時点を解答するとよい。

class RerollCheater {
	public:
	vector <int> reroll(vector <int> currentDice, vector <int> futureRolls) {
		int best=0;
		int S=0;
		FORR(c,currentDice) S+=c;
		vector<int> ret,cur;
		best=S;
		
		int i,j;
		FOR(i,futureRolls.size()) {
			int x=futureRolls[i];
			int tar=0;
			FOR(j,currentDice.size()) if(currentDice[j]<currentDice[tar]) tar=j;
			S-=currentDice[tar];
			currentDice[tar]=x;
			cur.push_back(tar);
			S+=x;
			if(S>best) {
				best=S;
				ret=cur;
			}
		}
		return ret;
		
		
	}
}

まとめ

Div1Easyにしては安直すぎる問題だったけど、これ225ptとかではないんだな。