読者です 読者をやめる 読者になる 読者になる

日々精進

新しく学んだことを書き留めていきます

SRM489 Div2 Medium

問題の分析
int型配列rosesとliliesでroseとlilyの数がそれぞれ与えられます。
同じインデックスのroseとlilyはセットになっています。各セットのうちいくつかを購入してroseとlilyを矩形に並べます。
ただし、同じ種類の花が隣り合ってはいけません。
矩形の長辺−短辺の最小値を求めなさい。
方針
各セット毎に購入する・しないの2パターンが考えられます。dfsですべての場合を調べます。
長辺−短辺の最小値はroseとlilyの合計値をM×Nに因数分解し、M - Nの絶対値の最小値を求めればOKです。
ソースコード
下記コードで大体OKなんですが、下記テストケースがエラーとなります。
roses: {1, 208, 19, 0, 3, 234, 1, 106, 99, 17}
lilies: {58, 30, 3, 5, 0, 997, 9, 615, 77, 5}
Returns: 36
どこが間違っているかわかる方いらっしゃいましたらご教授願います。

using System;
using System.Collections.Generic;
using System.Text;
 
 
public class BuyingFlowers
{
    private int min = int.MaxValue;
    public int buy(int[] roses, int[] lilies)
    {
        dfs(roses, lilies, 0, 0, 0);
        if (min == int.MaxValue)
            return -1;
        else
            return min;
    }
 
 
    private void dfs(int[] roses, int[] lilies, int idx, int sumR, int sumL)
    {
        if (idx == roses.Length)
        {
            if (Math.Abs(sumR - sumL) >= 2) return;
            int sum = sumR + sumL;
            List<int> factors = getFactors(sum);
            foreach (int factor in factors)
                min = Math.Min(min, Math.Abs(factor - sum / factor));
        }
        else
        {
            dfs(roses, lilies, idx + 1, sumR + roses[idx], sumL + lilies[idx]);
            dfs(roses, lilies, idx + 1, sumR, sumL);
        }
    }
 
 
    private List<int> getFactors(int num)
    {
        List<int> res = new List<int>();
        double sq = Math.Sqrt(num);
        for (int i = 2; i <= sq; i++)
            if (num % i == 0)
                res.Add(i);
        return res;
    }
}