8
5

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@ta_to_co

Rust初心者がAtCoder Beginers SelectionをRustで解いてみた

8
Posted at

Rustの勉強を始めたので,今回はRustの理解も兼ねて
AtCoder Beginners Selectionを解いてみます.

自分がAtCoderで水色で、そのレベルだとここの問題を解くのは難しくないレベルです.
なので,問題を解くアルゴリズムを考えることではなく,Rustの文法に慣れることを目指して解説していきます.

文字列の扱い

競技プログラミングでは入力を受けて処理をするので、まず入力の文字列を処理する方法を考えます.

Rustでは文字列を扱うときはよくstr型とString型が使われます.
Stringはコードを見ると構造体としては
Vector型で,strはu8のスライスとなります.

どちらもutf8以外受け取らない様になっています.

変換方法

これらは簡単に変換することができまず.実際,以下で変形します.

str -> String: to_string,
String -> &str: &をつけるだけ

Stringはヒープに値を持つの可変長,strは固定長なので,適当に文字列操作して新しい文字列を操作するのであれば,&str型を使うほうが性能が出そうです.
ただ,str型は基本さらに参照して使う事が多いため,メソッドの引数と復帰値両方に使う場合はライフタイムを意識しないといけない場合はがあります.

メソッドでのライフタイム

ライフタイムは変数が何かを参照して作ったもの場合に,その参照先のデータが残っていることを保証するための仕組みです.

とはいえ、常に書いていると面倒なので、基本はコンパイラ側で推論してくれています.
ただ,いつまでなのか期間が保証されない場合は自分で指定する必要があります.
例えば以下のメソッドを見ます.

fn main() {
    let hello = "Hello";
    let world = "World";
    println!("{}", longer(hello, world));
}

fn longer(x: &str, y: &str) -> &str {
    if x.len() >= y.len() { return x} else {return y}
    }

これをコンパイルしようとすると,

|
9 | fn longer(x: &str, y: &str) -> &str {
 |                                ^ expected lifetime parameter
 |
 = help: this function's return type contains a borrowed value, but the signature does not say whether it is borrowed from `x` or `y`

とエラーになります.

この変数の復帰値がどこまでのライフタイムを保証すればいいかわからないからです.
この場合はx,yの短い方と明記する必要があります.(実際これをライフタイムの短い方に勝手に推論してくれてもいい気はしますが...)
なので、引数の参照になる場合は気をつけなければいけません.

これを回避するにはライフタイムを指定するのが常套手段ですが,
それ以外に以下のように新しくヒープ領域にデータを作ってしまう(つまりString)にしてしまうという方法があります.

fn main() {
    let hello = "Hello";
    let world = "World";
    println!("{}", longer(hello, world));
}

fn longer(x: &str, y: &str) -> String {
    if x.len() >= y.len() { return x.to_string()} else {return y.to_string()}
    }

こういうエラーははまりやすいので、メソッドの復帰値では新しい文字列をStringで生成する方が楽なのかなと思います.

標準入力

rustの標準入力はread_lineが使われます.
引数は必ず文字列型になるため、AtCoder用には条件に応じて型を変換する必要があります.

let mut s = String::new();
std::io::stdin().read_line(&mut s).ok();

AtCoderでそのまま読むにはこれが一番素直なやり方かなと思います.

AtCoderの問題

前置きが相当長くなったので、この辺から真面目にAtCoderときましょう.

今回は上のサイトにあるreadのコードを使いました.
また,全てを使うわけではないので、何も考えずにコンパイルするとwarningが出ます.
なので、コードの先頭に#![allow(dead_code)]と書くことを推奨しておきます.

Prcatice

文字を入力として、ただしく受け取ればよいです.
今回は数値はread_vec,文字列はreadで取得してみます.

fn practice() {
    let first_int: Vec<i32> = read_vec();
    let second_int: Vec<i32> = read_vec();
    let s: String = read();
    let mut res = first_int[0];
    res += second_int[0] + second_int[1];
    println!("{} {}", res, s);
}

ABC086a

入力の積を2で割った余りをみて出力します.

fn abc086a() {
    let fline: Vec<i32> = read_vec();
    if (fline[0] * fline[1]) % 2 == 1 {
        println!("Odd");
    } else {
        println!("Even");
    }
}

ABC081a

文字として受け取って、一文字ずつループさせ、'1'の場合は1増やします.

fn abc081a() {
    let s: String = read();
    let mut num = 0;
    for i in 0..3 {
        if s.chars().nth(i).unwrap() == '1' {
            num += 1;
        }
    }
    println!("{}", num);

}

ABC081B

問題はループの中で再帰的に2で割っていけば,求まると思います.
rustの場合,条件を満たすまでずっとループするのはloopでかけます.
脱出の時はbreakですが、今回のようにforでネストしてしまう場合はスコープを指定する必要があります.

fn abc081() {
    let n: usize = read();
    let mut A: Vec<i32> = read_vec();
    let mut ret = 0;
    'outer: loop {
        for i in 0..n {
            if A[i] % 2 == 1 {
                break 'outer;
            } else {
                A[i] /= 2;
            }
        }
        ret += 1;
    };
    println!("{}", ret);
}

ABC087B

1250通りしかないので、愚直に全探索します.

fn abc087b() {
    let a: i32 = read();
    let b: i32 = read();
    let c: i32 = read();
    let x: i32 = read();
    let mut num = 0;
    for _a in 0..(a+1) {
        for _b in 0..(b+1) {
            for _c in 0..(c+1) {
                if 500 *_a + 100 * _b + 50 * _c  == x {
                    num += 1;
                }
            }
        }
    }
    println!("{}", num);
}

ABC083B

