トップページに戻る
次の競技プログラミングの問題へ
前の競技プログラミングの問題へ
No.15 カタログショッピング
■■■問題■■■
太郎君はカタログショッピングが大好き。
今日もカタログから商品を選んで購入したのだが、
太郎君はとてもお金持ちなので適当に商品を選んでしまい、
何を購入したかいつも忘れてしまいます。
幸い、クレジットカードの明細は手元にあるので、
購入した合計金額だけはわかりました。
太郎君が何を購入したのかを計算し、その商品番号を太郎君に教えてあげてください。
ただし、一つの商品を複数買うことはないものとします。
■■■入力■■■
N S
P1
P2
・
・
・
PN
1行目に、カタログに載っている商品の数を表す整数N (1 <= N <= 31)と、
購入した合計金額を表す整数S (1 <= S <= 310000000)がスペース区切りで与えられる。
続くN行に、商品番号i (1 <= i <= N) の価格を表す整数Pi (1 <= Pi <= 10000000)が与えられる。
■■■出力■■■
購入した商品の商品番号を1行に、昇順で、1つのスペース区切りで出力してください。
行の最後に改行してください。
購入した商品の組み合わせが複数あり得る場合、昇順となるようすべて出力してください。
(組み合わせ内で、より小さい商品番号が先に来る組み合わせを先に出力してください。
出力例はsample4,sample5を参照)
出力が50行以上になるような入力が与えられることはありません。
C#のソース
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "Input2";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("3 220");
WillReturn.Add("180");
WillReturn.Add("220");
WillReturn.Add("280");
//2
//太郎君は3つの商品の中から、2番の商品だけを購入しました
}
else if (InputPattern == "Input2") {
WillReturn.Add("5 150");
WillReturn.Add("10");
WillReturn.Add("30");
WillReturn.Add("40");
WillReturn.Add("20");
WillReturn.Add("50");
//1 2 3 4 5
//太郎君は5つの商品をすべて購入しました
}
else if (InputPattern == "Input3") {
WillReturn.Add("12 348940");
WillReturn.Add("47250");
WillReturn.Add("76500");
WillReturn.Add("9520");
WillReturn.Add("29960");
WillReturn.Add("19520");
WillReturn.Add("70960");
WillReturn.Add("91390");
WillReturn.Add("35610");
WillReturn.Add("71190");
WillReturn.Add("25840");
WillReturn.Add("10150");
WillReturn.Add("35000");
//2 3 4 6 7 8 12
}
else if (InputPattern == "Input4") {
WillReturn.Add("15 445566");
WillReturn.Add("13075");
WillReturn.Add("16966");
WillReturn.Add("20695");
WillReturn.Add("21052");
WillReturn.Add("25917");
WillReturn.Add("25917");
WillReturn.Add("28431");
WillReturn.Add("31001");
WillReturn.Add("44064");
WillReturn.Add("47151");
WillReturn.Add("59372");
WillReturn.Add("63934");
WillReturn.Add("63934");
WillReturn.Add("66757");
WillReturn.Add("88888");
//4 5 7 9 10 11 12 14 15
//4 5 7 9 10 11 13 14 15
//4 6 7 9 10 11 12 14 15
//4 6 7 9 10 11 13 14 15
//同じ値段の商品が複数存在する場合があります。
//あり得る4つの組み合わせを、昇順に出力してください。
}
else if (InputPattern == "Input5") {
WillReturn.Add("4 20000");
WillReturn.Add("10000");
WillReturn.Add("10000");
WillReturn.Add("10000");
WillReturn.Add("10000");
//1 2
//1 3
//1 4
//2 3
//2 4
//3 4
//すべて同じ値段なので、どれか2つを購入したようです。
//あり得る6つの組み合わせをすべて出力してください。
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
struct JyoutaiDef
{
internal int CurrP;
internal int SumPrice;
internal List<int> SelectedIDList;
}
struct SyouhinDef
{
internal int ID;
internal int Price;
}
static int S;
static void Main()
{
List<string> InputList = GetInputList();
S = int.Parse(InputList[0].Split(' ').Last());
var SyouhinList = new List<SyouhinDef>();
int wkID = 1;
foreach (string EachStr in InputList.Skip(1)) {
SyouhinDef WillAdd;
WillAdd.ID = wkID++;
WillAdd.Price = int.Parse(EachStr);
SyouhinList.Add(WillAdd);
}
//合計金額より価格の高い商品をRemove
SyouhinList.RemoveAll(X => X.Price > S);
//価格の昇順の配列に変換しておく
SyouhinDef[] SyouhinArr =
SyouhinList.OrderBy(X => X.Price).ThenBy(X => X.ID).ToArray();
//半分全探索を行う
JyoutaiDef[] JyoutaiArrZenhan = { };
JyoutaiDef[] JyoutaiArrKouhan = { };
int UB = SyouhinArr.GetUpperBound(0);
int HalfUB = UB / 2;
if (0 < HalfUB && HalfUB < UB) {
JyoutaiArrZenhan = ExecHanbunZentansaku(SyouhinArr, 0, HalfUB);
JyoutaiArrKouhan = ExecHanbunZentansaku(SyouhinArr, HalfUB + 1, UB);
}
else {
JyoutaiArrZenhan = ExecHanbunZentansaku(SyouhinArr, 0, UB);
}
//デバッグ用で半分全探索の結果を出力
ProntResultHanbunZentansaku(JyoutaiArrZenhan, JyoutaiArrKouhan);
//半分全探索の前半部と後半部を使って解判定を行う
AnswerHantei(JyoutaiArrZenhan, JyoutaiArrKouhan);
}
//半分全探索を行う
static JyoutaiDef[] ExecHanbunZentansaku(SyouhinDef[] pSyouhinArr, int pStaInd, int pEndInd)
{
var WillReturn = new List<JyoutaiDef>();
var stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
for (int I = pStaInd; I <= pEndInd; I++) {
WillPush.CurrP = I;
WillPush.SelectedIDList = new List<int>() { pSyouhinArr[I].ID };
WillPush.SumPrice = pSyouhinArr[I].Price;
stk.Push(WillPush);
}
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
WillReturn.Add(Popped);
for (int I = Popped.CurrP + 1; I <= pEndInd; I++) {
WillPush.CurrP = I;
WillPush.SumPrice = Popped.SumPrice + pSyouhinArr[I].Price;
//合計金額を超えるならbreak
if (S < WillPush.SumPrice) break;
WillPush.SelectedIDList = new List<int>(Popped.SelectedIDList);
WillPush.SelectedIDList.Add(pSyouhinArr[I].ID);
stk.Push(WillPush);
}
}
return WillReturn.ToArray();
}
//デバッグ用で半分全探索の結果を出力
static void ProntResultHanbunZentansaku(JyoutaiDef[] pJyoutaiArrZenhan, JyoutaiDef[] pJyoutaiArrKouhan)
{
Console.WriteLine("■■■前半部■■■");
for (int I = 0; I <= pJyoutaiArrZenhan.GetUpperBound(0); I++) {
var sb = new System.Text.StringBuilder();
sb.AppendFormat("SumPrice={0}", pJyoutaiArrZenhan[I].SumPrice);
sb.Append(" IDList=");
foreach (int EachInt in pJyoutaiArrZenhan[I].SelectedIDList) {
sb.AppendFormat("{0},", EachInt);
}
Console.WriteLine(sb.ToString());
}
if (pJyoutaiArrKouhan.Length > 0) Console.WriteLine("■■■後半部■■■");
for (int I = 0; I <= pJyoutaiArrKouhan.GetUpperBound(0); I++) {
var sb = new System.Text.StringBuilder();
sb.AppendFormat("SumPrice={0}", pJyoutaiArrKouhan[I].SumPrice);
sb.Append(" IDList=");
foreach (int EachInt in pJyoutaiArrKouhan[I].SelectedIDList) {
sb.AppendFormat("{0},", EachInt);
}
Console.WriteLine(sb.ToString());
}
Console.WriteLine();
}
//半分全探索の前半部と後半部を使って解判定を行う
static void AnswerHantei(JyoutaiDef[] pJyoutaiArrZenhan, JyoutaiDef[] pJyoutaiArrKouhan)
{
//価格の合計の昇順にソートしておく
Array.Sort(pJyoutaiArrZenhan, (A, B) => A.SumPrice - B.SumPrice);
Array.Sort(pJyoutaiArrKouhan, (A, B) => A.SumPrice - B.SumPrice);
var AnswerList = new List<int[]>();
//前半部だけで解だった場合
for (int I = 0; I <= pJyoutaiArrZenhan.GetUpperBound(0); I++) {
if (pJyoutaiArrZenhan[I].SumPrice == S)
AnswerList.Add(pJyoutaiArrZenhan[I].SelectedIDList.OrderBy(X => X).ToArray());
}
//後半部だけで解だった場合
for (int I = 0; I <= pJyoutaiArrKouhan.GetUpperBound(0); I++) {
if (pJyoutaiArrKouhan[I].SumPrice == S)
AnswerList.Add(pJyoutaiArrKouhan[I].SelectedIDList.OrderBy(X => X).ToArray());
}
//後半部のSumPriceごとの開始IndのDict
var StartIndDict = new Dictionary<int, int>();
for (int I = 0; I <= pJyoutaiArrKouhan.GetUpperBound(0); I++) {
int wkSum = pJyoutaiArrKouhan[I].SumPrice;
if (StartIndDict.ContainsKey(wkSum)) continue;
StartIndDict[wkSum] = I;
}
for (int I = 0; I <= pJyoutaiArrZenhan.GetUpperBound(0); I++) {
int NeedSum = S - pJyoutaiArrZenhan[I].SumPrice;
if (StartIndDict.ContainsKey(NeedSum) == false) continue;
int StartInd = StartIndDict[NeedSum];
for (int J = StartInd; J <= pJyoutaiArrKouhan.GetUpperBound(0); J++) {
int wkSum = pJyoutaiArrZenhan[I].SumPrice + pJyoutaiArrKouhan[J].SumPrice;
if (wkSum > S) break;
if (wkSum < S) continue;
var wkList = new List<int>();
wkList.AddRange(pJyoutaiArrZenhan[I].SelectedIDList);
wkList.AddRange(pJyoutaiArrKouhan[J].SelectedIDList);
wkList.Sort();
AnswerList.Add(wkList.ToArray());
}
}
PrintAnswer(AnswerList);
}
//解を出力
static void PrintAnswer(List<int[]> pAnswerList)
{
pAnswerList.Sort((A, B) =>
{
int MaxUB = Math.Max(A.GetUpperBound(0), B.GetUpperBound(0));
for (int I = 0; I <= MaxUB; I++) {
if (I > A.GetUpperBound(0)) return -1;
if (I > B.GetUpperBound(0)) return 1;
if (A[I] > B[I]) return 1;
if (A[I] < B[I]) return -1;
}
return 0;
});
foreach (int[] EachIntArr in pAnswerList) {
var sb = new System.Text.StringBuilder();
for (int I = 0; I <= EachIntArr.GetUpperBound(0); I++) {
sb.Append(EachIntArr[I]);
if (I < EachIntArr.GetUpperBound(0))
sb.Append(' ');
}
Console.WriteLine(sb.ToString());
}
}
}
デバッグ情報付の実行結果
■■■前半部■■■
SumPrice=30 IDList=2,
SumPrice=20 IDList=4,
SumPrice=50 IDList=4,2,
SumPrice=10 IDList=1,
SumPrice=40 IDList=1,2,
SumPrice=30 IDList=1,4,
SumPrice=60 IDList=1,4,2,
■■■後半部■■■
SumPrice=50 IDList=5,
SumPrice=40 IDList=3,
SumPrice=90 IDList=3,5,
1 2 3 4 5
解説
半分全探索のアルゴリズムを使ってます。