D - 壊れた電卓 CODE FESTIVAL 2014 予選A

D - 壊れた電卓

問題概略

K種類の数字を使う時、Aとの最小の差はなにか

制約

$A(1\leqq A\leqq {10}^{15})$ 

$K(1\leqq K\leqq 10)$ 

解法

前からP桁目までをAと同じ数にして、P+1桁目をQに、それ以降をRにして全探索すればいいと分かる

問題の芯

限りなく簡単に実装したい。時間に余裕があるなら、細かい条件はつけずに大まかに全探索

public static void main(String[] args)
    {
        long a = sc.nextLong();
        int len = keta(a);
        A = new int[len];
        for (int i = 0; i < len; i++)
            A[i] = (int) ((a / Math.pow(10, i)) % 10);
        reverse(A);
        long best = Long.MAX_VALUE;
        K = sc.nextInt();
        if (K == 10 || len <= K)
        {
            System.out.println(0);
            return;
        }
        if (K == 1)
        {
            //桁数が増える場合
            int[] nump = new int[len + 1];
            for (int j = 0; j < 10; j++)
            {

                for (int i = 0; i < len+1; i++)
                {
                    nump[i] = j;
                    long score = Math.abs(toLong(nump) - a);
                    best = Math.min(best, score);
                }
            }
            //桁数がへる場合
            int[] numm = new int[len - 1];
            for (int j = 0; j < 10; j++)
            {

                for (int i = 0; i < len-1; i++)
                {
                    numm[i] = j;
                    long score = Math.abs(toLong(numm) - a);
                    best = Math.min(best, score);
                }
            }

        }

        int[] num = new int[len];
        for (int pi = 0; pi <= len; pi++)
        {

            for (int q = 0; q < 10; q++)
            {
                for (int r = 0; r < 10; r++)
                {
                    int i;
                    for (i = 0; i < pi; i++)
                    {
                        num[i] = A[i];
                    }
                    if (i < len)
                    {
                        num[i++] = q;
                    }
                    for (; i < len; i++)
                    {
                        num[i] = r;
                    }
                    if (canMake(num))
                    {
                        long score = Math.abs(toLong(num) - a);
                        best = Math.min(best, score);
                    }
                }

            }

        }
        System.out.println(best);
    }