D - Match Matching
はじめに
競技プログラミング、AtCoder Beginner Contest 118
D - Match Matching
言語はC#
何かあればTwitter→@pirorirori_n712まで
問題
問題文
ちょうどN本のマッチ棒を使って作れる整数の中で最大のものを求めてください。 ただし、以下の条件を満たさなければなりません。 ・作る整数の各桁は、1から9までの数字のうちA1,A2,...,AM(1≤Ai≤9)のいずれかでなければならない。 ・数字1,2,3,4,5,6,7,8,9を1つ作るには、それぞれちょうど2,5,5,4,5,6,3,7,6本のマッチ棒を使う。
制約
・入力は全て整数である。 ・2≤N≤104 ・1≤M≤9 ・1≤Ai≤9 ・Aiは全て異なる。 ・ちょうどN本のマッチ棒を使って条件を満たすように作れる整数が存在する。
入力
入力は以下の形式で標準入力から与えられる。 N M A1 A2 ... AM
出力
問題文の条件下でちょうどN本のマッチ棒を使って作れる整数の最大値を出力せよ。
解き方
こちらの解き方を参考にしています。
goo.gl
まず、
この問題で出す答えは
「問題文の条件下でちょうどN本のマッチ棒を使って作れる整数の最大値」
なので、
整数を最大化する条件を考えます。
整数をなるべく大きくするためには、
まず桁数を大きくすることが必要です。
そして、
大きい桁に大きい数字をおけば
数は大きくなります。
ここから、
この問題の答えを出すには
以下の二つの条件があることが分かります。
・与えられた条件下でなるべく桁を多くすること
・大きい桁には大きい数字を置くこと
上の二つを念頭に置いて、実装を考えます。
すると、以下の2ステップになります。
・動的計画法でマッチ棒を○本使ったときに、最大で×桁作れることを割り出す
→桁数の最大化
・上で出した桁数をもとに、マッチ棒で作れる適当な数字を作る
→大きい桁に大きい数字を配置する
実装を順番に見ていきます。
✩動的計画法でマッチ棒を○本使ったときに、
最大で×桁作れることを割り出す
まず、dpの配列のかたちは以下のようになります。
dp[i]=マッチ棒 i 本で作れる最大桁数
dpの配列の大きさは
マッチ棒0～N本のときの桁数の情報が欲しいので
N+1（0～N）とします。
//dp用の配列 var dp = new int[N+1];
コードを見ながら解説していきます。
使用できる数字と、その数字で使用するマッチ棒の本数は以下のようにしています。
//使える数字
var A= Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).OrderByDescending(x=>x).ToArray();
//それぞれの数字で使用するマッチの本数（index+1=数字）
var cost = new int[] { 2,5,5,4,5,6,3,7,6};
動的計画法の部分は以下です。
//マッチ棒を0本使用してできる桁はないので、0を入れる
dp[0] = 0;
//dpの配列にintの最小の数を入れる（inde=0以外）
for (int i = 1; i <= N; ++i) dp[i] = int.MinValue;
//動的計画法
//マッチ棒をdpのindexぶん、使ったときにできる最大桁数を求める
for (int i=0;i<=N;++i)
{
if (i != 0 && dp[i] == int.MinValue) continue;
for (int j=0;j<M;++j)
{
if (N < i + cost[A[j] - 1]) continue;
dp[i+cost[A[j] - 1]] = dp[i]+1;
}
}
0. 準備
使用できる数字と、数字を作るのにかかるマッチ棒の本数を使える状態にします。
//使える数字
var A= Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).OrderBy(x=>x).ToArray();
//それぞれの数字で使用するマッチの本数（index+1=数字）
var cost = new int[] { 2,5,5,4,5,6,3,7,6};
「使える数字の配列」(A[M])は大きい順にしていますが、
これは動的計画法ではなく
その後の、
最終的にマッチ棒で作ることのできる数字を出す（問題の答え）
ときのために並び替えを行っています。
「それぞれの数字で使用するマッチの本数の配列」(cost[9])は、
1から9までの数字で、必要となるマッチ棒の本数を順番に入れています。
数字からマッチ棒のコストを取り出したいときは
数字から1引いた数を添え字にします。
//1 //数字1で使用するマッチ棒の本数は2 cost[1-1/*=0*/]=2; //7 //数字7で使用するマッチ棒の本数は3 cost[7-1/*=6*/]=3;
1. dp配列の始点に「0」を入れる
マッチ棒0本で作れる数字はないので、
dp[0]に0を代入します。
ここが、動的計画法の始点になります。
//マッチ棒を0本使用してできる桁はないので、0を入れる dp[0] = 0;
2. dp配列の準備
dpの0以外のindexにint.MinValueを代入します。
これは、
後で配列の値が更新されたかどうかを
確認したいので初期値として入れています。
まだここでピンとこなくても、
後でループを回す段になると分かり易くなると思います。
//dpの配列にintの最小の数を入れる（inde=0以外） for (int i = 1; i <= N; ++i) dp[i] = int.MinValue;
3. ループを回してdp配列を埋めていく
以下の部分を見ていきます。
//動的計画法
//マッチ棒をdpのindexぶん、使ったときにできる最大桁数を求める
for (int i=0;i<=N;++i)
{
if (i != 0 && dp[i] == int.MinValue) continue;
for (int j=0;j<M;++j)
{
if (N < i + cost[A[j] - 1]) continue;
dp[i+cost[A[j] - 1]] = dp[i]+1;
}
}
まず、このループの目的は
dp[マッチ棒を使用する本数]=「マッチ棒を使用する本数」で最大何桁の数字が作れるか
を埋めていくことが目的です。
外側のループでは「i」を「N」になるまで1ずつ増やしています。
この「i」はdp配列のindexであり
このdp配列を埋めていく上での基準です。
//動的計画法
//マッチ棒をdpのindexぶん、使ったときにできる最大桁数を求める
for (int i=0;i<=N;++i)
{
//if (i != 0 && dp[i] == int.MinValue) continue;
//for (int j=0;j<M;++j)
//{
// if (N < i + cost[A[j] - 1]) continue;
// dp[i+cost[A[j] - 1]] = dp[i]+1;
//}
}
中の動きを「i」を増やしながら順番に見ていきます。
//動的計画法
//マッチ棒をdpのindexぶん、使ったときにできる最大桁数を求める
for (int i=0;i<=N;++i)
{
if (i != 0 && dp[i] == int.MinValue) continue;
for (int j=0;j<M;++j)
{
if (N < i + cost[A[j] - 1]) continue;
dp[i+cost[A[j] - 1]] = dp[i]+1;
}
}
まず「i==0」のとき
if (i != 0 && dp[i] == int.MinValue) continue;
は条件式に当てはまらないので、そのまま下に進みます。
下に進むと内側のループにあたります。
for (int j=0;j<M;++j)
{
if (N < i + cost[A[j] - 1]) continue;
dp[i+cost[A[j] - 1]] = dp[i]+1;
}
このループでは
外側のループの「i」、
そして使用できる数字を基準として
dp配列の値をうめていくということをしています。
①index「j」
「j」は0～(M-1)までの値を取りますが
これは使用できる数字を一つずつ見るためです。
for (int j=0;j<M;++j){}
②if文
ループ内のif文の条件と
下のdp配列のindexを見ると
中身が同じになっていることに気が付きます。
if (N < i + cost[A[j] - 1]) continue;
dp[i+cost[A[j] - 1]] = dp[i]+1;
上のif文は下のdp配列のindexがエラーにならないように
チェックしているだけなので、
dp配列に値を入れるために存在しているわけではありません。
③dp配列に値を入れる
dp[i+cost[A[j] - 1]] = dp[i]+1;
上の部分で配列に値を入れています。
まず、cost[A[j] - 1]は数字A[j]で使用するマッチの本数です。
A[j]は使用できる具体的な数字なので、
そこから1を引いたindexを
コストに入れると使用するマッチの本数が出てきます。
ここから
dp[i+cost[A[j] - 1]]は
「i」が「0」であることから
dp[使用するマッチの本数] =dp[i]+1;
となることが分かります。
右辺は左辺がdp[i+cost[A[j] - 1]]であることから
「i」本にさらに
使用できる数字のマッチの本数を追加しているので
dp[i]+1となります。
（i=0のときはdp[0]=0なので、全て1になります。）
以上より、
i=0のときdp配列は
使用できる数字とちょうど同じ
マッチ棒の使用本数のdp配列のindexが1になります。
i=1以降の場合
i=1以降の場合にはif文で見ている条件が一つ追加されます。
外側のループの中にある以下のものです。
if (i != 0 && dp[i] == int.MinValue) continue;
これはdp[i]の値が初期値かどうかを見ています。
初期値の場合にはcontinueして処理を飛ばしています。
例えば、
使える数字が3と6だとすると
使えるマッチ棒の数は5と6です。
i=0のときに
dp[5]とdp[6]に1を入れます。
5と6で作れる数字を並べてみると「5,6,10,11,12,15,16,17,18,20…」
となり、
いずれも「5と6」に
「5か6」を足した数しか作れないことが分かります。
「5,6,5+5,5+6,6+6,5+5+5,5+5+6,5+6+6,6+6+6,5+5+5+5…」
ここから
i=0の時点で値が入っていなかったdp配列のindexは
処理をせずに飛ばすということをしています。
i==1以降はこれを繰り返して
dp配列を最後まで埋めていきます。
✩上で出した桁数をもとに、
マッチ棒で作れる適当な数字を作る
コードは以下のようになっています。
//答えを格納する文字列を用意
var ans = string.Empty;
//数字の文字列を作成する
var match = N;
while (0<match)
{
for (int j=0;j<M;++j)
{
if (match - cost[A[j] - 1] < 0) continue;
if (dp[match - cost[A[j] - 1]] == dp[match] -1) {
ans += A[j];
match -= cost[A[j] - 1];
break;
}
}
}
①答えを格納する文字列を用意
出力が64ビット整数型におさまらないので、文字列で答えを入れる変数を用意します。
//答えを格納する文字列を用意 var ans = string.Empty;
②数字の文字列を作る
//数字の文字列を作成する
var match = N;
while (0<match)
{
for (int j=0;j<M;++j)
{
if (match - cost[A[j] - 1] < 0) continue;
if (dp[match - cost[A[j] - 1]] == dp[match] -1) {
ans += A[j];
match -= cost[A[j] - 1];
break;
}
}
}
まず、match=Nを定義していますが
これはマッチの本数です。
マッチをN本使ったときの数字を作りたいので
match=Nとしています。
while文の条件は
数字を答えの文字列に増やすたびに
match(＝使用するマッチ棒の数)を減らしていくので
matchが0以下になるとループが終了するようにしています。
次に、内側のループでは答えの文字列に実際に数字を入れています。
ここでは、一桁ずつ数字を当てはめています。
数字はなるべく大きいものを使いたいですが
一番初めにA[]を大きい順に並び替えているので
「j」を0から順番に当てはめていくと
自然に大きいものから当てはめていっていることになります。
for文の中身を見ていきます。
if (match - cost[A[j] - 1] < 0) continue;
if (dp[match - cost[A[j] - 1]] == dp[match] -1) {
ans += A[j];
match -= cost[A[j] - 1];
break;
}
まず一番初めのif文は
dpのindexが外にでないかどうかを確認しています。
if (match - cost[A[j] - 1] < 0) continue;
if (dp[match - cost[A[j] - 1]] == dp[match] -1) {
次のif文は以下のように変形できます。
dp[match - cost[A[j] - 1]] == dp[match] -1
dp[現在のマッチの本数 - 数字A[j]を作ったときに使用するマッチの本数] == dp[現在のマッチの本数] -1
dp[index]に入っているのは、
マッチ棒index本でできる数字の最大桁数なので
この条件式が成り立てば
A[j]が今追加されるべき数字だということが分かります。
そのあとは、
ansにA[j]を追加して
現在のマッチ棒の本数からA[j]を作るのに使うマッチ棒の本数を引き
また処理を使用できる最大の数から始めるために
breakしています。
これをマッチ棒が0になるまで繰り返せば、
答えの数字の列が出ます。
全体のコード
using System;
using System.Linq;
using System.Collections.Generic;
class Dmondai {
static void Main()
{
var line = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
var N = line[0];
var M = line[1];
//使える数字
var A= Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).OrderByDescending(x=>x).ToArray();
//それぞれの数字で使用するマッチの本数（index+1=数字）
var cost = new int[] { 2,5,5,4,5,6,3,7,6};
//dp用の配列
var dp = new int[N+1];
//マッチ棒を0本使用してできる桁はないので、0を入れる
dp[0] = 0;
//dpの配列にintの最小の数を入れる（inde=0以外）
for (int i = 1; i <= N; ++i) dp[i] = int.MinValue;
//動的計画法
//マッチ棒をdpのindexぶん、使ったときにできる最大桁数を求める
for (int i=0;i<=N;++i)
{
//index確認
if (i != 0 && dp[i] == int.MinValue) continue;
//使用できる数字を一つずつ追加していく
for (int j=0;j<M;++j)
{
if (N < i + cost[A[j] - 1]) continue;
//i本+数字で使用する本数ぶんを足すと、dp[i]+1桁の数字が作れる
dp[i+cost[A[j] - 1]] = dp[i]+1;
}
}
//答えを格納する文字列を用意
var ans = string.Empty;
//数字の文字列を作成する
var match = N;
while (0<match)
{
for (int j=0;j<M;++j)
{
//index確認
if (match - cost[A[j] - 1] < 0) continue;
//現在のマッチの本数から、作る数字で使うマッチ棒の使用本数を引いた、本数で作ることのできる最大桁数と
//現在のマッチ棒で作ることのできる最大桁数-1が同じなら
//その数字を使用する
if (dp[match - cost[A[j] - 1]] == dp[match] -1) {
ans += A[j];
match -= cost[A[j] - 1];
break;
}
}
}
Console.WriteLine(ans);
}
}