これも10000個しかないので、全探索します.
桁数の和は数値を文字列に変形して,一文字ずつ分割した後足しました.
rustの場合はchar型の列にして、それを文字コードをみながら整数に置き直しています.

fn abc083b(){
    let input: Vec<i32> = read_vec();
    let (n, a, b) = (input[0], input[1], input[2]);
    let mut num = 0;
    for _n in 1..(n+1) {
        let _n_sum: i32 = _n.to_string().chars().map(|c| c as i32 - 48).fold(0, |sum, c| sum + c);
        if _n_sum >= a  && _n_sum <= b {
            num += _n;
        }
    }
    println!("{}", num);
}

ABC088B

全体をソートして差分をひきます.

fn abc088b() {
    let n: usize = read();
    let mut a: Vec<i32> = read_vec();
    let mut num = 0;
    a.sort();
    for _n in 0..n {
        if _n % 2 == 0 {
           num += a[n-1-_n];
        } else {
            num -= a[n-1-_n];
        }
    }
    println!("{}", num);
}

ABC085B

重複排除して、サイズを数えればよいです.
重複排除するときはsetにするのが自然かと思いますが,
rustの場合はHashSetクラスが存在するので、それで計算します.

fn abc085b(){
    let n: u32 = read();
    let d: Vec<Vec<u32>> = read_vec2(n);
    let uniq_d: HashSet<u32> = d.into_iter().map(|x| x[0]).collect();
    println!("{}", uniq_d.len());
}

ABC085C

条件を考えると
1000円札をz枚使ったとき,
10000円札をx枚、5000円札をy枚使う解答があるかどうかは

  • $Y - 1000 z$ が$5000$で割り切れ

さらに,以下の方程式について、x,yを解くと0以上の整数解(今回は整数には必ずなので)になればよいです。

  • $2x + y = (Y - 1000 z) / 5000$
  • $x + y = N - z$

それは $x = (Y -1000 z) / 5000 - N + z >= 0$かつ$y = N - z - x >= 0$で判定できます.

fn abc085c(){
    let input: Vec<i32> = read_vec();
    let (n, Y) = (input[0], input[1]);
    let mut flag = false;
    for z in 0..(n+1) {
        if (Y - 1000 * z) % 5000 != 0 { continue }
        let div_y = (Y - 1000 * z) / 5000;
        let x = div_y - n + z;
        let y = n - z - x;
        if x < 0 || y < 0 { continue }
        flag = true;
        println!("{} {} {}", x, y, z);
        break
    }
    if !flag {
        println!("{} {} {}", -1, -1, -1);
    }
}

ABC049C

貪欲に解けばいいです.後ろからの方が楽そうですが,何も考えずに前から解きます.
条件をざっと考えると,

  • 1文字目がeの場合
    • eraser or erase
    • 文字の長さが5かつeraseならYes
    • 文字の長さが6かつeraserならYes
    • 文字列の長さが6以下で上記以外の場合No
    • 6文字目がrならeraserを削除
    • 6文字目がe or dなら eraseを削除
    • それ以外No
  • dreamの場合も同様に分けていけばよい.
    • ただし、dreamera,dreamerd等で区別する必要はある.
n abc049c(){
    let mut s: String = read();
    loop {
        let len = s.len();
        if len < 5 {
            println!("NO");
            break
        }
        if s == "erase" || s == "eraser" || s == "dream" || s == "dreamer" {
            println!("YES");
            break
        }
        if s.chars().nth(0).unwrap() == 'e' {
            if &s[0..6] == "eraser" {
                s = s[6..len].to_string();
            } else if &s[0..5] == "erase" {
                s = s[5..len].to_string();
            } else {
                println!("NO");
                break
            }
        } else if s.chars().nth(0).unwrap() == 'd' {
            if &s[0..7] == "dreamer" {
                if &s[0..8] == "dreamera" {
                    s = s[5..len].to_string();
                } else {
                    s = s[7..len].to_string();
                }
            } else if &s[0..5] == "dream" {
                s = s[5..len].to_string();
            } else {
                println!("NO");
                break
            }
        } else {
            println!("NO");
            break
        }
    }
}

脳直で書いたらひどいコードになってしまった...

いろいろ整理する方法がありますが,今回はアルゴリズムは気にしないことにしたので,妥協します.

ABC086 C

移動時間が最短移動時間$＋2n(n >= 0)$であればよいので、
それに合わせて実装します.

fn abc086c(){
    let n: u32 = read();
    let input: Vec<Vec<i32>> = read_vec2(n);
    let mut old_x = 0;
    let mut old_y = 0;
    let mut old_t = 0;
    let mut flag = true;
    for inp_i in input {
        let (t, x, y) = (inp_i[0], inp_i[1], inp_i[2]);
        let diff = t - old_t - (x - old_x).abs() - (y - old_y).abs();
        if diff < 0 || diff % 2 == 1 {
            println!("No");
            flag = false;
            break;
        } else {
            old_t = t;
            old_x = x;
            old_y = y;
        }
    }
    if flag {
        println!("Yes");
    }
}

感想

なんとか解けました. 感想としては

  • 標準入力は大変だなというお気持ち.
  • 配列のindexがuintでないとエラーになるのはつらい.
  • 常に型を意識するので、コードを書く時間はかかるが、変なミスは減りそう.
  • 実行時エラーをきちんと読むのは大変そう(indexをミスって実行時エラーが何回か発生した)
  • 知識がない状態で書いたので、他の人のコードを見た時の学びが多い.

なによりも

  • 何よりも,慣れれば楽しそうでﾜｸﾜｸする.

参考

最後に今回いろいろ参考にした記事をあげておきます.

8
5
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
8
5

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?