ABC015_C 高橋くんのバグ探しで学ぶstatic mutの危険性[Rust]

要約

• DFS（深さ優先探索）の勉強としてAtCoder Beginner Contest 015 C問題をピックアップ。
• グローバル変数を使った解答例を模倣してstatic mutで実装AC。
• static mutは超危険、Rustの思想に反することを知る。
• 謝罪の念をいだきつつ、代替案で実装AC。←イマココ

問題概要

atcoder.jp

解法

AtCoder Beginner Contest 015 解説

• 答えを導くために判定するパターンが最大でも5^5(=3125)通りしかないので、全探索が可能。
• ただし、質問の個数が入力によって変わってくるためforループの場合分けは大変。
• DFSならば質問、選択肢の数に合わせて探索が可能なのでDFSを利用。
• 全ての回答の排他的論理和が０（全7bit(0～127)の各bitの真が偶数）になる場合があるかを探索していく。
• 見つかった場合は’Found’、そうでなければ'Nothing'を出す。

危険な実装（ダメ絶対）

Rustでグローバル変数を使う方法を調べていたら、こちらの記事を見つけ味を覚えて実装ACしました。その後、こちらの記事を発見し、とても丁寧にstatic mutは危険とのご指摘をされておりました。そして構造体を利用するイディオマティックな代替案を提示してくれていたので、早速これを使って実装AC。
static mut 使っている時も、unsafe祭りで良くはないとは思っていたのですが解決策がわからず蓋をしていました。そこに上記のような貴重な指摘を発見できて良かったです。また競プロ以外では参照を持ち回すことを検討しましょうとのことで、こちらも少しずつ修得できればと思います。

構造体を使った安全なコード*1

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

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();

    token.parse().ok().expect("failed to parse token")
}

struct Q {
    n: usize,
    k: usize,
    t: [[u8; 5]; 5],
}

impl Q {
    fn dfs(&mut self, num_q: usize, value: u8) -> bool {
        //最深到達
        if num_q == self.n {
            return value == 0;
        }
        for i in 0..self.k {
            //println!("value{}, t[{}][{}]{}", value, num_q, i, self.t[num_q][i]);
            let value_xor: u8 = value ^ self.t[num_q][i];
            if self.dfs(num_q + 1, value_xor) {
                return true;
            }
        }
        false
    }
    fn main(&mut self) {
        for i in 0..self.n {
            for j in 0..self.k {
                self.t[i][j] = read();
            }
        }
        if self.dfs(0, 0) {
            println!("Found");
        } else {
            println!("Nothing");
        }
    }
}

fn main() {
    let mut q = Q {
        n: read(),
        k: read(),
        t: [[0; 5]; 5],
    };
    q.main();
}

static mut を使った危険なコード

use std::io::*;
use std::str::FromStr;
 
static mut N: usize = 0;
static mut K: usize = 0;
static mut T: &'static mut [[u8; 5]; 5] = &mut [[0; 5]; 5];
 
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
 
    token.parse().ok().expect("failed to parse token")
}
 
fn main() {
    unsafe {
        N = read();
        K = read();
        for i in 0..N {
            for j in 0..K {
                T[i][j] = read();
            }
        }
        if dfs(0, 0) {
            println!("Found");
        } else {
            println!("Nothing");
        }
    }
}
 
//線形探索と深さ優先探索の計算量は同じ
unsafe fn dfs(num_q: usize, value: u8) -> bool {
 
    //最深到達
    if num_q == N {
        return value == 0
    }
    for i in 0..K {
        //println!("value{}, T[{}][{}]{}",value, num_q, i, T[num_q][i]);
        if dfs(num_q + 1, value ^ T[num_q][i]) { return true }
    }   
    false
}

参考

qiita.com
qiita.com

*1:Rust(1.15.1)ではdfsの引数に直接XORの計算を入れるとCEしたので別途変数定義。