Ccmmutty logo
Commutty IT
・4 min read

RustとAtCoderを勉強する(typical90_bo)

AtCoderRust
https://cdn.magicode.io/media/notebox/23dc80a9-d1f2-4ec4-9f8f-e7d697772ac9.jpeg

はじめに

AtCoderの問題をRustで解いていきます。AtCoderもRustも初心者ですが、温かい目で成長を見守っていただけるとありがたいです。
今回は、競プロ典型90問の067 - Base 8 to 9（★2）を解きました。

提出コード

rust
use num::pow;

fn base_8_to_10(n_8: u128) -> u128 {
    let n_str = n_8.to_string();
    let mut n_10 = 0;
    for (e, x) in n_str.chars().rev().enumerate() {
        n_10 += (x as u128 - '0' as u128) * pow(8, e);
    }
    n_10
}

fn base_10_to_9(mut n_10: u128) -> u128 {
    let mut n_9_str = String::new();
    while n_10 > 0 {
        n_9_str.push(std::char::from_digit((n_10 % 9) as u32, 10).unwrap());
        n_10 /= 9;
    }

    n_9_str
        .chars()
        .rev()
        .collect::<String>()
        .parse::<u128>()
        .unwrap_or(0)
}

fn rewrite_8_to_5(n: u128) -> u128 {
    n.to_string().replace('8', "5").parse::<u128>().unwrap()
}

fn main() {
    proconio::input! {
        mut n: u128,
        k: usize,
    }

    for _ in 0..k {
        n = base_8_to_10(n);
        n = base_10_to_9(n);
        n = rewrite_8_to_5(n);
    }

    println!("{}", n);
}

解説

進数変換の問題です。変換の過程で数値⇄文字列の型変換が多く、良い練習になりました。
fn base_8_to_10(n_8: u128) -> u128 {...} では、8進数の数字をひとまず10進数に変換します。この関数で重要なことは、以下の２つです。
  • イテレータに添字をくっつけたい時は enumerate() を利用する
  • charを数字に変換したい時は、'0' as u128 を引く
特に2つ目は下記のコードを見ていただけると分かりやすいかもしれません。
rust
for c in 'a'..='c' {
  println!("{} as usize: {}", c, c as usize);
}

for c in '0'..'3' {
  println!("{} as usize: {}", c, c as usize);
}
a as usize: 97
b as usize: 98
c as usize: 99
0 as usize: 48
1 as usize: 49
2 as usize: 50
()
上記のコードから、char を数値に変換すると文字コードに変換されていることが分かります。また、文字コードは '0'..='9' や 'a'..='z' などで連続しています。そのため、'2' などの数字を表す char を u128 型の数値 2u128 に変換したい場合、'2' の文字コードから '0' の文字コードを引くことで実現できます。もちろん、単純に '2' as u128 - 48 としても問題ありません。
fn base_10_to_9(mut n_10: u128) -> u128 {...} では、10進数の数字を9進数に変換しています。ここで注意する点は以下の２つです。
  • std::char::from_digit() の第1引数は u32 を取るため、変換する。
  • n_9_str を u128 に変換するとき、unwrap_or(0) を使用する。
まず1つ目に関して、おそらくこんなやらかしをする人は自分以外いないと思いますが (n_10 % 9) as u32 を n_10 as u32 % 9 としてもコンパイルは通るものの、異なる計算結果となる可能性があります。理由としては、今回の問題の入力の最大値は 8^20 であり、これは u32 の最大値である 2^32-1 を上回っているためです。ついでに言及しておくと、今回のコードでは u128 として数値を取り扱っていますが、8^20 < 2^64 なのでおそらく u64 でも大丈夫です。今までpythonを使ってきた弊害で自分はこれに気づくのに時間がかかったので、注意してください。
また、2つ目に関してもここを単に unwrap() とすると入力が 0 のときに panic が生じてしまうため注意してください。

まとめ

  • イテレータに添字をつけたいときは enumerate() を使う
  • char を数値に変換するときは '0' の文字コードを引く
  • 型を常に意識する
  • 場合によっては unwrap_or() などを使用する

Discussion

コメントにはログインが必要です。