競プロの過去問をPython, Go, Rust 使って黙々と解く_Day3

苦行 3日目

「競プロの過去問をPython, Go, Rust 使って黙々と解く」 という、１人アドベントカレンダーの3日目です！(遅刻3回目)🎉
このアドカレを始めた理由や、ルールは1日目の記事をみてください。

問題3 Some Sums

「AtCoder Beginner Contest 083」
B - Shift only

今回は新たに条件分岐を使いそうな問題を選びました。

Python

自分の回答

n,a,b = list(map(int, input().split()))
ans = 0

for i in range(1, n+1) :
    digit_sum = sum(map(int, list(str(i))))

    if a <= digit_sum <= b:
        ans+=i

print(ans)

なんか公式の解説とは違う回答だが、こっちの方が簡単に書けた。

digit_sum = sum(map(int, list(str(i))))

数字を文字配列にしてから、mapで一気にint配列に変換。それの合計を求めている。
これで各桁数字の合計が得られる。簡単。

if a <= digit_sum <= b:

a以上、b以下を判定している。条件式の書き方が数学的な書き方に近いのが、初心者にもわかりやすい上に、andで繋ぐより若干速度が速いので嬉しい。

別解

c = []
for i in range(10):
    for j in range(10):
        for k in range(10):
            for l in range(10):
                c.append(i+j+k+l)
c.append(1)
n, a, b = map(int,input().split())
print(sum([i for i in list(filter(lambda i : a <= c[i] <= b, range(n+1)))]))

提出されている中で2番目に実行速度の速いコード(22ms)がこれなんですが・・・

え、なにこれは・・・(困惑)

どうやら10⁴分の[桁の和]を全て格納したリストcを作ったようです。
こうすることでc[hoge]のhogeに桁の合計を求めたい数字を渡すだけで検索できるというわけです。
え、なにそれは・・・(困惑)

新たな学びとしては、filter(function, iterable)は、リストから条件に合う特定の要素だけを抽出できるということです。これは便利そう。

Go

自分の回答

package main

import (
    "fmt"
    "strconv"
    "strings"
)

func main() {
    n, a, b, ans := 0, 0, 0, 0

    fmt.Scan(&n, &a, &b)

    for i := 1; i <= n; i++ {
        str := strconv.Itoa(i)
        char_slice := strings.Split(str, "")
        digit_sum := 0

        for _, c := range char_slice {
            digit_val, _ := strconv.Atoi(c)
            digit_sum += digit_val
        }

        if a <= digit_sum && digit_sum <= b {
            ans += i
        }
    }

    fmt.Println(ans)
    // println(ans) //標準エラーに書き込まれる
}

昨日もそうだったが、自分の組み方が悪いだけかもしれないが、他の２つに比べてコードが長くなりがち。
考え方はさっきのpythonの解き方と同じ。
ただ、Goにはmap()が無いため、forで書いている。
ちなみにmap()的なことしたいという問いに対して、Goの開発に関わっているRob Pike氏が「forを使え」と言っているので、多分言語の思想が他2つと違うのだろう。

うっかり間違えたとこが2つ。

1つ目

digit_val, _ := strconv.Atoi(c)

strconv.Atoi()は、それぞれ、valとerrorの2つの値を返してくる。
正しく変換できない時の例外処理が簡単にできるようにだろう。多分。 以下のように1つだけ受け取るように書くと動かない。厳しい。

digit_val := strconv.Atoi(c)

2つ目

   fmt.Println(ans)
    // println(ans) //標準エラーに書き込まれる

fmtのPrintlnと、ビルドインのprintlnの違い。
どうやらビルドインのprintlnは標準エラーに書き込まれるらしい。
ビルドインのprintlnを使ったコードをAtCoderに提出した時、結果が全部[WA]になって焦りました・・・

別解

package main

import "fmt"

func main() {
    var n, a, b int
    fmt.Scan(&n, &a, &b)

    var ans int
    for i := 1; i <= n; i++ {
        v := i
        s := 0
        for v > 0 {
            s += v % 10
            v /= 10
        }
        if s >= a && s <= b {
            ans += i
        }
    }
    fmt.Println(ans)
}

別解というか、公式の解説ではこの解き方が解答例として載っていた。
数字vに対して、v /= 10を繰り返すことで桁が一つずつ右にシフトし、v % 10でその時の一番下の桁が取れるので、あとはそれを足し合わせていけば各桁の合計を出したことになるわけだ。
やっぱりstrconvとかsplitが遅いのか、こっちのコードの方が自分のコードより5倍速い。(自分：5ms, 別解：1ms)

Rust

自分の回答

use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n: u32 = read();
    let a: u32 = read();
    let b: u32 = read();

    let mut ans: u32 = 0;

    for i in 1..n + 1 {
        let digit_sum: u32 = i.to_string().chars()
                          .map(|c| c.to_digit(10).unwrap()).sum();

        if a <= digit_sum && digit_sum <= b {
            ans += i;
        }
    }
    println!("{}", ans);
}

pythonと全く同じだこれぇ！！

let digit_sum: u32 = i.to_string() //int -> string
                  .chars() //string -> Vec<char>
                  .map(|c| c.to_digit(10).unwrap()) //Vec<char> -> Vec<int>
                  .sum(); //Vec<int> の総和

コメントの通りです。pythonのセクションで開設したので特にいうことはありません・・・
書きやすかったけど、これはRustの特徴を生かし切れているのか・・・？

書くことがなさすぎるので、強いてポイントをあげるとすれば、
string -> intはu32::from_str(str).unwrap()ですが、char -> intはchar.to_digit(10).unwrap()です。
.to_digit(10)の引数には何進数に変換するか指定します(この場合10進数)
普通に1つのcharを変換するならlet i: u32 = i as u32 - 48とかできます。

別解

fn main() {
    let scan = std::io::stdin();
    
    let mut line = String::new();
 
    let _ = scan.read_line(&mut line);
    let vec: Vec<&str> = line.split_whitespace().collect();
 
    let n: i32 = vec[0].parse().unwrap();
    let a: i32 = vec[1].parse().unwrap();
    let b: i32 = vec[2].parse().unwrap();

    let mut ans = 0;
    for i in 1..n+1 {
        let s = i/10000+(i%10000)/1000+(i%1000)/100+(i%100)/10+(i%10);
        if s >= a && s <= b {
            ans += i
        }
    }
    println!("{}", ans);
 
}

コード自体は愚直に10⁴分、書く桁の割れる回数を足し合わせることで各桁数の合計を出してる。（お金の計算とかでこんなコード書いた気がする）
で、気になったのは自分の書いたコードとこのコードでは、ms単位では実行速度が変わらないということ。(どちらも実行速度は2ms)
こっちのコードの方が速い気もするが・・・なぜだ？🤔
コンパイラが優秀なのかもしれない。

まとめ

今回から実行速度と、メモリ使用量も記録してみました。
自分の回答の情報はそれぞれ以下の通り。

言語	実行速度(ms)	メモリ使用量(KB)
Python	33	2940
Go	5	1280
Rust	2	4352

やっぱ同じアルゴリズム書いてもRustが速いっすね。

日に日にスラスラかけるようになってきているのが楽しい今日この頃です💪
だんだんPythonとRustが好きになってきました。Goはまだ掴めない感じ。
3日目で得た教訓は「Goは書き方によって爆速になるかも」ということでした。
以上、また明日！