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問題まで解くことができて良かったです。次のコンテストに向けて勉強したいと思います。