Rust歴3日の私がAtCoderの精選過去問題10問を解きつつRustを雑に紹介する

序

Rustについて

Rust、というプログラミング言語の噂を小耳に挟んだ。

曰く、類稀なる高効率を誇り、GCからも人力メモリ管理からも解放され、厳格な文法によって数多のバグを未然に防ぎ、無に近いオーバーヘッドで高度な抽象化を可能ならしめ、処理速度は鬼の如し、堅牢なること岩の如し、優雅たること鷹の如し、立てば芍薬座れば牡丹、喰う寝る処に住む処、何の話だっけ、とにかく何かがすごいということだ。

触ってみたらことのほか面白かったので、誰に読ませるわけでもないのですが、何か書いておきたいと思った次第です。

AtCoderとは

これです。

• AtCoder

毎週のようにオンラインでコンテストが開かれていて、出されたお題に応じたプログラムを提出して速さを競うというもので、問題の難易度が幅広いので気軽に参加できます。

過去問精選10問とは

こちらの記事からです。

• AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～

公式にもまとめられているみたいですね。

• AtCoder Beginners Selection

様々な言語で「解いてみた」系の派生記事がありまして、ちゃんとRustも既にありますので、あれでしたらそちらをお読みください。私は後になって読んだんですが、こう書けばよかったのか～と思うことしきりです。

• AtCoder に登録したら解くべき精選過去問 10 問を Rust で解いてみた

筆者のバックグラウンド

題の通り、Rustが分かっている人ではありませんし、他の言語に精通しているわけでもありません。

ふだん使っている言語は以下です。

• Haxe（ゲームの個人制作のため）
• Processing（文法は古いJava。お絵かき、いわゆるクリエイティブコーディングのため）
• TypeScript（p5.jsと合わせて、同じくお絵かきのため）

あとAtCoderも最近数回やっただけのレベルです。

対象読者

なにぶん上記の通りですので……

対象外

・RustやAtCoderに関して信頼のおける情報をお探しの人

対象

・Rust初心者が何を考えてどんなコードを書きがちなのか見てみたい人

・なんか知らんがとりあえず読むぞという人

言い訳 Disclaimer

• Rustのバージョンは現時点のAtCoderに準じて v1.15.1 ですので、最新版よりだいぶ古いはずです。
• この記事のコードは学習目的で書いたので、およそ競プロらしからぬコードが多く、それ以外の観点でも怪しいです。
• 実際に解いた時のコードはこちら（GitHub）ですが、話の都合上、この記事に載せるときに変えた部分が多々あります。
• 各問題の題意はとても大雑把に書いており、実際の問題文は各見出しのリンクからご覧ください。
• 毎度場当たり的に調べているので、おそらく推奨されるであろう学習順序に逆行した部分が多いです。
• 細かいこと言うと問題を解いた時点でRust歴約3日、執筆時点ではそこから1週間くらい経っています。
• 最初の準備がスムーズでないので問題を解きに入るまで（1.～3.）が長い
• ご批判あれば甘んじて受ける所存です

1. 標準入出力、変数と参照、Result型

標準出力

実際に問題を解く前に、AtCoderは標準入出力でデータを受け渡しするので、そのやり方を確認する必要があります。

まず標準出力を使ったHelloWorldはこうだ。

main.rs

fn main() {
  println!("Hello, world!");
}

ハハン、どんな難解言語かと思ったら普通の文法ですね。これなら私にもかけそうだ！（）

println!()を介さずstdout()で出力先を取得しても良いようだが、ここでは割愛します。

標準入力

次は入力のほう。軽く調べると、

• stdin()で標準入力を司る何かをゲットできるらしい。
• それのメソッドread_to_string(s)で、あらかじめ用意した文字列sに対して標準入力の内容をロードできるらしい。
• イミュータブルな変数宣言はlet、ミュータブルならlet mutとする。（デフォルトがイミュータブル、いいですね！）
• 関数名や変数名はスネークケース。（個人的にもキャメルケースより好き）

するとこう書けばいいはず……

main.rs

use std::io::*;  // stdin() とかが入ってるやつ、以後省略します

fn main() {
    let mut string_buffer = String::new();  // 可変な空の文字列を用意
    stdin().read_to_string(string_buffer);  // 標準入力からロード
    println!(string_buffer);                // それをそのまま出力
}

error...

error: expected a literal
 --> src\main.rs:6:14
  |
6 |     println!(string_buffer);
  |              ^^^^^^^^^^^^^

なんでや！

println! マクロ

調べると、println!のビックリマーク、これはマクロの意味らしいんですね。println!("{}", s)という形で書くと{}のところに変数sの中身をぶちこんでフォーマットしてくれるという代物で、その代わり変数を直接入れちゃダメだと。あと関数じゃなくてマクロなのは可変長引数に対応するためだとか。

直しました。

error...

 --> src\main.rs:5:28
  |
5 |     stdin().read_to_string(string_buffer);
  |                            ^^^^^^^^^^^^^ expected mutable reference, found struct `std::string::String`
  |
  = note: expected type `&mut std::string::String`
  = note:    found type `std::string::String`

なんでや！

参照および可変参照

reference、参照か～～、ポインタとかを扱ったことのないゆるふわコーダーはこれだからいけません。値じゃなくて参照にしたいときは変数の前に&とつける、さらに可変なものとして渡すなら&mutとつけるらしい、つまりread_to_string(&mut string_buffer)と書けばよかった。

直しました。

warning...

warning: unused result which must be used, #[warn(unused_must_use)] on by default
 --> src\main.rs:5:5
  |
5 |     stdin().read_to_string(&mut string_buffer);
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

なんでや！（コンパイルは通ったが）

Result型

調べると、read_to_string()の戻り値はResult<T, E>型で、成功したらOk<T>、失敗したらErr<E>が返るらしい。これはゼミ、じゃなかったHaxeでやったから分かるんですが、値付きenumというやつでしょうか。Okだったらその中身の値を見て、Errだったら中身のエラー情報をみてエラーハンドリングするわけだ、いいですね。

しかしread_to_string()が返すのは読み込んだバイト数、今回この情報は要らないし、Result型はメソッドok()でエラーを握りつぶせるらしいので、そうしよう（推奨はしません）。

