競技プログラミングに参加してみました。

初参加

UNIQUE VISION Programming Contest 2022（AtCoder Beginner Contest 248） - AtCoder

転職活動中にプログラミングテストがあり、AtCoder社の競技プログラミングコンテストに練習がてら参加してみました。
言語は全てJavaで解きました。
問題はA～G,Exまであり、後ろになるほど難しくなってきます。
制限時間は100分。結果としてはまるまる使ってBまで行けました。

A問題は25分ぐらいかかってなんとか、、、

数字のみからなる、長さがちょうど 9 の文字列 S が与えられます。 S には 0 から 9 までのうち、ちょうど 1 つの数字を除いた 9 種類の数字が一度ずつ登場します。 S に登場しない唯一の数字を出力してください。

という問題でした。

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 整数の入力
        String a = sc.next();
        String[] strArray = a.split("");
        boolean[] r = {false,false,false,false,false,false,false,false,false,false};
        for (String s : strArray) {
            r[Integer.valueOf(s)] = true;
        }
        for( int i = 0; i < 10 ; i++){
            if (!r[Integer.valueOf(i)]) {
                System.out.println(i);
                return;
            }
        }
    }
}

10個の数字でそれぞれ、出現したかどうかのフラグを持つような感じにしました。
難しく考えすぎたかな、、、なんかもうちょっと簡単にできたのかも。
解説を見ていたら0~9の合計数から引いて求める解法もあったりして、頭いいなぁという感想。

B問題のほうが簡単に感じる

A 匹のスライムがいます。 すぬけくんが 1 回叫ぶたびに、スライムは K 倍に増殖します。 スライムが B 匹以上になるには、すぬけくんは最小で何回叫ぶ必要があるでしょうか？
1≤A≤B≤10⁹
2≤K≤10⁹
入力は全て整数

これはそこまで難しくないな～と思ったんですが、一個だけ落とし穴がありました。

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // スペース区切りの整数の入力
        int a = sc.nextInt();
        int b = sc.nextInt();
        int k = sc.nextInt();
        int s = 0;
        int slime = a;
 
        while (true) {
            if (slime >= b) {
                System.out.println(s);
                return;
            }
            slime = slime * k;
            s++;
        }
    }
}

500000000 1000000000 1000000000
という値を入れたとき、int型ではオーバーフローします。
値の範囲が-2³¹ ～ 2³¹-1（およそ21億5千万）なので。
ですのでslimeはintではなくlongにしないとでした。
これに引っかかって数分悩みました。

追記： これがヒントになって解けました！
デバッグ力を高める！ ～5 年間の経験から学んだ、競プロ・アルゴリズム実装におけるバグ取りの戦略～ - Qiita

鬼門のC問題、まったくわからず惨敗。。。

これは全然わからなかったです。
解説見たけど、イマイチピンと来ず。
とはいえ疑問を言語化できず、何がわからないかわからない状態。。。

DP（ダイナミックプログラミング）というものをここで初めて知りました。
これはまた次回頑張ります。
なお、CがダメだったのでD以降は見てもいません。
まずはCが解けるように勉強進めます！

まとめ

初めてのコンテストにしては、Bまで解けたし良かったです。
（一問も解けないのではと心配していたので、一旦は良かったかなと。）
ただしDPは全くわからなかったので、壁にぶつかった感があります。
これは引き続き勉強進めたいと思います。

余談ですが、上位の人は1問数十秒から数分で解いていて、どんな頭しているんだと思いました。。。