TopCoder SRM601: WinterAndPresents

それぞれのバッグから採るフルーツの個数 X を固定したとき、apple を取った個数が決まれば、orange を取った個数は自動的に決まる。

よって、それぞれの X について、appleを取る個数のパターンを調べれば良い。以下のプログラムでは、取れる apple の最大値と最小値を求めることで対処している。

public class WinterAndPresents {
    public long getNumber(int[] apple, int[] orange) {
        long ans = 0;
        long maxValue = apple.Zip(orange, (a, o) => a + o).Min();
        long n = apple.Length;
        for (long take = 1; take <= maxValue; take++) {
            long maxApple = 0, minApple = 0;
            for (int i = 0; i < n; i++) {
                maxApple += Math.Min(take, apple[i]);
                minApple += take - Math.Min(take, orange[i]);
            }
            ans += maxApple - minApple + 1;
        }
        return ans;
    }
}