最終的にこれで通りました。

main.rs

fn main() {
    let mut string_buffer = String::new();
    stdin().read_to_string(&mut string_buffer).ok();
    println!("{}", string_buffer);
}

ちなみに、動かして確認するときにどうやって実データを標準入力に渡しているかというと、こういう感じでいにしえのBATファイルを書いたんですが、普通はどうやるんでしょうか、まあ動けばいいか。

2. ライフタイム

さて、ググると分かるのですが入出力の効率についてはちょっと注意が必要らしい。

参考： Rust の標準入出力は(何も考えないで使うと)遅い

stdinに対してreadなんちゃらを呼ぶたびにロックとアンロックがかかるので、何度も読むときはlock()によってあらかじめロックしておいた方が良いとのこと。

この例だと一回しか読んでないから意味ないけど、とりあえずlock()付けてみよう。

main.rs

fn main() {
    let mut string_buffer = String::new();
    stdin().lock().read_to_string(&mut string_buffer).ok();
    println!("{}", string_buffer);
}

error...

error: borrowed value does not live long enough
  --> src\main.rs:16:59
   |
16 |     stdin().lock().read_to_string(&mut string_buffer).ok();
   |     ------- temporary value created here                  ^ temporary value dropped here while still borrowed
   |
   = note: values in a scope are dropped in the opposite order they are created
   = note: consider using a `let` binding to increase its lifetime

なんでや！

そういえばRustにはライフタイムという独特の概念があると聞きます。ある変数がメモリのどこかを参照しているとき、参照先が解放されて無効な状態になっているのに気付かず参照だけが残ってしまう、というのがC/C++でありがちな話で（若干違うけどC/C++以外でもオブジェクトプーリングしたときに悩まされる話である）、それを防ぐため、Rustはコンパイラさんがあらゆる値のライフタイムすなわち生存期間を管理してくれるというんですね。

なるほどなと思いつつ、これがそうなの？？ というのが最初は結びつかなかったんですが、とりあえずメッセージに従って直してみます。

main.rs

fn main() {
    let mut string_buffer = String::new();

    let stdin = stdin();  // いったんここで束縛
    stdin.lock().read_to_string(&mut string_buffer).ok();

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

直った。

どうもletは他の言語の変数宣言の感覚で使うだけではないらしい。そもそも用語からして違う、正しくは「宣言」ではなく「束縛」と呼ぶ。letで束縛することで、変数がそのスコープの範囲内（この例だとmain()の中）で生存できるようになるようです。

それをやってなかったので、ロックしようにも一瞬で死んじゃうぞ、ロックするってことは後で使いたいわけだろ、ならまずロックする対象を生存させておきたまえ……という理解で良いんでしょうか？　何にしても、そこまで見てくれるんだなというのは面白いです。

「プログラミング言語Rust」のライフタイムの項を読むと、まず「所有権」と「借用」を理解するのが先っぽいので、順序がまずかったかもしれません。

3. クロージャと高階関数（未遂）

さて、ロックしたstdinからデータを複数回読み込むことができるはずなので、そのへんをクロージャにしてmain()の中をすっきりさせたくなってきた。例えばJavaScriptだとアロー関数で(引数) => 処理とやって、そこに環境を埋め込むやつですね（記法の話とクロージャはイコールではない、為念）。

Rustだとクロージャは

|引数| 戻り値

という形らしい。

クロージャを返す関数

「標準入力を読んでくれるクロージャ」を作る関数、を作ろう。クロージャの型の書き方がまだよく分からんが、見よう見まねで、こんな感じでしょうか……

main.rs

fn create_fn_read_stdin() -> (Fn() -> String) {
    let stdin = stdin();
    let mut locked_stdin = stdin.lock();    // ロック済みのstdinが裏で保持される（という目論見）

    // 引数なしのクロージャを戻り値にする
    || {
        let mut string_buffer = String::new();
        locked_stdin.read_to_string(&mut string_buffer).ok();
        string_buffer
    }
}

fn main() {
    let read_stdin = create_fn_read_stdin();  // 「標準入力の内容を返すクロージャ」を作る
    let input_string = read_stdin();          // それを呼ぶことで標準入力の内容を得る
    println!("{}", input_string);             // 出力する
}

error...

（省略）
error: aborting due to 6 previous errors

なんでや！

エラーで真っ赤になりました。まず、「プログラミング言語Rust」のクロージャの項を読むと、クロージャを返すときにはBox<>で包むのだという。まあそういうこともあらぁなという感じで、直します。

error...

error: `stdin` does not live long enough
  --> src\main.rs:5:28
   |
5  |     let mut locked_stdin = stdin.lock();
   |                            ^^^^^ does not live long enough
（省略）
   = note: borrowed value must be valid for the static lifetime...

なんでや！

関数を抜けるとライフタイムが終わる

create_fn_read_stdin()を出た時点でstdinのライフタイムが終わっちゃうようで、やっぱりライフタイムってそういう感じなんですね？ 定義からしてそうなのだろうというのは分かるけど、ではJavaScriptのノリでこういうことをやりたいときにどうするのか？

ライフタイム修飾子<a'>とかでライフタイムを明示的に指定できるらしくて、それでどうにかできるのかもしれませんが、すみませんが私はここでいったん諦めました（その後、複数の記事を参考にしてこういう感じになりつつありますが、未だによく分かってないし、計測とか何もしてないので効率も不明です）。

いいかげん問題を解きましょう。ちなみにこの時点でだいぶ心を折られかけていましたが、幸いそれ以降は面白くなる一方でした、最初はあれこれ頑張ろうとしないほうがいいね。

以降、この記事の冒頭のものをちょこっとだけ変えたread()関数で入力を読むこととします（実際に解いたときは都度やり方を変えてましたが、簡単のため）。スペース・改行関係なく、read()を一回呼ぶたびに次の区切り文字までを読み込みます。

main.rs

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

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let s = stdin.bytes().map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok().unwrap()
}

fn main() {
    // 使い方
    let u32_value = read::<u32>(); // データ型を指定して呼ぶ。u32は32bit符号なし整数
    let string_value: String = read(); // 変数側の型が決まってれば推論される
}

4. イテレータと加算

