WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM669 Div1 Easy "SubdividedSlimes"

解法

スライムをn回斬ると決めたとき、最終的なミニスライムの大きさがなるべく均一になるように斬ると最もポイントが高くなる。
例えば、スライムの大きさが10、3回斬るとする。その時、ミニスライムは4つになっているが、これが均一になるとよいので、{3, 3, 2, 2}とするとよい。

根拠としては、最後のミニスライムの大きさがそれぞれa, b, c, dだとすると、ポイントはab + ac + ad + bc + bd + cdとなる。これは、a,b,c,dそれぞれが自分以外の要素と掛けたものの総和のため、・・・あれ?


・・ごめん分からない・・・

ソースコード

class SubdividedSlimes {
    public:
    int needCut(int S, int M) {
        for (int K = 1; K < S; K++) {
            int rem = S;
            int sum = 0;
            int d = S / (K + 1);
            int a = S % (K + 1);
            for (int i = 0; i < K; i++) {
                int m = d + (i < a ? 1 : 0);
                rem -= m;
                sum += m * rem;
            }
            if (sum >= M) return K;
        }
        return -1;
    }
};