こちらではpaiza事務局側で作成した模範解答を掲載していす。
C#: paiza事務局作成コード Vol.2 動的計画法
得点：100点
通過テストケース：7/7
using System;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections;
using System.Diagnostics;
using System.Collections.Generic;
public class ClassName
{
public static void Main()
{
int m = int.Parse(Console.ReadLine());
int n = int.Parse(Console.ReadLine());
int sum_q = 0;
int sum_r = 0;
List<int[]> qr = new List<int[]>();
for (int i = 0; i < n; i++)
{
string[] tmp = Console.ReadLine().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
int q = int.Parse(tmp[0]);
int r = int.Parse(tmp[1]);
qr.Add(new int[] { q, r });
sum_q += q;
sum_r += r;
}
int dp_m = sum_q - m;
int[] dp = new int[dp_m + 1];
for (int i = 0; i < qr.Count; i++)
{
int q = qr[i][0];
int r = qr[i][1];
for (int j = dp.Length - 1; j >= q; j--)
{
dp[j] = Math.Max(dp[j], dp[j - q] + r);
}
}
Console.WriteLine(sum_r - dp[dp_m]);
}
}
C#: paiza事務局作成コード Vol.1 O(2^n)
得点：71点
通過テストケース：5/7
using System;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections;
using System.Diagnostics;
using System.Collections.Generic;
public class ClassName
{
public static void Main()
{
int m = int.Parse(Console.ReadLine());
int n = int.Parse(Console.ReadLine());
List<int[]> qr = new List<int[]>();
for (int i = 0; i < n; i++)
{
string line = Console.ReadLine();
string[] tmp = line.Split(' ');
qr.Add(new int[] { int.Parse(tmp[0]), int.Parse(tmp[1]) });
}
//m社のうちi番目の会社を使うか使わないかの表を作る
//3社とかなら
// A, B, C
// 1, 1, 1
// 1, 1, 0
// 1, 0, 1
//.....続く...
//みたいな1を使う0は使わないの表を作る
List<int[]> use_list = new List<int[]>();
//2進数で考えると
for (int i = 0; i < (1 << n); i++)
{
int[] array = new int[n];
for (int j = 0; j < n; j++)
{
array[j] = (i >> j & 1);
}
use_list.Add(array);
}
//使う使わないリストから、人月を満たせる組み合わせで最安を探す
int ans = 0;
for (int i = 0; i < qr.Count; i++)
{
ans += qr[i][1];
}
for (int i = 0; i < use_list.Count; i++)
{
int cost = 0;
int ningetsu = 0;
for (int j = 0; j < use_list[i].Length; j++)
{
if (use_list[i][j] == 1)
{
ningetsu += qr[j][0];
cost += qr[j][1];
}
}
if (ningetsu >= m && ans > cost)
{
ans = cost;
}
}
Console.WriteLine(ans);
}
}