PracticeA - Welcome to AtCoder

精選過去問題10問の前に、AtCoder操作確認用の練習問題です。

整数 A, B, C と文字列 S が与えられるので、 ABC の合計と S をスペース区切りで出せ、というもの（実際の問題文は見出しのリンク先参照、以下同様）。

個別に読むならこうか。

main.rs

fn main() {
    let a = read::<u32>();
    let b = read::<u32>();
    let c = read::<u32>();
    let s = read::<String>();

    println!("{} {}", a + b + c, s);
}

でもABCのところは読み込みと加算を一気にやりたいなあ、JavaScriptのreduce()みたいなのあるかなと思ったら、fold()というのがありました。

こうなりました。

main.rs

fn main() {
    let abc_sum = (0..3).fold(0, |acc, _| acc + read::<u32>());

    let s: String = read();

    println!("{} {}", abc_sum, s);
}

0..3というのが、普通のforでいうfor (int i = 0; i < 3; i++)に該当する感じですね。後で分かった話だが0..3はイテレータという扱いになっていて、0以上3未満の数値を逐次生成する能力を持った何かであり、宣言した時点で[0, 1, 2]みたいな配列がまるごと生成されているわけではない、ということなのでなかなかスマートではありませんか。

fold()に投げ込んだクロージャ|acc, _| acc + read::<u32>()の方で第2引数に 0, 1, 2 が入るわけですが、この数値自体を使うわけではないのでアンダーバー _ にしている。未使用変数があるとコンパイラがワーニングを出しますが、アンダーバーまたはそれで始まる名前にしたときだけ無視されるようです（これも後で知ったがそもそも束縛されないようだ。参考： Rustのパターンマッチを完全に理解した）。

そして、この時点では気付かなかったけど普通にsum()というのもあって、さっきのfold()のところはこうも書ける。

let abc_sum: u32 = (0..3).map(|_| read::<u32>()).sum();

単に合計するだけならこれがいいですね、ただこっちはabc_sumの型を明記する必要があった。

5. ジェネリクス

問1: ABC086A - Product

整数 A, B が与えられるので、その積の偶奇を判定せよというもの。

ここでこれやる意味まったくないんだけど、なんとなくジェネリクスのやり方を確認したくなったので、「偶奇に応じて、任意の型で別の値を返す関数」を作ってみます。

fn map_parity<T>(n: u32, even_value: T, odd_value: T) -> T {
    if n & 1 == 0 {
        even_value
    } else {
        odd_value
    }
}

使う側はこうだ。

main.rs

fn main() {
    let a = read::<u32>();
    let b = read::<u32>();
    println!("{}", map_parity(a * b, "Even", "Odd"));
}

通った。よくある文法で行けるようだ。

ifが式になるのいいですね、条件式の()が要らないのもいい。代わりに{}が省略できないのと、3項演算子が無いので不便に思うこともあるんですが、いろいろ議論された結果そうなっているようなので、それはそれでいいかという感じです。

あと、セミコロンの有無でまったく意味が違ってきて（式と文の違いなんですがなんて表現したらいいのか？）、関数の最後にセミコロンなしの何かがあるとそれが戻り値になるので、早期returnを別にするとあまりreturnを書かなくて良い、このへんも割と好きです。

6. Option型、他

問2: ABC081A - Placing Marbles

010とか110とかの文字列が与えられるので、1をカウントせよというもの。

文字列→二進数

普通に文字を数えればいいんですが、せっかくなので二進数として処理してみたいので、標準入力から0と1からなる文字列を取得して、それを二進数として読む関数を作る。ググったらfrom_str_radix()というのがありました。

fn read_bits() -> u32 {
    let input_string = read::<String>();
    u32::from_str_radix(&input_string, 2).ok().unwrap()
}

データ型u32の後にコロン2つ、それに関数名を続けるようだ。Javaその他でいうところのstaticメソッドに該当する関数がこういう呼び方になって、インスタンスメソッドにあたる関数がドットで繋ぐ感じになる、ということでいいのか？

このへんは後述のtraitとimplを知ったあたりでもう少しイメージができてきましたが、私は最初コロン2つ書くのに慣れず、ドットで繋ごうとして認識されずに なんでや！ なんでや！ となるのを繰り返してました。

Option型

そして、上で書いたようにResult型のエラーをok()で握りつぶせるわけだが、その戻り値がなにかというとOption<T>型、これもまたenumで、取りえる値がSome<T>かNoneになるらしい。通常ならそれぞれに対応した処理を書いて、Noneである場合を考えなくて良いならunwrap()でSome<T>の中身を取り出すことができる（そのときNoneだと強制終了する、Rustだとpanicと呼ぶようです）。

Scalaやその他の言語でもこういう型があると聞きますが、つまり知らんうちにnullになってたみたいなやつを防げるわけで、こういうのにどれだけ救われることか！

個人的な好みとしても、よくあるindexOf()とかで探し物が見つからなかったときに-1が返ってきたりするやつ、特定の値に意味を持たせるんじゃなくて無かったら無かったいう専用の何かを返してほしいよなという感じなんですが、このOption型があるとそういうときにNoneが返ってくるわけで、分かりやすくて良いです。

文字列の型

あと、from_str_radix()の第1引数がString型とはまた別の&str型で、それに直すためにinput_stringに&を付けている。Stringと&strは、後述のVecとスライスの関係に対応していて、ここでは端折りますがこのへんも理解していかねばという状態です。

参考： Stringとstr入門

これは後でまた出てきます。

結果

さて、ビット列をu32型で取得したので、あとはその中の1を数えて出力する。こうかと。

main.rs

fn count_bits(bits: u32, len: u32) -> u32 {
    let mut bits = bits;
    (0..len).fold(0, |acc, _| {
        let next = if bits & 1 == 1 { acc + 1 } else { acc };
        bits = bits >> 1;
        next
    })
}

fn main() {
    println!("{}", count_bits(read_bits(), 3));
}

後で気付きましたが（まさか標準で用意されてると思わなかった）、ずばりcount_ones()というのがあって、それでスパッと書けましたね。

main.rs

fn main() {
    println!("{}", read_bits().count_ones());
}

7. Vec型、Result型の活用、他

