AtCoder Beginner Contest 099 - C - Strange Bank

C - Strange Bank

https://abc099.contest.atcoder.jp/tasks/abc099_c

 問題概要

Nが与えられる。以下の数を足してNを作るには、最小で何回の操作が必要か

• 1 

• 6 、6²(=36) 、6³(=216) 、…

• 9 、9²(=81) 、9³(=729) 、…

また、同じ数字は何度でも使える

制約

• 1≤N≤100000
• Nは整数

自分の解法

使える数のリストを作り、動的計画法を使いました。

（Nが127の時、空白には-1が入っている）

	0	1	…	10	…	19	…	28	…	37	…	46	…	55	…	64	…	73	…	82	…	91	…	100	…	109	…	118	…	127
81																														0
36																														0
9																														0
6																														0
1																														0

Nから数字をどんどん引いていき、0にする事を目標に考えます。

表の数字は、操作をした回数を表しています。もし空白でなければ、その回数で列の数字が作れる。行の数を何回か使ってNを減らし、0にする最小の回数を求めたい。

空白でなければ、列の数は現状作れるので、そこから行(81とか)を引いた数も作れる。

右端から見ていき、もし同じ行で(上+左)列に数があれば、1足した数を入れる。

値が更新されたら、同列をその数で埋める。（↓は81について考えた時）

	0	1	…	10	…	19	…	28	…	37	…	46	…	55	…	64	…	73	…	82	…	91	…	100	…	109	…	118	…	127
81												1																		0
36												1																		0
9												1																		0
6												1																		0
1												1																		0

36について考えた場合。数字を使う度、数が増える

	0	1	…	10	…	19	…	28	…	37	…	46	…	55	…	64	…	73	…	82	…	91	…	100	…	109	…	118	…	127
81												1																		0
36				2		3						1		2								1								0
9				2		3						1		2								1								0
6				2		3						1		2								1								0
1				2		3						1		2								1								0

数が衝突した場合、少ない方を採用する

	0	1	…	10	…	19	…	28	…	37	…	46	…	55	…	64	…	73	…	82	…	91	…	100	…	109	…	118	…	127
81												1																		0
36				2		3						1		2								1								0
9		3		2		3		3		2		1		2		4		3		2		1		3		2		1		0
6		3		2		3		3		2		1		2		4		3		2		1		3		2		1		0
1	4	3		2		3		3		2		1		2		4		3		2		1		3		2		1		0

上より127から数を引いていき、0を作る最小の操作回数は4だとわかります

Nが最大値のときでも、使える数字は17,8個程度なので計算量はO(10^7)となり間に合います。

import java.io.*;
import java.util.*;

public class Main
{
    static int N;
    static List<Integer> nlist;

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        nlist = new ArrayList<>();
        int i;
        //使える数のリストを作り、ソート
        int n9 = 1, n6 = 1;
        for (i = 0; n9 * 9 <= N; i++)
        {
            n9 *= 9;
            nlist.add(n9);
        }
        for (; n6 * 6 <= N; i++)
        {
            n6 *= 6;
            nlist.add(n6);
        }
        nlist.add(1);
        Collections.sort(nlist, Comparator.reverseOrder());

        /////////////
        int[][] dp = new int[nlist.size()][N + 1];
        fill(dp, -1);
        for (int j = 0; j < nlist.size(); j++)
            dp[j][N] = 0;
        for (i = 0; i < nlist.size(); i++)
        {
            int iva = nlist.get(i);
            for (int ni = N - iva; ni >= 0; ni--)
            {
                if (dp[i][ni + iva] == -1) continue;
                //niが作れる時　
                if (dp[i][ni] == -1)
                {
                    dp[i][ni] = dp[i][ni + iva] + 1;
                }
                else
                {
                    dp[i][ni] = Math.min(dp[i][ni], dp[i][ni + iva] + 1);
                }
                //同列を更新された数で埋める
                for (int j = i + 1; j < nlist.size(); j++)
                {
                    dp[j][ni] = dp[i][ni];
                }
            }
        }
        int res = 1000000;
        for (int j = 0; j < nlist.size(); j++)
        {
            if (dp[j][0] == -1) continue;
            res = Math.min(res, dp[j][0]);
        }

        System.out.println(res);
    }

    static void fill(int[][] a, int v)
    {
        for (int i = 0; i < a.length; i++)
            for (int j = 0; j < a[0].length; j++)
                a[i][j] = v;
    }
}

（追記）

【初級者競プロer向け】動的計画法（DP）を見て、改良しました

package com.company;

import java.io.*;
import java.util.*;

public class Main
{
    static int N;
    static List<Integer> nlist;
    static int[] dp;

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        nlist = new ArrayList<>();

        //使える数のリストを作り、ソート
        int n9 = 1, n6 = 1;
        while (n9 * 9 <= N)
        {
            n9 *= 9;
            nlist.add(n9);
        }
        while (n6 * 6 <= N)
        {
            n6 *= 6;
            nlist.add(n6);
        }
        nlist.add(1);
        Collections.sort(nlist);

        //dp
        dp = new int[N + 1];
        for (int i = 0; i < N; i++)
        {
            for (int li = 0; li < nlist.size(); li++)
            {
                int v = nlist.get(li);
                if (i + v > N) break;

                if (dp[i + v] == 0) dp[i + v] = dp[i] + 1;
                else dp[i + v] = Math.min(dp[i + v], dp[i] + 1);
            }
        }
        System.out.println(dp[N]);
    }
}

 いいねぇ