1 年 ago
新, 韵
4 minutes

AtCoder 緑になったのでパズル好きな人に競プロを紹介してみる に続く色変記事です。

想定読者

    • Rust で AtCoder に参加しようとしている

 

    • Rust の経験がある、または Rust 以外の何かのプログラミング言語を使える

 

    • (Windows + Visual Studio Code を使っている)

違う OS や違うエディターの方は読み替えてください

ちなみに Rust が AtCoder 参加に向いている言語かどうかというのは人によって意見が分かれそうです。 AtCoderコンテストにRustで参加するためのガイドブック 最初にメリット・デメリットがまとまっています。

この記事を書いている人は Rust 歴 3か月弱の初心者です。Rust を学んでから競技プログラミングに参加したいというより、競技プログラミングを通じてそこで使う Rust の機能を学ぼうという方が強いです。コンテスト中は Rust っぽくない書き方でもえいやっと通る提出コードを作り、あとから綺麗に書き直すようにしています。

C++ は Rust より経験があります。本エントリでは C++ 標準ライブラリも併記します。

Rust 用の開発環境を設定

以下を参考に、開発環境を入れます:

    • AtCoderコンテストにRustで参加するためのガイドブック

 

    • Windows で Rust 用の開発環境を設定する | Microsoft Docs

 

    Rust in Visual Studio Code

具体的に入れるものです:

    • Rust

 

    • Visual Studio Code

 

    • Visual Studio Code 拡張

rust-analyzer (コード補完、ハイライト)

CodeLLDB (デバッグ実行用)
C/C++ for Visual Studio Code

cargo-generate

rust-analyzer が強力です。 mut 可変値が下線付きになる、index の型が自動分析で表示されるなどで分かりやすいです。とくに Rust 初心者は借用周りの型指定が難しく、コンパイルを通すだけでも苦戦しがちです。助かります。

例えば ABC258-C の画像です。コードの説明は後ほど。

image.png

AtCoder で使う Rust 1.42 では rust-analyzer 最新が動かないかもしれません。そのときは Rust 1.42.0 環境で rust-analyzer を動作させる を参考に設定します。

試しに解いてみる

問題例: ABC258 C – Rotation

2022/07/02 開催の ABC258 から、ABC258 C – Rotation を解きます。

問題文
正整数 $N, Q$ と、長さ $N$ の英小文字からなる文字列 $S$ が与えられます。
以下で説明されるクエリを $Q$ 個処理してください。クエリは次の 2 種類のいずれかです。
1 x: 「$S$ の末尾の文字を削除し、先頭に挿入する」という操作を $x$ 回連続で行う。
2 x: $S$ の $x$ 番目の文字を出力する。
入力
$N\ Q$
$S$
$query_1$
$query_2$
$⋮$
$query_Q$
入力例 1
3 3
abc
2 2
1 1
2 2
出力例 1
10 8
dsuccxulnl
2 4
2 7
1 2
2 7
1 1
1 2
1 3
2 5
入力例 2
3 3
abc
2 2
1 1
2 2
出力例 2
c
u
c
u

テンプレートを持ってくる

AtCoderコンテストにRustで参加するためのガイドブック の通り、 cargo generate でひな形を取ってきます。

PS C:\atcoder-solutions\abc\abc258> cargo generate --git https://github.com/rust-lang-ja/atcoder-rust-base --branch ja
?   Project Name : abc258-c
(中略)
✨   Done! New project created C:\atcoder-solutions\abc\abc258\abc258-c

src\main.rs と tests\sample_inputs.rs が作られました。ABC086-C の main と単体テストです。

// -*- coding:utf-8-unix -*-

use proconio::input;

// ABC086C - Traveling
// https://atcoder.jp/contests/abs/tasks/arc089_a

fn main() {
    input! {
        n: usize,
        mut plan: [(i32, i32, i32); n],  // Vec<(i32, i32, i32)>
    }
    plan.insert(0, (0, 0, 0));
    let yes = plan.windows(2).all(|w| {
        let (t0, x0, y0) = w[0];
        let (t1, x1, y1) = w[1];
        let time = t1 - t0;
        let dist = (x1 - x0).abs() + (y1 - y0).abs();
        dist <= time && time % 2 == dist % 2
    });
    println!("{}", if yes { "Yes" } else { "No" });
}

use cli_test_dir::*;

const BIN: &'static str = "./main";

