山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

AtCoder Beginner Contest 099 の感想

AtCoder Beginner Contest 099

結果

C問題まで解くことができました。D問題の題意は分かりましたが、どのようにして解いたらいいのか分かりませんでした。全探索でしょうか?

A - ABD

A: ABD - AtCoder Beginner Contest 099 | AtCoder

数値を比較して解答します。

B - Stone Monument

B: Stone Monument - AtCoder Beginner Contest 099 | AtCoder

面白いと思った問題。

考え方

 n 番目の塔の高さを  T_n とすると、

 T_n = \dfrac{n(n + 1)}{2}

となります。また、隣り合う塔の高さの差は、

 T_{n} - T_{n - 1} = n

となります。西側と東側の塔の高さを雪を無視して考えると、

西側:  x + a

東側:  x + b

となります。このとき、二つの塔の高さの差は、

 n = b - a

となります。

したがって、

 T_n = \dfrac{n(n + 1)}{2} = x + b

となるので、この方程式を x について解けば解答が得られます。

C - Strange Bank

C: Strange Bank - AtCoder Beginner Contest 099 | AtCoder

特殊な引出し方をするキャッシュディスペンサです。

考え方

 i = 1 から  i = N まで順番に回数を記録していきます。

ん?なんかこのやり方yukicoderで見ましたね。

yamakasa3.hatenablog.com

メモ化再帰と言うんでしょうか?解答の方針としては似たように思います。

まず初めに、 6 9 N 以下の累乗の値と 1を昇順にリストに入れておきます。このリストをlistとします。

ここで、  i 円の最小の操作回数を m_i とします。

 i がlistに含まれるとき、 m_i = 1 となります。

 i がlistに含まれないときを考えます。ここで、listのある値を l_j とします。list の中で、

 i - l_j \geq 0

を満たす全ての j に対して、

 m_j が最小となるものを選び、

 m_i = m_j + 1

とします。これを N まで続けることで回答が得られます。

公式の解説

公式の解説を見るとすごいスマートなやり方をしています。良く読んでいないので、まだ理解していませんが、値が大きくなると僕の方法ではタイムアウトになると思います。

コード

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class ProblemC {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        scan.close();
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(1);
        listMoney(list, N, 6);
        listMoney(list, N, 9);
        Collections.sort(list);
        if(N <= 10) {
            if(N <= 5) {
                System.out.println(N);
                System.exit(0);
            }else if(N <= 8) {
                System.out.println(N - 5);
                System.exit(0);
            }else {
                System.out.println(N - 8);
                System.exit(0);
            }
        }

        int []m = new int[N + 1];
        m[1] = 1;
        m[2] = 2;
        m[3] = 3;
        m[4] = 4;
        m[5] = 5;
        m[6] = 1;
        m[7] = 2;
        m[8] = 3;
        m[9] = 1;
        int t = 0;
        for(int i = 10; i <= N; i++) {
            if(isCheck(i, 9)) {
                m[i] = 1;
            }else if(isCheck(i, 6)) {
                m[i] = 1;
            }else {
                t = i;
                int k = 100000;
                int a;
                for(int j = 0; j < list.size(); j++) {
                    a = t - list.get(j);
                    if(a >= 0) {
                        if(k > m[a] + 1) {
                            k = m[a] + 1;
                        }
                    }else {
                        break;
                    }
                }
                m[i] = k;
            }
        }
        System.out.println(m[N]);

    }
    public static void listMoney(ArrayList<Integer> list, int N, int k) {
        int t = 0;
        int i = 1;
        while(N - t >=0) {
            t = (int) Math.pow(k, i);
            list.add(t);
            i ++;
        }
    }
    public static boolean isCheck(int n, int k) {
        int t = 0;
        int i = 0;
        while(n - t >= 0) {
            t = (int) Math.pow(k, i);
            i ++;
            if(n - t == 0) {
                return true;
            }
        }

        return false;
    }
}

感想

D問題は解くことができなかったんですが、C問題まで解くことができて良かったです。次のコンテストに向けて勉強したいと思います。