uzutaka's notes

web系ソフトウェア開発,プログラミングなどについてまとめます.

TopCoder SRM 588 DIV 1 EASY GUMIAndSongs をC#で解く

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Linq;

public class GUMIAndSongsDiv1
{
    public const int Inf = int.MaxValue / 2;

    public struct Pair :IComparable<Pair>
    {
        public int duration;
        public int tone;

        public Pair(int duration, int tone)
        {
            this.duration = duration;
            this.tone = tone;
        }

        public int CompareTo(Pair other)
        {
            if (this.tone < other.tone)
            {
                return -1;
            }
            else if (this.tone > other.tone)
            {
                return 1;
            }
            else
            {
                return this.duration - other.duration;
            }
        }
    }

    public int maxSongs(int[] duration, int[] tone, int T)
    {
        int N = tone.Length;
        
        Array.Sort(tone, duration);
        
        int[,] dp = new int[N + 1, N + 1];
        
        for (int i = 0; i <= N; i++)
        {
            for (int j = 0; j <= N; j++)
            {
                dp[i, j] = Inf;
            }
        }
        for (int j = 0; j < N; j++)
        {
            dp[1, j] = duration[j];
        }
        
        for (int i = 1; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                for (int k = 0; k < j; k++)
                {
                    if (dp[i, j] != Inf)
                    {
                        dp[i + 1, j] = Math.Min(dp[i + 1, j], dp[i, k] + Math.Abs(tone[j] - tone[k]) + duration[j]);
                    }
                }
            }
        }
        
        int res = 0;
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (dp[i + 1, j] <= T)
                {
                    res = Math.Max(res, i + 1);
                }
            }
        }
        
        return res;
    }

    // BEGIN CUT HERE
    public void run_test(int Case)
    {
        if ((Case == -1) || (Case == 0))
            test_case_0();
        if ((Case == -1) || (Case == 1))
            test_case_1();
        if ((Case == -1) || (Case == 2))
            test_case_2();
        if ((Case == -1) || (Case == 3))
            test_case_3();
        if ((Case == -1) || (Case == 4))
            test_case_4();
    }

    void verify_case(int Case, int Expected, int Received)
    {
        Console.Write("Test Case #" + Case + "...");
        if (Expected == Received)
            Console.Write("PASSED\n");
        else
        {
            Console.Write("FAILED\n");
            Console.Write("\tExpected: \"" + Expected + "\"\n");
            Console.Write("\tReceived: \"" + Received + "\"\n");
        }
    }

    private void test_case_0()
    {
        int[] Arg0 = { 3, 5, 4, 11 };
        int[] Arg1 = { 2, 1, 3, 1 };
        int Arg2 = 17;
        int Arg3 = 3;
        verify_case(0, Arg3, maxSongs(Arg0, Arg1, Arg2));
    }

    private void test_case_1()
    {
        int[] Arg0 = { 100, 200, 300 };
        int[] Arg1 = { 1, 2, 3 };
        int Arg2 = 99;
        int Arg3 = 0;
        verify_case(1, Arg3, maxSongs(Arg0, Arg1, Arg2));
    }

    private void test_case_2()
    {
        int[] Arg0 = { 1, 2, 3, 4 };
        int[] Arg1 = { 1, 1, 1, 1 };
        int Arg2 = 100;
        int Arg3 = 4;
        verify_case(2, Arg3, maxSongs(Arg0, Arg1, Arg2));
    }

    private void test_case_3()
    {
        int[] Arg0 = { 9, 11, 13, 17 };
        int[] Arg1 = { 2, 1, 3, 4 };
        int Arg2 = 20;
        int Arg3 = 1;
        verify_case(3, Arg3, maxSongs(Arg0, Arg1, Arg2));
    }

    private void test_case_4()
    {
        int[] Arg0 =
        {87, 21, 20, 73, 97, 57, 12, 80, 86, 97, 98, 85, 41, 12, 89, 15, 41, 17, 68, 37, 21, 1, 9, 65, 4,
            67, 38, 91, 46, 82, 7, 98, 21, 70, 99, 41, 21, 65, 11, 1, 8, 12, 77, 62, 52, 69, 56, 33, 98, 97
        };
        int[] Arg1 =
        {88, 27, 89, 2, 96, 32, 4, 93, 89, 50, 58, 70, 15, 48, 31, 2, 27, 20, 31, 3, 23, 86, 69, 12, 59,
            61, 85, 67, 77, 34, 29, 3, 75, 42, 50, 37, 56, 45, 51, 68, 89, 17, 4, 47, 9, 14, 29, 59, 43, 3
        };
        int Arg2 = 212;
        int Arg3 = 12;
        verify_case(4, Arg3, maxSongs(Arg0, Arg1, Arg2));
    }
    // END CUT HERE


    // BEGIN CUT HERE
    public static void Main()
    {
        try
        {
            GUMIAndSongsDiv1 ___test = new GUMIAndSongsDiv1();
            ___test.run_test(-1);
        }
        catch (Exception e)
        {
            // Console.WriteLine(e.StackTrace);
            Console.WriteLine(e.ToString());
        }
    }
    // END CUT HERE
}