#[test]
fn sample1() {
    let testdir = TestDir::new(BIN, "");
    let output = testdir
        .cmd()
        .output_with_stdin(r#"2
3 1 2
6 1 1
"#)
        .tee_output()
        .expect_success();
    assert_eq!(output.stdout_str(), "Yes\n");
    assert!(output.stderr_str().is_empty());
}

#[test]
fn sample2() {
    let testdir = TestDir::new(BIN, "");
    let output = testdir
        .cmd()
        .output_with_stdin(r#"1
2 100 100
"#)
        .tee_output()
        .expect_success();
    assert_eq!(output.stdout_str(), "No\n");
    assert!(output.stderr_str().is_empty());
}

#[test]
fn sample3() {
    let testdir = TestDir::new(BIN, "");
    let output = testdir
        .cmd()
        .output_with_stdin(r#"2
5 1 1
100 1 1
"#)
        .tee_output()
        .expect_success();
    assert_eq!(output.stdout_str(), "No\n");
    assert!(output.stderr_str().is_empty());
}

もちろん単体テストが通ります。

PS C:\atcoder-solutions\abc\abc258\abc258-c> cargo test
(中略)
test result: ok. 3 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

これをベースに、コードをそれぞれの問題に差し替えていきます。

単体テストを更新

入力例 1
3 3
abc
2 2
1 1
2 2
出力例 1
10 8
dsuccxulnl
2 4
2 7
1 2
2 7
1 1
1 2
1 3
2 5
入力例 2
3 3
abc
2 2
1 1
2 2
出力例 2
c
u
c
u

に対応するように、各テストケースの output_with_stdin(), assert_eq() 内を書き換えます。

use cli_test_dir::*;

const BIN: &'static str = "./main";

#[test]
fn sample1() {
    let testdir = TestDir::new(BIN, "");
    let output = testdir
        .cmd()
        .output_with_stdin(r#"3 3
abc
2 2
1 1
2 2
"#)
        .tee_output()
        .expect_success();
    assert_eq!(output.stdout_str(), "b\na\n");
    assert!(output.stderr_str().is_empty());
}

#[test]
fn sample2() {
    let testdir = TestDir::new(BIN, "");
    let output = testdir
        .cmd()
        .output_with_stdin(r#"10 8
dsuccxulnl
2 4
2 7
1 2
2 7
1 1
1 2
1 3
2 5
"#)
        .tee_output()
        .expect_success();
    assert_eq!(output.stdout_str(), "c\nu\nc\nu\n");
    assert!(output.stderr_str().is_empty());
}

単体テスト実行は省略します。この時点では標準入力が想定と違って panic するだけですので。

標準入力を読み取る

入力
$N\ Q$
$S$
$query_1$
$query_2$
$⋮$
$query_Q$

に対応するように proconio 部を書き換えます。

// -*- coding:utf-8-unix -*-

use proconio::{input, marker::Chars};

fn main() {
    input! {
        n: usize,
        q: usize,
        s: Chars,
        queries: [(usize, usize); q],
    }
    // ここから実装
}

こちらで、標準入力の値がすべて読み込まれます。

    • n: usize

 

    • q: usize

s: Vec (C++: vector 型)

queries: Vec<(usize, usize)> (C++: vector<tuple<usize, usize>> 型)

proconio クレートなしで標準入力を読み込むのは手間です。読み込めたとしても、文字列を1文字単位で取り出すのも手間です。制限時間のある競技プログラミングですから、ここはお任せします。

2020 Update 標準ライブラリ以外の AtCoder で使えるクレート一覧です。proconio はとくに有用です。

proconio で値を読み取るときに難があるとすると2点:

    • Vec への詰め方がいつもインデックス 0 開始。 AtCoder 問題中の指定は多くが $A_1$ など 1 開始。番号の入れ替えでバグを入れかねない。

気になるなら別の Vec に 1 開始で詰めなおすこともできます。

input! マクロが柔軟な取り出しに対応しているためか、rust-analyzer での型表示がうまくいかず {unknown} と表示されがち。

気になるなら let queries: Vec<(usize, usize)> = queries; のように型指定して詰めなおします。

実装

先頭から値を取り出すということで、末尾側の追加削除だけ強い Vec を使っての処理はナシ。両端に強い VecDeque (C++: deque) なら使えるかもしれません。

この問題の場合、deque を実現する仕組みのリングバッファがそのまま当てはめられると気づくと、index を動かすだけで解けます:

// -*- coding:utf-8-unix -*-

use proconio::{input, marker::Chars};

fn main() {
    input! {
        n: usize,
        q: usize,
        s: Chars,
        queries: [(usize, usize); q],
    }
    let mut index = 0usize;
    for (t, x) in queries {
        if t == 1 {
            index = (index + n - x) % n;
        } else {
            println!("{}", s[(index + x - 1) % n]);
        }
    }
}

単体テスト、提出

PS C:\atcoder-solutions\abc\abc258\abc258-c> cargo test
(中略)
test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

こちらを提出します。お疲れさまでした。

残念ながらテストが通らない場合、 println!(“{:?}”, …); で変数が正しく作られているか書き出す、それでもだめならデバッグ実行する、として修正していきます。

よく使う機能とライブラリ → 次回

    • The Rust Programming Language 日本語版

 

    • Rust by Example 日本語版

 

    • The Rust Standard Library

 

    • AtCoderコンテストにRustで参加するためのガイドブック

 

    RustCoder ―― AtCoder と Rust で始める競技プログラミング入門

このあたりを読めば言語に詳しくなれます。でも量が多く、とくに公式の The Rust Standard Library は欲しい機能を探すだけで時間が過ぎていきます。

そこで、今まで 3か月弱解いてきた中で使ってきたもの、今後使いそうなものをレシピ形式で書いてみようと思います。たとえば i64 だとこのように。

let i = 1i64; // 1i64 でも 1_i64 でもいい
assert_eq!(i, 1);

// 四則演算
let j: i32 = 2;
// assert_eq!(i + j, 3); // 異なる型同士は演算できない
assert_eq!(i + j as i64, 3); // キャストすれば OK

// min, max (C++: min, max)
assert_eq!(i.max(2), 2);
assert_eq!(i.min(2), 1);

// abs (C++: abs)
assert_eq!(i.abs(), 1);

// シフト演算
assert_eq!(1i64 << 4, 0b10000);
assert_eq!(0xffi64 >> 4, 0xf);

// ビット演算 (C++: popcount)
assert_eq!(0b10100000i64.count_ones(), 2);

// 最大値: Rust 1.42 では使えない
// assert_eq!(i64::MAX, 9_223_372_036_854_775_807);

次回に続きます。

✖
广告
将在 10 秒后关闭
bannerAds