【AtCoder 緑色を目指して】RustでABC377をC問題まで解いてみた【競技プログラミング】

技術ブログ 競技プログラミング

はじめに

こんにちは、最近コンテストへの参加をさぼっていた駒嶺です。

今回はRustの勉強のために普段Pythonで挑戦していたAtCoder Beginner Contest 377をRustで解いてみました。

A – Rearranging ABC

与えられた文字列を並び替えてABCにできるかどうか判定します。

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

fn main() {
    input! {
        mut s: Chars
    }
    s.sort();
    println!("{}", if s.iter().collect::<String>() == "ABC" {"Yes"} else {"No"})
}

4行目のInput!はproconioというクレートのマクロです。
proconioは名前の通り競技プログラミングの入出力を助けてくれるクレートです。
7行目でソートをするために変数sの型はStringではなくChars（chrのVec）を指定しています。

Rustらしいところとして、変数名の前にmutというキーワードが付いています。
mutはmutableの略で可変を意味します。なんとRustでは変数はデフォルトでは不変になっています！
しかもmutをつけて宣言したのに一度も再代入を行っていない変数があるとコンパイラが指摘してくれます。信頼できますね。

B – Avoid Rook Attack

ルークがいくつか置かれたチェス盤が渡されます。ルークの効きがない空きマスは何マスあるでしょうか。

解答

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

fn main() {
    input! {
        board: [Chars; 8]
    }
    let mut is_empty_col = [true; 8];
    let mut is_empty_row = [true; 8];

    for (i, col) in board.iter().enumerate(){
        for (j, space) in col.iter().enumerate(){
            is_empty_col[i] &= *space == '.';
            is_empty_row[j] &= *space == '.';
        }
    }

    let mut ans = 0;
    for i in 0..8{
        for j in 0..8{
            if is_empty_col[i] && is_empty_row[j]{
                ans += 1;
            }
        }
    }

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

効きがないマスとは同じ行、同じ列にルークが存在しないマスのことです。
盤面が8×8と小さいので二重ループで各列、各行にルークが存在するかどうかを記録します。
その後もう一度8×8の二重ループで効きがない空きマスをカウントすればOKです。

C – Avoid Knight Attack

今度はナイトの効きがない空きマスを数えます。
先ほどは盤面が8×8固定でしたが今度は最大で10^9×10^9です。

解答

use proconio::input;
use std::collections::HashSet;

fn main() {
    input! {
        n: i64,
        m: usize,
        knights: [(i64, i64); m]
    }

    let attack_range: [(i64, i64); 9] = [
        (0, 0),
        (2, 1),
        (1, 2),
        (-1, 2),
        (-2, 1),
        (-2, -1),
        (-1, -2),
        (1, !1),
        (2, -1)
    ];
    let mut attacked: HashSet<(i64, i64)> = HashSet::new();
    for (kx, ky) in knights{
        for (dx, dy) in attack_range{
            let x = kx + dx;
            let y = ky + dy;
            if x >= 1 && x <= n && y >= 1 && y <= n {
                attacked.insert((x, y));
            }
        }
    }
    println!("{}", n.pow(2) - attacked.len() as i64);
}

11行目の配列はナイトの効きを表しています。ナイトの位置にこれを足せば8方向の攻撃可能マス（とナイト自信が埋めているマス）を判定できます。
効きがあるマスはHashSetで持たせればOKですね。HashSetはPythonのSetと同じで重複のない集合を扱うコレクションです。

おわりに

今回はRustの勉強をしながらゆっくりやりたかったのでコンテストには参加しませんでした。
次回はRustでコンテストに参加して記事を書こうと思います。次回がいつになるかは未定です。

本ブログを通じて私と一緒に競技プログラミングの世界を楽しんでいただければ幸いです。
また、各種ご支援させていただきますので、お気軽に「お問い合わせフォーム」よりお問い合わせください。

お問い合わせ
業務実績

関連記事