naoya_t@hatenablog

いわゆるチラシノウラであります

Rust入門記(チュートリアルからABSまで)

そろそろRustじゃないかなと思ったのでちゃんと入門してみる。
(前にも一度そう思ってhomebrewでRustを入れたんだけど何もしてなかった)

(再)インストール

homebrew版は捨てて、rustupでインストール。

和訳ドキュメントをビルドしたいけれどrustbookが入らない。。。
ここにあるrustbook入りDockerイメージを利用して解決。

第1段階

チュートリアルの「数あてゲーム」を写経して動かしてみる。

$ cargo new kazuate
$ cd kazuate ; vi src/main.rs
$ cargo run
   Compiling kazuate v0.1.0 (file:///Users/naoyat/work/rust/kazuate)
    Finished dev [unoptimized + debuginfo] target(s) in 10.76s
     Running `target/debug/kazuate`
数字を当ててみて!
予想値を入力してください
...

cargo便利。

// main.rs
extern crate rand;

use std::io;
use std::cmp::Ordering;
use rand::Rng;

fn main() {
    println!("数字を当ててみて!");

    let secret_number = rand::thread_rng().gen_range(1, 101);
    // println!("秘密の数字: {}", secret_number);

    println!("予想値を入力してください");

    loop {
        let mut guess = String::new();

        io::stdin().read_line(&mut guess).expect("行の読み取りに失敗しました");

        let guess: u32 = match guess.trim().parse() {
            Ok(num) => num,
            Err(_) => continue,
        };

        println!("あなたの予想値: {}", guess);

        match guess.cmp(&secret_number) {
            Ordering::Less    => println!("小さすぎます!"),
            Ordering::Greater => println!("大きすぎます!"),
            Ordering::Equal   => {
                println!("あなたの勝ちです!");
                break;
            }
        }
    }
}

文字列リテラルに日本語をそのまま書いても大丈夫みたいだ。

第2段階

ABS (AtCoder Beginners Selection)あたりをRustで解きながら色々見ていこう。
その前に、標準入出力についてさらっておく。

標準出力

println!("テキスト"); でテキストが表示され(た後に改行され)る。ln なしの print!("文字列") で(想像通り)改行なしで表示される。
プレースホルダ {} を置いて、変数の内容を表示させることもできる。

fn main() {
    let name = "Rust";
    print!("Hello. ");
    println!("My name is {}.", name);
}

print!() の文字列を返す版(何も表示しない)が format!() である。

標準入力

文字列には std::string::String&str の2種類があるらしい。
(前者はmutableで後者は定数?)

標準入力から文字列を1行読み取るには

fn main() {
    let mut s = std::string::String::new();
    std::io::stdin().read_line(&mut s).ok();
    println!("Your input is \"{}\"", n);
}

ダブルクオートのエスケープは他の多くの言語同様バックスラッシュを用いればよい。
これだと行末の改行も含まれるので、ダブルクオートが次の行に飛ばされて表示される。

fn main() {
    let mut s = std::string::String::new();
    std::io::stdin().read_line(&mut s).ok();
    let s = s.trim_right();
    println!("Your input is \"{}\"", n);
}

これで余分な改行が消える。

数値として入力するには?

fn main() {
    let mut s = std::string::String::new();
    std::io::stdin().read_line(&mut s).ok();
    let n = s.trim_right().parse().ok().unwrap();
    println!("Your input is {}", n);
}

unwrap() は結果の値を得るための何か。(これがないと std::option::Option が来る)

でもこれでは parse()型推論ができなくて怒られる。

$ rustc foo.rs
error[E0282]: type annotations needed
 --> foo.rs:4:9
  |
4 |     let n = s.trim_right().parse().ok().unwrap();
  |         ^
  |         |
  |         cannot infer type for `_`
  |         consider giving `n` a type

受ける変数nに型を指定すれば良いらしい。あるいはparse()の方に型を指定しても行ける。

fn main() {
    let mut s = std::string::String::new();
    std::io::stdin().read_line(&mut s).ok();
    let n:i32 = s.trim_right().parse().ok().unwrap();
    // let n = s.trim_right().parse::<i32>().ok().unwrap();
    println!("Your input is {}", n);
}

i32は言うまでもなく32ビット符号付き整数。

競プロでよくある、沢山の整数がスペース区切りで1行に入っているやつを読み取るには?

fn main() {
    let mut s = std::string::String::new();
    std::io::stdin().read_line(&mut s).ok();
    let a:Vec<i32> = s.trim_right().split(' ').map(|s| s.parse().ok().unwrap()).collect();
    println!("Your input is {:?}", a);
}

VecSTLvectorにあたる、のかな。splitしてmapしてcollectしたらVecが出来るのか。便利。
{:?} とすると Vec<i32> も表示できる。

qiita.com
に、こうした入力を便利関数にまとめたものが載っている。(2次元配列への入力なんてのもある)
split(' ') の代わりにsplit_whitespace() なんてのもあるのね。
とりあえずスニペットにしておこう。

(以下、ここにある read_なんとか() は略)

PracticeA - はじめてのあっとこーだー(Welcome to AtCoder

  • 標準入力から3つの整数a,b,c(1行目にa、2行目にbとc)と文字列s(3行目)を読み取って、
  • 整数a,b,cの和と文字列sを標準出力に返す
fn solve(a:i32, b:i32, c:i32, s:&str) {
    println!("{} {}", a+b+c, s);
}
fn main() {
    let a = read::<i32>();
    let bc = read_vec::<i32>();
    let s = read::<String>();
    solve(a, bc[0], bc[1], &s);
}

→AC
https://beta.atcoder.jp/contests/abs/submissions/2972324

ABC086A - Product

2つの整数を読んでその積が偶数か奇数かを答える問題。

fn solve(a:i32, b:i32) {
    if a * b % 2 == 1 {
        println!("Odd");
    } else {
        println!("Even");
    }
}
fn main() {
    let ab = read_vec::<i32>();
    solve(ab[0], ab[1]);
}

→AC
https://beta.atcoder.jp/contests/abs/submissions/2972353

ABC081A - Placing Marbles

'0'と'1'のみから成る3文字の文字列に'1'がいくつ含まれているか。
(文字コード - 0x30) の和を取る方法で書いてみる。

fn solve(s:String) {
    let cnt:i32 = s.chars().map(|c| c as i32 - 0x30).sum();
    println!("{}", cnt);
}
fn main() {
    let s = read::<String>();
    solve(s);
}

→AC
https://beta.atcoder.jp/contests/abs/submissions/2972857
charをi32にキャストすることを覚えた。

ABC081B - Shift only

整数の配列が与えられて、それぞれの数が2で何回割れるかを数え、その最小値を表示する問題。

  transform(ALL(v), v.begin(), [](int x){ return __builtin_ctz(x); });
  cout << *min_element(ALL(v)) << endl;

のようなことがしたい。

fn trailing_zeros(x: i32) -> i32 {
    let mut c = 0;
    let mut x = x;
    while x > 0 {
        if x % 2 != 0 { break; }
        x /= 2;
        c += 1;
    }
    c 
}
fn solve(a: Vec<i32>) {
    let ans:i32 = a.iter().map(|x| trailing_zeros(*x)).min().unwrap();
    println!("{}", ans);
}
fn main() {
    let _ = read::<i32>();
    let a = read_vec::<i32>();
    solve(a);
}

→AC
https://beta.atcoder.jp/contests/abs/submissions/2973078
map()で *x としないと

expected i32, found &i32
help: consider dereferencing the borrow: `*x`

と怒られる辺りがまだよく分かってない。(言われるがままに*xと書いたら通った)

ABC087B - Coins

(DPとか考えずに)愚直なforループで解いてみる。
for i in 0..a だと 0 から a-1 までしか回らないから a+1 で。(括弧は要らないみたい)

fn solve(a:i32, b:i32, c:i32, x:i32) -> i32 {
    let mut cnt:i32 = 0;
    for i in 0..a+1 {
        for j in 0..b+1 {
            for k in 0..c+1 {
                if 500*i + 100*j + 50*k == x {
                    cnt += 1;
                }
            }
        }
    }
    cnt 
}
fn main() {
    let a = read::<i32>();
    let b = read::<i32>();
    let c = read::<i32>();
    let x = read::<i32>();
    println!("{}", solve(a, b, c, x));
}

→AC
https://beta.atcoder.jp/contests/abs/submissions/2973207

ABC083B - Some Sums

1≦x≦N の範囲で十進表記された時の全桁の和がa以上b以下なxの合計

fn ksum(x:i32) -> i32 {
    let mut y = 0;
    let mut x = x;
    while x > 0 {
        y += x % 10;
        x /= 10;
    }
    y
}
fn solve(n:i32, a:i32, b:i32) -> i32 {
    let mut ans = 0;
    for i in 1..n+1 {
        let y = ksum(i);
        if a <= y && y <= b {
            ans += i;
        }
    }
    ans
}
fn main() {
    let nab = read_vec::<i32>();
    println!("{}", solve(nab[0], nab[1], nab[2]));
}

→AC
https://beta.atcoder.jp/contests/abs/submissions/2973387
a <= y <= b みたいな書き方は出来ないみたい。

ABC088B - Card Game for Two

AliceとBobが大きい順に交互に取って行って、それぞれが取った数の合計の差のabs
(大きい順でも小さい順でも、どちらが先手でも同じこと)

fn solve(_n:i32, mut a:Vec<i32>) -> i32 {
    a.sort();
    a.reverse();
    let mut alice:i32 = 0;
    let mut bob:i32 = 0;
    for (i, a_i) in a.iter().enumerate() {
        if i % 2 == 0 {
            alice += *a_i;
        } else {
            bob += *a_i;
        } 
    }
    (alice - bob).abs()
}
fn main() {
    let n = read::<i32>();
    let a = read_vec::<i32>();
    println!("{}", solve(n, a));
}

→AC
https://beta.atcoder.jp/contests/abs/submissions/2973465
sortやreverseをするのでaにはmutが必要。
iter().enumerate()の中のa_iの*がなくてもローカルでは動いたんだけどサーバでは動かなかった。バージョン依存?(ローカルは1.28.0、サーバは1.15.1)

ABC085B - Kagami Mochi

単調減少な部分列のサイズの最大値を求めたい。

    set<int> s(ALL(d));
    cout << s.size() << endl;

みたいなことがしたい。

use std::collections::HashSet;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn main() {
    let n = read::<i32>();
    let mut set: HashSet<i32> = HashSet::new();    
    for _ in 0..n {
        let d_i = read::<i32>();
        set.insert(d_i);
    }
    println!("{}", set.len());
}

→AC
https://beta.atcoder.jp/contests/abs/submissions/2973519

ABC085C - Otoshidama

1万円札・5千円札・千円札合計N枚でY円になる組み合わせを1つ挙げる(なければ-1 -1 -1を表示)。
愚直に二重ループで。
答えをタプルで返して受け取ってみる。これはお手軽。

fn solve(n:i32, total:i32) -> (i32,i32,i32) {
    for i in 0..n+1 {
        for j in 0..n-i+1 {
            let k = n - i - j;
            if 10000*i + 5000*j + 1000*k == total {
                return (i, j, k);
            }
        }
    }
    (-1, -1, -1)
}
fn main() {
    let ny = read_vec::<i32>();
    let (x,y,z) = solve(ny[0], ny[1]);
    println!("{} {} {}", x, y, z);
}

→AC
https://beta.atcoder.jp/contests/abs/submissions/2973542

ABC049C - 白昼夢 / Daydream

後ろからなら煩雑な場合分けが必要ない問題だと知ってしまっているので後ろから…
elifとかelsifとかelseifみたいな予約語はRustには無いのかな。
substringどうやって取る?
slice_unchecked(begin, end) というのがあって、begin, endはusizeを取るというのは良いとして
unsafeって何だ?unsafe{ } で囲めば良い?

fn solve(s:&str) -> bool {
    let mut n = s.len(); 
    loop {
        if n == 0 {
            return true;
        } else if n >= 5 && unsafe { s.slice_unchecked(n-5, n) == "dream" } {
            n -= 5;
        } else if n >= 7 && unsafe { s.slice_unchecked(n-7, n) == "dreamer" } {
            n -= 7;
        } else if n >= 5 && unsafe { s.slice_unchecked(n-5, n) == "erase" } {
            n -= 5;
        } else if n >= 6 && unsafe { s.slice_unchecked(n-6, n) == "eraser" } {
            n -= 6;
        } else {
            return false;
        }
    }
}
fn main() {
    let s = read::<String>();
    if solve(&s) {
        println!("YES");
    } else {
        println!("NO");
    }
}

→AC
https://beta.atcoder.jp/contests/abs/submissions/2973604

(続く)

ABC086C - Traveling

寄って行くべき座標と時刻のリストが与えられるので、その旅程が可能かを調べる。移動は縦横方向のみ。
次の場所までのマンハッタン距離が時間内に到達不可能なら即No。到達可能でも余りが奇数ならNo。

fn solve(_n:u32, p:Vec<Vec<i32>>) -> bool {
    let mut x = 0;
    let mut y = 0;
    let mut t = 0;
    for pi in p {
        let (ti, xi, yi) = (pi[0], pi[1], pi[2]);
        let dx = (xi - x).abs() + (yi - y).abs();
        let dt = ti - t;
        if dx > dt {
            return false;
        }  
        if (dt - dx).abs() % 2 == 1 {
            return false;
        }
        x = xi;
        y = yi;
        t = ti;
    }
    true
}
fn main() {
    let n:u32 = read::<u32>();
    let p = read_vec2::<i32>(n);
    if solve(n, p) {
        println!("Yes");
    } else {
        println!("No");
    }
}

→AC
https://beta.atcoder.jp/contests/abs/submissions/2973625

とりあえずABSの問題程度であればRustで解けるようになった。めでたしめでたし。