問3: ABC081B - Shift only

与えられた整数の数列について、「各要素を余りなく2で割る」という操作を何回実行できるか、を答えるというもの。

Vec型

まず数列を読み込んでリストを返す関数を用意しておこう。Vec<T>がよく使う可変長リストのようなので、それを戻り値にします。下記のようにイテレータから始めて最後にcollect()を呼ぶと、型推論して適切な型（つまりこの場合Vec<T>）にしてくれるのだ！ 賢い。

fn read_vec<T: FromStr>(length: usize) -> Vec<T> {
    (0..length).map(|_| read::<T>()).collect()
}

整数型いろいろ

ちなみにusizeというのは符号なし整数、かつそのマシンのポインタサイズに対応したサイズになるとのことで、つまり 64bit OS だとu64と同じサイズということでしょうか。リストのインデックスや長さが規定でusizeになっているので、私は現時点では

• インデックスや長さとして使う整数はusize
• それ以外の整数はu32やその他、値の範囲に応じた整数型

という感じで使っていますが、暗黙の型変換は無いので、変換が面倒だったりする場合は基本usize（符号ありならisize）でもいいのかもしれません、でもまだよくは分かってない。

Result型を返す自作関数

さて次に、この問題をどう解くか。とりあえず問題文の通りに愚直に操作を繰り返そう、ということで「数列の各要素を2で割る（破壊的変更）、奇数を発見したら中断してエラーを返す」という関数を作ってみる。ここで上述のResult<T>型が使えそうだなと思いました。

use std::result::Result;

fn divide_each_by_two(numbers: &mut Vec<u32>) -> Result<(), usize> {
    for i in 0..numbers.len() {
        if numbers[i] & 1 == 1 {
            return Err(i);
        }

        numbers[i] >>= 1;
    }

    Ok(())
}

Rustは「タプル型」という型があって、(1, 2, "a")みたいに異なる型の値をまとめた型を作れるんですが、これのもう一つの使い方として、void的なものを返したいときに空のタプル()を使うようなのですね。

OKだった場合は他に特に情報が無いので、空タプルを包んだOk(())を返す。奇数があった場合は、（今回別に使わないんだけど）当該のインデックスをErr()で包んで返す、としてみた。

これらを使った本処理はこうだ。

main.rs

