SRM 736 Div2 Med ReRoll - ちゃっくのメモ帳

問題概要

サイコロがN個ある。そのN個の目は配列Aで渡される。
Aのうち幾つかのサイコロを振り直して、その合計値をtargetにしたい。
最小で幾つのサイコロを振り直せば合計値がtargetになる可能性があるか?

解法

sum(A) = targetならば0個
sum(A) < target ならば小さいやつから振り直していけば良い
sum(A) > target ならば大きいやつから振り直せば良い

class Reroll {
    public:
    int minimumDice(int target, vector <int> dice) {
        int N = dice.size();
        sort(all(dice));
        int sum = accumulate(all(dice),0);
        if(sum == target) return 0;

        if(sum > target){
            int ans = 0;
            for(int i=N-1;i>=0;i--){
                if(sum > target){
                    sum -= dice[i] - 1;
                    ans++;
                }
            }
            return ans;
        }else{
            int ans = 0;
            for(int i=0;i<N;i++){
                if(sum < target){
                    sum += 6 - dice[i];
                    ans++;
                }
            }
            return ans;
        }
    }
};

メモ

解法は自明だが実装でミスった。
ミスった実装は、各目の個数を計算しておいて、sum > targetならば次のように計算していた

diff = sum - target;
for(int i=6;i>=2;i--){
    int t = min(nums[i],diff/(i-1));
    ans++;
    sum -= t * (i-1);
}
return ans;

この実装は例えばdiff=2,A={3}みたいな場合に失敗する。
こういうパターンの実装はdiff/(i-1)を単純に天井関数にしてもsumの更新のときに非zeroかのチェックが必要になったりして複雑になりがちなので解法で提示したように計算量的に大丈夫なら安全な実装をしたほうがよさそう...(教訓)

こういう危険な実装をしがちだけど、危険な実装をやりきるだけの注意力もないので気をつけていきたい