はじめに
「会社で業務の傍ら採用のお手伝いをしているけど、あんまり募集進んでない・・・いいアピールの方法ないかな？」
と思っていたところ、日頃お世話になっているQiitaで面白そうなキャンペーンを見つけて、
「これ使えないかな？」
と試験的に投稿してみることにしました。所属企業を公開されてる方たちもいるしね。
決してApple Watchがほしいわけではありません。うん。
問題を見てみて、「ハノイの塔がAかー、このくらいのランクならなんとか解けそうかな？」
ということで、チャレンジしてみました。言語はC#です。
それではどうぞ。
お菓子の詰め合わせ（初回提出)
考え方
条件は以下3つ。
・商品は種類ごとに1つしか買うことはできない
・与えられた金額でできるだけ多くの商品を買うこと
・商品の個数が同じであれば、できるだけおつりが少なくなるように買うこと
解法は以下のように考えた。
- 商品を安い順から買えるだけ買う ( = できるだけ多くの商品を買うことが可能)
- 買った商品とそれ以外のより高い商品を比較し、差額が予算内に納まれば商品を交換する( = できるだけ高い商品を買い、おつりを少なくする）
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static void Main()
{
// 1行目(種類, 総額)の取得
var line1 = Console.ReadLine().Split(' ');
var kind = int.Parse(line1[0]);
var amount = int.Parse(line1[1]);
// 2行目以降(商品)の取得
var products = new List<int>();
for (int ii = 0; ii < kind; ++ii)
{
products.Add(int.Parse(Console.ReadLine()));
}
// 昇順ソート必須
products.Sort();
//最少額の商品から限界まで購入する(購入可能な種類数を求める)
var boughtList = new List<int>();
foreach (var product in products)
{
if ((boughtList.Sum() + product) > amount) { break; }
boughtList.Add(product);
}
// 購入した商品から、残金の範囲でできるだけ高い金額の商品と交換する
for (int ii = 0; ii < boughtList.Count; ++ii)
{
var preOrder = -1;
foreach (var product in products)
{
// すでに購入していた商品は除く
if (boughtList.Contains(product)) { continue; }
// 購入した商品より高額、かつ総額の範囲に納まる商品を探す
if ( (product > boughtList[ii]) &&
(boughtList.Sum() + (product - boughtList[ii]) <= amount) )
{
// 交換可能な商品を仮押さえしておき、差額の大きい商品があれば更新する
preOrder = product;
}
}
// できるだけ差額の大きい商品と交換する
if (preOrder >= 0) { boughtList[ii] = preOrder; }
}
// 購入した商品の残額を出力する
Console.WriteLine(amount - boughtList.Sum());
}
}
結果（初回提出)
foreachしてるコレクションをループ中に変更するなんてダメだろ、とコンパイラ様にマサカリを投げられる恐怖を抱えつつ、まあ通ったしええやろの精神で提出。
赤点の予感を感じつつテストを提出した気分でした。
結果は・・・
思ったよりいい。
1パターン通らなかったらしく、しっくりこないので確認する
気づき
「これ結局、総当たり必要じゃね？」
そう、最もお釣りの少なくなる組み合わせが欲しいのであって、それは必ずしも高い商品ではないのだ。（とても高い商品と安い商品のパターンもあれば、すべてそこそこ高い商品のパターンもある）
ひとつずつ交換していたのでは正しい答えは得られない。
「いい考えだと思ったのになぁ」とうなだれつつ、コードを修正する。まるで現実のようだ
最終提出
解法1. の「商品を安い順から買えるだけ買う」の部分に関しては正しいはずなので、商品の個数は求められた前提でコードを修正した。
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static void Main()
{
// 1行目(種類, 総額)の取得
var line1 = Console.ReadLine().Split(' ');
var kind = int.Parse(line1[0]);
var amount = int.Parse(line1[1]);
// 2行目以降(商品)の取得
var products = new List<int>();
for (int ii = 0; ii < kind; ++ii)
{
products.Add(int.Parse(Console.ReadLine()));
}
// 昇順ソート必須
products.Sort();
//最少額の商品から限界まで購入する(購入可能な種類数を求める)
var boughtList = new List<int>();
foreach (var product in products)
{
if ((boughtList.Sum() + product) > amount) { break; }
boughtList.Add(product);
}
// 修正部分
var productCount = boughtList.Count;
boughtList.Clear();
var sum = ChoiseProducts(products, productCount, amount);
// 購入した商品の残額を出力する
Console.WriteLine(amount - sum);
}
// 再帰関数を追加
public static int ChoiseProducts(List<int> productList, int productCount, int amount, int oldSum = 0, int sum = 0)
{
--productCount;
foreach (var product in productList)
{
// 商品を買う
sum += product;
// 最大個数の商品を買うまで繰り返す
if (productCount > 0)
{
// 購入した商品を除いて他の商品をチョイスする
var copyProductList = new List<int>(productList);
copyProductList.Remove(product);
oldSum = ChoiseProducts(copyProductList, productCount, amount, oldSum, sum);
}
// よりお釣りの少ない組み合わせが見つかったら合計を更新する
if ((productCount == 0) && (sum <= amount) && (sum > oldSum))
{
oldSum = sum;
}
sum -= product;
}
return oldSum;
}
}
なんか、コレジャナイ感。。。
うまぶって再帰関数にしたけれどわかりにくい。あとコレクションのコピーが重い。
そもそも早さを求める人はC#は使わないだろうが
まぁ愚直に作るとN次の繰り返しになるので仕方ないね。次元を減らさない限り。
なにはともあれ、100点をいただくことができました。やったぜ。
おわりに
ちょっと時間がかかってしまいましたが、解くことができました。
頭のトレーニングにはちょうどいいですね。
次はオブジェクト指向的にモデリングしてみても面白いかも。。なんて。
以上です。
※初投稿のため、気になった点・マサカリがあれば教えていただけると幸いです。