TopCoder SRM 588: GUMIAndSongsDiv2

問題文

Div1 とは違って、|songs| が 15以下なので全探索で通る。

無理にLINQを使うとより複雑になる一例。

public class GUMIAndSongsDiv2 {
    IEnumerable<int> GetBitIndice(long n)
    {
        int index = 0;
        var list = new List<int>();
        while (n > 0)
        {
            if ((n & 1) != 0) list.Add(index);
            index++;
            n /= 2;
        }
        return list;
    }

    public int maxSongs(int[] duration, int[] tone, int T)
    {
        int n = duration.Length;

        var songs = Enumerable.Range(0, n)
            .Select(index => new { duration = duration[index], tone = tone[index] })
            .OrderBy(s => s.tone)
            .ToArray();

        return Enumerable.Range(1, (1 << n) - 1)
            .Select(group => GetBitIndice(group).Select(index => songs[index]).ToArray())
            .Where(selectedSongs =>
                selectedSongs.Sum(s => s.duration) + selectedSongs.Last().tone - selectedSongs.First().tone <= T)
            .Select(selectedSongs => selectedSongs.Count())
            .DefaultIfEmpty(0)
            .Max();
    }
}