AtCoder (AtCoder Beginners Selection) [ABC083B]

AtCoderの問題を解いてみます。今回は初心者向けの問題のAtCoder Beginners Selectionの3回目です。

問題

ABC083B – Some Sums

https://atcoder.jp/contests/abs/tasks/abc083_b

問題概要

整数NとAとBが入力されます。そして、1からNまでの整数で、条件を満たすものの和を求める問題です。その条件は以下になります。

  • 整数の各桁の和がA以上、B以下

なお、整数Nは1から10,000という制約があります。

回答

今回は2つほど回答を作成しました。

言語

Java8 (OpenJDK 1.8.0)

作成コード(1つ目)

最初に作成したコードが以下です。

public class Main {
 
    public static void main(String... args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        pw.println(new Main(br).execute());
        pw.flush();
 
    }
 
    private final int n, a, b;
 
    Main(BufferedReader br) throws Exception {
        String[] s = br.readLine().split(" ");
        this.n = Integer.parseInt(s[0]);
        this.a = Integer.parseInt(s[1]);
        this.b = Integer.parseInt(s[2]);
    }
 
    int execute() {
        int result = 0;
        for (int i = 1; i <= n; i++) {
            result += checkRange(i, a, b);
        }
        return result;
    }
 
    private static int checkRange(int n, int a, int b) {
 
        String n5 = String.valueOf(100000 + n); // 1 padding
 
        int n4 = n5.charAt(1) - 48; // n0000
        int n3 = n5.charAt(2) - 48; // n000
        int n2 = n5.charAt(3) - 48; // n00
        int n1 = n5.charAt(4) - 48; // n0
        int n0 = n5.charAt(5) - 48; // n
 
        int sum = n4 + n3 + n2 + n1 + n0;
 
        return (a <= sum && sum <= b) ? n : 0;
 
    }

}

解説

入出力部分の説明は不要だと思うので省略します。

まず、以下の部分について説明します。

    int execute() {
        int result = 0;
        for (int i = 1; i <= n; i++) {
            result += checkRange(i, a, b);
        }
        return result;
    }

これは1からNまでループしつつ、サブメソッドの戻りを足しています。後ほど説明しますがサブメソッドは、条件を満たす場合はiを、満たさない場合は0を返すメソッドになっています。

次に以下の部分的について説明します。

    private static int checkRange(int n, int a, int b) {
 
        String n5 = String.valueOf(100000 + n); // 1 padding
 
        int n4 = n5.charAt(1) - 48; // n0000
        int n3 = n5.charAt(2) - 48; // n000
        int n2 = n5.charAt(3) - 48; // n00
        int n1 = n5.charAt(4) - 48; // n0
        int n0 = n5.charAt(5) - 48; // n
 
        int sum = n4 + n3 + n2 + n1 + n0;
 
        return (a <= sum && sum <= b) ? n : 0;
 
    }

条件を満たすか判定するサブメソッドです。条件を満たした場合、引数の整数を返し、そうでない場合は0を返します。なお、何となく変更してしまいましたが引数のnはループ変数のままiにしておいた方が良かったかなと思います。

ロジック的には、整数を一旦文字列に変換し、各桁の文字を整数として見て総和を取っています。処理を単純にするために最初に100,000を足して、どのような入力の場合でも桁数が一定になるようにしています。またcharからintに変換するのに48を引いています。

結果

今回の結果は以下のようになりました。ぼちぼちの結果かなと思います。

  • 実行時間:88 ms
  • メモリ:20,564 KB

作成コード(2つ目)

改良したコードが以下です。

public class Main {
 
    public static void main(String... args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        pw.println(new Main(br).execute());
        pw.flush();
 
    }
 
    private final int n, a, b;
 
    Main(BufferedReader br) throws Exception {
        String[] s = br.readLine().split(" ");
        this.n = Integer.parseInt(s[0]);
        this.a = Integer.parseInt(s[1]);
        this.b = Integer.parseInt(s[2]);
    }
 
    int execute() {
        int result = 0;
        for (int i = 1; i <= n; i++) {
            result += checkRange(i, a, b);
        }
        return result;
    }
 
    private static int checkRange(int i, int a, int b) {
 
        int sum = 0;
 
        int n = i;
        while (true) {
            sum += n % 10;
            if ((n = n / 10) == 0) {
                break;
            }
        }
 
        return (a <= sum && sum <= b) ? i : 0;
 
    }
}

解説

基本的には最初のコードと同じです。以下の部分が変更になっています。

    private static int checkRange(int i, int a, int b) {
 
        int sum = 0;
 
        int n = i;
        while (true) {
            sum += n % 10;
            if ((n = n / 10) == 0) {
                break;
            }
        }
 
        return (a <= sum && sum <= b) ? i : 0;
 
    }
}

整数を10で割ってその余りを足し、また10で割った際の商に対して同様の処理を行い、それを繰り返しています。10で割った余りがその桁の数になるので、それを繰り返すことで各桁の数の和を計算しています。

結果

今回の結果は以下のようになりました。性能UPを狙ってのカスタマイズではなかったのですが、1回目より実行時間が結構早くなっていて、いい感じかなと思います。

  • 実行時間:72 ms
  • メモリ:20,944 KB

作成物

今回の作成物は以下に置いています。

https://github.com/masaki-code/java/tree/master/atcoder

コメント

タイトルとURLをコピーしました