【プログラミングコンテスト】AtCoder Beginner Contest 119③
花粉症における耳鼻科の薬の偉大さを知りました、ねむーです。
今回はAtCoder(https://atcoder.jp/contests/abc119)にて開催されました、AtCoder Beginner Contest 119の第3回目です。
今回は、第3問「C - Synthetic Kadomatsu」の問題と僕との戦闘記です。
0.はじめに
1.問題文
あなたは N 本の竹を持っています(Nは8以下)。これらの長さはそれぞれ l 1 , l 2 , . . . , l N です (単位: センチメートル)。
あなたの目的は、これらの竹のうち何本か (全部でもよい) を使い、長さが A , B , C であるような 3 本の竹を得ることです。そのために、以下の三種類の魔法を任意の順に何度でも使うことができます。
延長魔法: 1 MP (マジックポイント) を消費し、 1 本の竹を選んでその長さを 1 増やす。
短縮魔法: 1 MP を消費し、 1 本の長さ 2 以上の竹を選んでその長さを 1 減らす。
合成魔法: 10 MP を消費し、 2 本の竹を選んで接続し 1 本の竹とする。この新たな竹の長さは接続した 2 本の竹の長さの合計に等しい。(以後、この竹に対してさらに魔法を使用することもできる。) 目的を達成するには、最小でいくつの MP が必要でしょうか？
2.入力例
5 100 90 80 98 40 30 21 80
出力
23
長さ 98 , 40 , 30 , 21 , 80 の 5 本の竹から長さ 100 , 90 , 80 の 3 本の竹を得ようとしています。長さ 80 の竹ははじめから持っており、長さ 100 , 90 の竹は次のように魔法を使うと合計 23 MP を消費することで得られ、これが最適です。
長さ 98 の竹に延長魔法を 2 回使い、長さ 100 の竹を得る。(消費 MP: 2 )
長さ 40 , 30 の竹に合成魔法を使い、長さ 70 の竹を得る。(消費 MP: 10 )
長さ 21 の竹に短縮魔法を 1 回使い、長さ 20 の竹を得る。(消費 MP: 1 )
手順 2. で得た長さ 70 の竹と手順 3. で得た長さ 20 の竹に合成魔法を使い、長さ 90 の竹を得る。(消費 MP: 10 )
3.初見の感想
- 入力と同じ長さの竹があれば、その竹を使用すべき
- 短縮は1ずつ下げるしか方法がないので、下げる必要がある時は優先的に竹を確保すべき
- どれとどれを合成したらいいのか目星の付け方がわからん
- うまく実装方法が思いつかない
4.他の人のコードを読んだりしてじっくり考えた感想
- 合成さえしなければ簡単な問題
→合成フェイズと伸縮フェイズに問題を切り分ける！
先に竹たちを合成しちゃいます
- どの竹を選ぶのかという問題ではない
「Aに使用する竹を選ぶ」のではなく、「1番目の竹は(Aに使う,Bに使う,Cに使う,使わない)の中から選ぶ」という考え方を行います
選択肢は少ない方がよいという鉄則を学べました。
- どう全パターンを試すのか
①ＤＦＳ（深さ優先探索木）
①番目の木はAに使う…②番目の木は使わない…といった情報は下の図のような木構造にするやり方です
それぞれの深さで行う処理は共通なので再帰的にコードを書くのがよさそうですね。
②16bitの数字を8つに分割して2bitずつ使う
(Aに使う,Bに使う,Cに使う,使わない)をそれぞれ01,10,11,00と割り当てると、例えば８つの組み合わせは、
左から順に00/01/10/11/11/10/10/00に表せる表示方法です。
今回は①の手法を使いました。
5.コードの簡単な解説
- まず、入力の値のパースを行う
string[] temp = System.Console.ReadLine().Split(' ');
N = int.Parse(temp[0]);
A = int.Parse(temp[1]);
B = int.Parse(temp[2]);
C = int.Parse(temp[3]);
bmp = new int[N];
for (int i = 0; i < N; i++)
{
bmp[i]=(int.Parse(System.Console.ReadLine()));
}
- 再帰関数の作り方
今回はSolve()関数を再帰させようと思います
具体的には選択肢となる竹の数分、再帰を回して竹を合成し、その合成結果をリストに投入する形にしました！
問題で指定された竹と合成結果との差が最小になる組み合わせを選べばそれが正しい組み合わせとなります！
static int Solve(int current, int a, int b, int c)
{
List<int> list = new List<int>();
list.Add(Solve(current + 1, a, b, c));
list.Add(Solve(current + 1, a + bmp[current], b, c) + 10);
list.Add(Solve(current + 1, a, b + bmp[current], c) + 10);
list.Add(Solve(current + 1, a, b, c + bmp[current]) + 10);
list.Sort();
return list.First();
}
- 後は目標の竹の長さまでの差を埋める分のMP消費を計算します
if (current == N)
{
List<int> tmp = new List<int>();
tmp.Add(a);
tmp.Add(b);
tmp.Add(c);
tmp.Sort();
if (tmp.First() > 0)
{
return Math.Abs(A - a) + Math.Abs(B - b) + Math.Abs(C - c) - 30;
}
else
{
return INF;
}
}
6.全コード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ABC119C
{
class Program
{
static int N;
static int A;
static int B;
static int C;
static int[] data;
static int INF = (int)Math.Pow(10, 9);
static int[] bmp;
static int Solve(int current, int a, int b, int c)
{
if (current == N)
{
List<int> tmp = new List<int>();
tmp.Add(a);
tmp.Add(b);
tmp.Add(c);
tmp.Sort();
if (tmp.First() > 0)
{
return Math.Abs(A - a) + Math.Abs(B - b) + Math.Abs(C - c) - 30;
}
else
{
return INF;
}
}
List<int> list = new List<int>();
list.Add(Solve(current + 1, a, b, c));
list.Add(Solve(current + 1, a + bmp[current], b, c) + 10);
list.Add(Solve(current + 1, a, b + bmp[current], c) + 10);
list.Add(Solve(current + 1, a, b, c + bmp[current]) + 10);
list.Sort();
return list.First();
}
static void Main(string[] args)
{
string[] temp = System.Console.ReadLine().Split(' ');
N = int.Parse(temp[0]);
A = int.Parse(temp[1]);
B = int.Parse(temp[2]);
C = int.Parse(temp[3]);
bmp = new int[N];
for (int i = 0; i < N; i++)
{
bmp[i]=(int.Parse(System.Console.ReadLine()));
}
Console.WriteLine(Solve(0, 0, 0, 0));
}
}
}
7.最後に
問題の切り分けが難しい問題でしたね～
問題を新しい方向で見ることを学べました！
