こちらでは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); } }