fn main() {
    let n = read::<usize>();
    let a = &mut read_vec::<u32>(n);
    let mut count = 0;

    while divide_each_by_two(a).is_ok() {
        count += 1;
    }

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

「操作して結果OKだったらカウントする」というのを繰り返すという、そのままを記述できました（aの破壊的変更が若干気持ち悪いかもしれませんが）。

これも後で気付いたけど、この記事のコードの方が圧倒的にクールに見えます（見る順序が違うのでテストケース次第かもしれませんが）。「2で何回割れるか」は二進数にしたときに末尾のゼロを数えればよく、しかもこれもtrailing_zeros()というのがあるので、それを使ってスパッと書かれています、まさか標準であるとは……。

8. イテレータと加算（２）

問4: ABC087B - Coins

整数 A, B, C, X が与えられる。500円玉がA枚、100円玉がB枚、50円玉がC枚あって、そこから選んで合計がX円となるような組み合わせが何通りあるか？ という問題。

グワーッこれは多重ループだ、普通にforで回せばいいんですが、他にないかなぁ思って、私が書いたのはこうでした。

main.rs

fn main() {
    let a = read::<u32>();
    let b = read::<u32>();
    let c = read::<u32>();
    let x = read::<u32>();

    let c_max_amount = c * 50;
    let mut valid_count = 0;

    (0..a + 1).fold(0, |a_amount, _| {
        (0..b + 1).fold(a_amount, |ab_amount, _| {
            if ab_amount <= x && x <= ab_amount + c_max_amount {
                valid_count += 1;
            }
            ab_amount + 100
        });
        a_amount + 500
    });

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

今見ると若干なんじゃこりゃ感があって、fold()じゃなくて他にないのかなという感じです。後述の問題 ABC085C で同じような多重ループをするので、続きはそちらで。

9. 所有権と借用

問題をいくつか解いたところで、個々の問題から離れますがこの話をしたい。なぜ問題から独立なのかというと、もうとにかくあらゆる場面でコンパイラに怒られまくって、逆に個別の事例を忘れちゃったからです。

既にあちこちで行われているのとまったく同じ説明になっちゃいますが、まずはこちらを。

fn main() {
    let mut words = Vec::new();
    words.push("apple");

    println!("{}", words[0]);
}

これは普通に"apple"と出力されます。

これの途中に1行挿入しただけで……

fn main() {
    let mut words = Vec::new();
    words.push("apple");

    let other_words = words; // new!

    println!("{}", words[0]);
}

error...

error[E0382]: use of moved value: `words`
 --> src\main.rs:7:20
  |
5 |     let other_words = words;
  |         ----------- value moved here
6 | 
7 |     println!("{}", words[0]);
  |                    ^^^^^ value used here after move
  |
  = note: move occurs because `words` has type `std::vec::Vec<&str>`, which does not implement the `Copy` trait

なんでや！（other_wordsが増えただけで、words自体は何もいじっていないのに）

となるのがRustなんですが、これは徹底したメモリ管理のため、「一つのデータを束縛する変数は一つだけ」という規則があるのですね。最初に作ったVec型データの所有権がother_wordsに移動したので、元のwordsはもはや使えないのだという。

これはwordsを何か関数に渡すときも同様で、渡した時点で所有権が移動してしまいます。

fn print_word(words:Vec<&str>, index: usize) {
    println!("{}", words[index]);
}

fn main() {
    let mut words = Vec::new();
    words.push("apple");

    print_word(words, 0); // 渡した先にwordsの中身の所有権が移動

    println!("{}", words[0]); // error
}

一般的に、気付かない所でデータが書き換わったためにバグが生まれる、というケースがものすごく多いことを思えば、なるほどなという感じではあります。

所有権を移動させずにデータを見せたければ、参照を渡せばよい。

// 引数のVec型に "&" を付けた。参照を受け取ることができる
fn print_word(words: &Vec<&str>, index: usize) {
    println!("{}", words[index]);
}

fn main() {
    let mut words = Vec::new();
    words.push("apple");

    print_word(&words, 0); // "&" を付けて参照を渡す

    println!("{}", words[0]); //OK
}

このとき、参照を渡された側は所有権を「借用」した、と表現するようです。

これで解決じゃんと思うところですが、値の変更が絡むとさらに制約があって（Programming Rust の「参照と借用」の項だとか、他の解説を見ていただきたい）、ちょっと何かするたびになかなかパズルめいた状況が発生します。

さいきん困ったのはクロージャで、こういうやつ。

fn main() {
    let mut count = 0;

    // 数値を渡すとそれをcountに足してくれるクロージャ
    let mut add_count = |val_to_add| count += val_to_add;
    add_count(3);

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

error...

error[E0502]: cannot borrow `count` as immutable because it is also borrowed as mutable
 --> src\main.rs:7:20
  |
4 |     let mut add_count = |val_to_add| count += val_to_add;
  |                         ------------ ----- previous borrow occurs due to use of `count` in closure
  |                         |
  |                         mutable borrow occurs here
...
7 |     println!("{}", count);
  |                    ^^^^^ immutable borrow occurs here
8 | }
  | - mutable borrow ends here

add_count()がcountを借用してて、かつ値を変更する可能性があるから、他の人にcountは見せられないよ！ 何が入ってるか分かったもんじゃないからね！ ということでprintln!()で使えなくなる。

その後分かったんですがこれは{}でスコープを作ればいいんですね。

fn main() {
    let mut count = 0;

    {
        let mut add_count = |val_to_add| count += val_to_add;
        add_count(3);
    } // このスコープを抜けた時点で借用が終了する

    println!("{}", count); // OK
}

値を、いつ！ 誰が！ どこで！ 変更するのか！ それを、他の誰が！ いつ！ どこで！ 見るのか！ きっちり管理する！ それがRustだァーッ！

というわけで、大変ではあるけど頼もしくもあり、強制的に行儀の良いコードを書かされる言語なのだと思えば、チャレンジする価値もあるというもの、かもしれません（正直、よく分からないまま&を付けたり外したりしてコンパイラの機嫌をうかがい、直った時も理由が分からないなんてことがまだまだありますが……）。

閑話休題。

10. trait、impl、struct、自作イテレータ

問5: ABC083B - Some Sums

整数 N, A, B が与えられる。1以上N以下の整数のうち、10進法での各桁の和がA以上B以下であるものの総和を求めよ、というもの。

文字列型を経由すれば楽そうですが、（意味あるかはともかく）型の変換を伴わない方法でやってみたい。あとそういう具体的な処理を外に追い出して、main()の中では「各桁の和がA～Bに収まる数だけを合計する」という抽象的な操作だけを書くようにしたい。

そこで、main()がどういう形になってほしいかを先に書いてみると、こうです。

main.rs

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

    let valid_range = a..b + 1;

    let sum: u32 = (1..n + 1)                                   // 整数 1～N のうち
        .filter(|n| valid_range.includes(n.digits(10).sum()))   // 各桁の和が A～B に含まれるもの
        .sum();                                                 // の、合計

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

includes()やdigits()なんてものは存在しないので、それを作ります。

traitとimpl

まずincludes()を作る。

a..b + 1とか1..n + 1というのがイテレータであると上の方で書いたけど、具体的な型としてはRange<T>型らしい。こいつは今のRustだとcontains()というのを持っているんですが、AtCoderで使われる Rust v1.15.1 では使えないので、やむなく再実装します。

このように、既存の型に対して独自のメソッドを生やすようなことができるものなのか？ と思ったら、なんとできるのである。ググった結果知ったのはtraitなるものの存在であった。

まずこのように宣言します。

trait CheckRange {
    fn includes(&self, n: u32) -> bool;
}

これは、似て非なるものかもしれませんが他の言語でいうインタフェースみたいな雰囲気の代物で、ある型が提供する機能を定義するものらしい。CheckRangeって命名しちゃったの、動詞は良くないかもしれないんだけど、名詞か形容詞がいいのかな？

そして実装をどこに書くかというと、こうだ。

use std::ops::Range;

impl CheckRange for Range<u32> {
    fn includes(&self, n: u32) -> bool {
        self.start <= n && n < self.end
    }
}

implでimplementする。こう書いておくと、Range<u32>型のデータに対してincludes()を呼べるようになって、例えば

(0..10).includes(3) // これは true になる

とか書くと、引数の&selfのところに自分自身すなわち0..10への参照が入る。

ちなみにstartとendはRangeがもともと持っているフィールドです。これだとstart > endのときにダメな気がするけど、まあいいや、このようにしてメソッドを生やせるんですね。素晴らしい。

ついでなので、上記のCheckRangeがu32型しか対応してないのをジェネリックにしたいと思ったんですけど、少なくともv.1.15.1だと、「整数」だとか「符号なし整数」などといった大きなくくりを簡単に指定する方法が無いように見えます。雑な変換を許す言語ではないだろうし、仕方ないのかも。

そこで、そもそもRange<T>のTにはどういう制約があるのか調べたところ、PartialOrdという組み込みのtraitでした。それでu32を置き換えてみます。

use std::cmp::PartialOrd;
use std::ops::Range;

trait CheckRange<T: PartialOrd> {
    fn includes(&self, n: T) -> bool;
}

impl<T: PartialOrd> CheckRange<T> for Range<T> {
    fn includes(&self, n: T) -> bool {
        self.start <= n && n < self.end
    }
}

このように書くと、大小比較が可能である全ての型を、Tのところに投げ込むことができる。

PartialOrdで比較処理を実装した型（少なくとも数値型はみんなそうなはず）は、実態がなんであれ不等号による比較が可能になるというんですね。比較だけでなく加減算とかの操作も同様らしく、そういう基本的なところまでtraitで制御されてるんだな～というのは、一貫性があって素敵です。

さてinlude()ができたので、同様に、もう一つのdigits()というのを整数型に生やしたいと思います。

これは、例えば321.digits()のように呼んだとき、1, 2, 3 （順番はどっちでもいいですが）を逐次的に出してくれるイテレータを返してほしい。ので、いったんそのようなtraitとimplを書きます。

trait Digits {
    fn digits(self, base: u32) -> DigitIterator;
}

impl Digits for u32 {
    fn digits(self, base: u32) -> DigitIterator {
        DigitIterator {
            value: self,
            base: base,
        }
    }
}

これもジェネリックにしたかったけど、今度はParticalOrdも関係ないし、よくわかんなかった（他にFrom<T>とかInto<T>などの変換系traitもあって、便利ではあるがデフォルトでu系とi系の間では定義されておらず、もう少し範囲の広いTryFrom<T>とかは v.1.15.1 にはまだないという感じでした）。

そして、上で断りもなく登場しているDigitIteratorは独自のイテレータでして、次で作ります。

structと独自イテレータ

イテレータはどう作るのか？

このページに例がありました。イテレータもまたひとつのIteratorというtraitであって、そこで定義されているnext()というメソッドを実装すれば実体はなんでも良いのであった。

それと、恐らくtraitよりも基礎的な話な気がするので順番が前後しちゃうけど、Rustのデータ構造の一つにstructというのがありました。構造体ですね。struct自体はただのデータの入れ物で、Rustの場合、これもまたimplでメソッドを実装することができる。

そうすると、イテレータを作るのにもstructが必要に思えます、なぜならどこまでイテレーションを回したかという状態を保持するための入れ物が必要だからだ。

以上を念頭に、こういう風に作ってみました。

struct DigitIterator {
    value: u32,
    base: u32,
}

impl Iterator for DigitIterator {
    type Item = u32;

    fn next(&mut self) -> Option<Self::Item> {
        if self.value > 0 {
            let digit = self.value % self.base;
            self.value /= self.base;
            Some(digit)
        } else {
            None
        }
    }
}

baseというのは、10進数なら10を入れる感じ。こうすると、next()を呼ぶたびに次の桁が返ってきて、全部の桁を見た後はNoneが返ることになります。これだと逆順イテレートはできませんが……。

以上で準備が整いまして、最初に書いたこれが見事に動きました、やったね。

// Range型の valid_range が、整数 n の各桁の和を含むなら、true
valid_range.includes(n.digits(10).sum()))

（だいぶ長くなってしまった、繰り返しますが問題を解くだけならもっと簡単に済む話です）

問6: ABC088B - Card Game for Two

要は与えられた複数の整数を大きい順にソートし、2人で交互に取っていけばいいという問題ですね。

traitの復習ということで、偶奇を判断する超簡単なメソッドを作ってみる。

trait Parity {
    fn is_even(self) -> bool;
}

impl Parity for usize {
    fn is_even(self) -> bool {
        self & 1 == 0
    }
}

これで、例えば 2.is_even() でtrueが返る。

そしてmain()はこうなりました。

main.rs

fn main() {
    let n = read::<usize>();
    let mut a = read_vec::<u32>(n);

    a.sort_by(|a, b| b.partial_cmp(a).unwrap()); // 降順ソート

    let mut alice_points: u32 = 0;
    let mut bob_points: u32 = 0;

    for index in 0..n {
        if index.is_even() {
            alice_points += a[index];
        } else {
            bob_points += a[index];
        }
    }

    println!("{}", alice_points - bob_points);
}

partial_cmp()というのは上述のtrait PartialOrd が持っているメソッドで、戻り値はOrdering型（これまたenum、値はLessEqualGreaterの3種）。このOrdering型を返すクロージャをsort_by()に投げ込めば任意の条件でソートできるようです。こればっかりはタイプ数が多くてウヘッとなりますが仕方ない。

あと、もしやインデックスに応じて要素を振り分けるような関数が既にあったりしないかと探しましたが、なさそうでした（要素自体を見て分類するやつならイテレータのメソッドでpartition()というのがあって、これじゃん、あ、ちゃうわ、となった）。

11. イテレータの活用

問7: ABC085B - Kagami Mochi

これは重複を削除した数を数えれば終わりなので、すぐです。

use std::collections::HashSet;

fn main() {
    let n = read::<usize>();
    let d = read_vec::<u32>(n);

    let mochimochi_diameter_set: HashSet<u32> = d.into_iter().collect();

    println!("{}", mochimochi_diameter_set.len());
}

collect()は上述のread_vec()を作るときにも使いましたが、型を書いておけば勝手にそこに収めてくれるので便利ですね。

あと、Vec<T>、そしてまだ使ってませんが配列やスライス（後述）についても、他の言語のfor ～ inとかfor ～ ofみたいに直接イテレートする方法が無くて、何をするにもiter()やinto_iter()でイテレータに変換する必要があるようです。変換といっても特段コストがあるわけではないのだと思われるし、イテレートするならイテレータの仕事だッ！ イテレータに任せろッ！ という一貫性を感じるので割と好きです。なおiter()とinto_iter()はそれぞれ参照を見るか値を見るかということらしくて、使い分けはまだあんまり消化できていません。

セットはHashSetでいいのかな？ と思ったら他にもBTreeSetというのがあったし、そもそもVec<T>から重複を削除するdedup()というメソッドもありました。逐次的に読んでセットに投入するか、上の例のようにVecに降ろした場合はdedup()するか、どちらかにすれば良かった。

問8: ABC085C - Otoshidama

お札が各種合わせてN枚ある、その合計がY円になるようなお札の組み合わせを一つ答えよ、という問題。また出たッ！ 多重ループだッ！（という気分になります）

この問題も普通にforで良いのだが、10000円が0枚、1枚、2枚……という具合に全探索するとなると、この金額は0始まりの等差数列ではないか。ということで練習がてらイテレータの形で等差数列を作ってみます。負数は考えないこととする。

struct ArithmeticProgression {
    value: u32,
    common_difference: u32,
}

impl Iterator for ArithmeticProgression {
    type Item = u32;

    fn next(&mut self) -> Option<Self::Item> {
        let next = self.value;
        self.value += self.common_difference;
        Some(next)
    }
}

ついでに、このようにstaticメソッド（Rustでは関連関数というらしい）を用意すると、この数列をnew()で作れるようになります。この例ではただ書き方が変わるだけだが。

impl ArithmeticProgression {
    fn new(initial_value: u32, common_difference: u32) -> ArithmeticProgression {
        ArithmeticProgression {
            value: initial_value,
            common_difference: common_difference,
        }
    }
}

仮に、あらかじめ配列か何かで有限の数列を作っておく場合だと、要素の個数を指定するか、数値の上限を定めるか、などで個別の作り方が必要になってしまうと思います。けど上のようにして無限に続くイテレータを作っておくと、後で用途に応じて好きに切り取る（例えばtake()で指定個数を取ったり、take_while()で条件に当てはまる特定連続範囲を取ったり、他色々）ということができるので便利だなと思いました。

今回の問題については、例えば次のようなものを用意できる。

type Bills = (usize, u32); // お札の枚数と金額の組
type Pattern = Vec<Bills>; // 各種お札をまとめる用

fn find_valid_pattern<F>(unit_amount: u32, repetition: usize, validate: F) -> Option<Pattern>
where
    F: Fn(Bills) -> Option<Pattern>,
{
    ArithmeticProgression::new(0, unit_amount)
        .take(repetition)     // 要素を指定個数だけ取る
        .enumerate()          // 添え字を付ける。各要素が(枚数, 金額)のタプルになる
        .filter_map(validate) // 有効なパターンだけ残して変換する
        .next()               // 1つめを取る
}

typeというのは型エイリアスで、とりあえず別名を付けているだけです。

この関数にお札の金額と枚数を入れる、例えば1万円を100枚まで使って有効なパターンを1つ探してね、とやることができて、実際は1万円の枚数だけでは判断しようがないので残りの5000円と1000円を使った全探索をvalidateの中でやらせる（その中で再びfind_valid_pattern()を呼ぶ）という寸法です。

あとは省略しますが全体像としてはこういう感じ（GitHub）、ただもっといい書き方あると思うし、繰り返すがそもそもforで済む話です。

Rustのイテレータが遅延評価である、と分かってきたのがこのコードを書いているあたりだったかと思います。つまり最終的に欲しい結果から逆算してコンパイラが実際の手順を考えてくれるので、上の例だと有効なパターンが見つかった時点で処理が完了し、それ以降の見なくてもいい要素についてはいちいち処理をしない、という風になるのが分かって、すごいじゃん、となりました。

12. 文字列、スライス

問9: ABC049C - 白昼夢 / Daydream

文字列Sが与えられる。'dream' 'dreamer' 'erase' 'eraser' を組み合わせてSと同じ文字列を作れるか？ というもの。

Sを先頭から読んでいくと場合分けに苦労するのですが、この4単語のいずれかがSの末尾にあればそれを削る、これを繰り返してSが空になればYES、という解き方ができます。

例えば、まず次のクロージャを作る。文字列を投げ込むと、末尾から4単語のいずれかを削ることを試み、削った後の文字列の長さをOption型で返します。どの単語も一致しなかったらNoneです。

let words = ["dream", "dreamer", "erase", "eraser"];
let try_drop_tail = |s: &str| -> Option<usize> {
    words.into_iter().filter_map(|word| {
        if s.ends_with(word) {
            Some(s.len() - word.len())
        } else {
            None
        }
    }).next()
};

削った文字列を直接返したかったんですが、ライフタイムが矛盾しているゾと怒られてしまい、直し方が分からなかったのでこうなりました。

あとは、これを繰り返し使ってSを削り切ることが可能かどうかを見ればよさそうです。

main.rs

fn main() {
    let s: &str = &read::<String>();

    // クロージャ try_drop_tail の定義（省略）

    let mut sub_str = s;

    while sub_str.len() > 0 {
        match try_drop_tail(sub_str) {
            Some(val) => sub_str = &s[0..val],
            None => {
                println!("NO");
                return;
            }
        };
    }

    println!("YES");
}

この&s[0..val]というのは、スライス表記というのを使って部分文字列を作っています。

&str型というのは文字列のスライスであり、スライスというのは他のコレクション（文字列や配列）の特定範囲を参照するための何かであるということで（参考： Stringとstr入門）、つまり実データのコピーや加工を伴わないんですね。

例えば文字列をsplitしたときにいちいち新たな部分文字列のデータを作り出さなくて良いわけで、出身言語によって感じ方違うかもしれませんが、ウワーッ画期的じゃん、などと思ってしまいました。

あとmatchって上の方で使ったっけ、使ってないな、いわゆるパターンマッチというやつで、ある値を見てSome(何か)だったら中身の何かを使って処理や戻り値を云々、というのを一息に書けるので便利。余談だがHaxeだとswitchがこれを兼ねていた記憶があります。

13. structの活用、自作マクロ

問10: ABC086C - Traveling

二次元平面上で、1秒ごとにx方向かy方向のどちらかに1マス動くとする。t秒目に座標(x, y)に到着せよ、という指示が複数与えられるが、すべての指示をクリアすることは可能か？　というもの。

移動パターンを図に描くと気付くのですが、ある一定時間が与えられたときに到達可能なポイントの規則を考えると、移動量≦時間、かつ移動量と時間の偶奇が同じ、というのが条件になるんですね。

原点から1つ目のチェックポイントへ到達可能か？　そこから2つ目へは到達可能か？　というのを順に見れば良さそうです。

コピー可能なstruct

まずチェックポイントの構造体を定義しよう。

#[derive(Copy, Clone)]
struct Point {
    t: i32,
    x: i32,
    y: i32,
}

使うときは時刻も位置も一緒に見るので、t, x, y をいっしょくたにしています。また、2番目のポイントから見た3番目のポイント、みたいな相対位置を知りたい、つまり引き算がしたいので符号あり整数にしています。

#[derive(Copy, Clone)]が何なのかというと、CopyやCloneというのはそういう既存のtraitで、deriveというのはそれらの既存の実装を継承するものらしい。で、そもそもRustでは何をするにも所有権をムーブしたり借用したりということが行われますが、CopyとCloneを継承した型は値のコピーが可能になり、必要な都度コピーされるので所有権やライフタイムで怒られることがなくなるという話です。

C++とかで、ひとかたまりのデータが小さければ構造体、大きいとコピーのコストが非効率なのでクラスにする、みたいな話を聞いたことがありますが（C++エアプです）、所有権の話を抜きにするとこれと似た雰囲気の話になるのでしょうか？

なおRustのこれは構造体に限ったことではなく、u32などのプリミティブな値はデフォルトでCopyが実装されていて、ゆえに適当に代入したり関数に渡したりしても怒られないという結果になっているようです。値型として例外扱いされている、みたいな感じではないわけですね。

そして自作の構造体をどうするかですが、公式情報で「一般論として、コピー可能にできるならそうすべき」みたいな文面があったので、そうしてみたという次第です。

ついでに標準入力からこれを読む関数も作っておく。

fn read_point() -> Point {
    Point {
        t: read::<i32>(),
        x: read::<i32>(),
        y: read::<i32>(),
    }
}

演算子オーバーロード

次に、上のPoint構造体の引き算を実装します。

大小比較を行うtraitPartialOrdの話をしたときに、加減算とかも同様と書きましたが、減算の機能を持つのがSubというtrait。

use std::ops::Sub;

impl Sub for Point {
    type Output = Point;

    fn sub(self, other: Point) -> Point {
        Point {
            t: self.t - other.t,
            x: self.x - other.x,
            y: self.y - other.y,
        }
    }
}

これはオーバーロードなんだろうか、既存の型が実装しているtraitを新たな型でも実装しただけというべきかもしれませんが、とにかくこれでマイナス記号で引き算ができます。

自作マクロ

次に、偶奇を比較するという話があったので、Pointから一旦離れてそれをやります。そんなのは直接書けばいい話ではあるが、せっかくなので。

問6あたりで作ったtrait Parity、それにhas_same_parity()なる関数を加えてみる。

trait Parity {
    fn is_even(self) -> bool;
    fn has_same_parity<T: Parity>(self, other: T) -> bool;
}

これについて、複数の数値型をまとめてジェネリクスにするのができないなあという話をしましたが、ググったところ、外部のクレート（Rustにおけるライブラリのようなもの）に頼らないのならマクロでやるしかないらしい。見よう見まねでこうなりました。

macro_rules! impl_parity {
    ($($t:ty),+) => {
        $(impl Parity for $t {
            fn is_even(self) -> bool {
                self & 1 == 0
            }
            fn has_same_parity<T: Parity>(self, other: T) -> bool {
                self.is_even() == other.is_even()
            }
        })+
    }
}

impl_parity!(u32);

こうすると、impl_parity!()という自作マクロが定義され、それに可変長引数で複数の型を渡せるので、例えば（今回必要ないけど）u32, usize, i32, isizeみたいにまとめて渡すと、implの中身がそれぞれに個別に実装されるようです。tyという謎の二文字、これは型を渡せますよということみたいですね。ただしこれだと型の違う数値の偶奇は結局比較できない。

普通こういうことをしたいときはnumというクレートがあってそれを使うらしい、というか細かく分かれたいろんなクレートを使い分けるのがRustですよという話を聞いていますが、AtCoderで使えないだろうしなぁ、ということでまだ試していません。

それと、一般にマクロって黒魔術感があってちょっと……という感じなんですが（偏見）、Rustだとそこそこ使う感じなんでしょうか。しょっぱなからprintln!がマクロですしね。

impl

Pointの実装を終わらせます。

簡単のためnew()と、あるポイントから他のポイントへ到達可能かを判定するis_reachable_from()を実装してみます、判定方法は上述の通り。

impl Point {
    fn new() -> Point {
        Point { t: 0, x: 0, y: 0 }
    }

    fn is_reachable_from(self, other: Point) -> bool {
        let relative_point = self - other;
        let delta_time = relative_point.t as u32; // self.tの方が大きい前提（雑）
        let distance = relative_point.x.abs() as u32 + relative_point.y.abs() as u32;

        delta_time >= distance && delta_time.has_same_parity(distance)
    }
}

特に新しい話は無い

scan() / windows() によるイテレータ走査

あとは全部のポイントについて判定すればよいのですが、各要素を見るときにひとつ前の要素も見るやつ、forでやる以外にないかなーと思って、scan()というのを見つけました。

fn main() {
    let n = read::<usize>();

    let any_unreachable = (0..n)
        .map(|_| read_point())
        .scan(Point::new(), |previous_point, current_point| {
            let reachable = current_point.is_reachable_from(*previous_point);
            *previous_point = current_point;
            Some(reachable)
        })
        .any(|reachable| reachable == false);

    println!("{}", if any_unreachable { "No" } else { "Yes" });
}

なんで気付かなかったか謎ですがこの用途にドンピシャなwindows()というのがあって、それにすれば良かったですね。まさか標準で（略

イテレータあれこれ

Rustのイテレータの機能についてはこの記事がたいへん面白いです。

• Rustのイテレータの網羅的かつ大雑把な紹介

武器庫みたいでワクワクするじゃないか！

あとイテレータついでに別の話をすると、イテレータを返す関数を書こうとして無事死亡というのに私もはまりました。

• イテレータを返す関数を書きたいんですけど？ → やめとけ。 死ぬぞ。

v1.15.1 の時点だとどうなんだろうか、どうしようもない？ そもそも設計がうまければそんなことしなくてもよい場面がほとんどなのかもしれませんが、はて。

終わりに

まさか本当にここまで読んだ人はおるまいが、以上やってみた所感としてはこうです。

• 最初は所有権・借用・ライフタイムでボコボコにされる
• main()内で完結する範囲なら比較的すぐに書けるようになるはず
• プログラムを構造化しようとするとなかなか難しいが、解決できるかは別として、ちゃんと理由があって怒られているんだなという感じにはなる
• traitで柔軟に拡張できるの便利
• 標準機能だけでもいろいろ効率的に面白いことができて良い（イテレータが気に入った）
• 場当たり的に調べていったけどやっぱり座学から始めた方が速いのかもしれない

あと大きな魅力の一つが処理速度のはずで（もともとそれが気になって手を出したんだった）、その検証・説明能力が私にまだ無いのが口惜しいところですが、習熟すればそちらの恩恵も分かってくるであろうことを考えると、やはり総じて魅力的な言語だなと思いました。

以上です！

Rust 完全に理解しました pic.twitter.com/m1tPkr3t7c

— FAL @STG制作とプログラミングお絵かき (@falworks_ja) May 28, 2019