Rustで蟻本

Rustで蟻本「プログラミングコンテストチャレンジブック」を解いていきます。
解くというよりはCのコードをRustで書く写経です。

三角形

n本の棒があるときに作れる三角形の最大周長

fn main() {
    let a = [1, 2, 3, 4];
    println!("{}", triangle(a.len(), &a)); // => 9
}

fn triangle(n: usize, a: &[i32]) -> i32 {
    let mut ans = 0;
    for i in 0..n {
        for j in (i+1)..n {
            for k in (j+1)..n {
                let l = a[i] + a[j] + a[k];
                let ma = [a[i], a[j], a[k]].into_iter().max().unwrap();
                let rest = l - ma;
                if ma < rest {
                    ans = l
                }
            }
        }
    }
    ans
}

メモ

• 配列的なものを渡すときは、&Vec<i32>とするよりは&[i32]の方がアクセスが早くていいかもしれない。ただし配列の長さ情報は失われるので、別個に渡す必要がある。
  (訂正：スライス&[i32]は先頭要素へのポインタと、長さ情報の組なので、a.len()のようにしたら、長さがわかる。)
  参考ページ　Rustを覚えて間もない頃にやってしまいがちなこと
• 3つの文字の最大をとるときはイテレータのmaxメソッドを使うのが短くていいような気がしている。

Ants

長さLの棒にn匹の蟻がいて、全員落ちるまでの最短時間と最長時間

fn ant(l: i32, x: &[i32]) -> (i32, i32) {
    let mut min_t = 0;
    let mut max_t = 0;
    for &a in x {
        min_t = cmp::max(min_t, cmp::min(a, l - a));
        max_t = cmp::max(max_t, cmp::max(a, l - a));
    }
    (min_t, max_t)
}

メモ

• スライスは長さの情報をもつ。だからこそfor文で要素をそのまま回すことができる。
• for文で取り出す要素に参照記号&をつけると、参照型ではなく値として取り出せる。この場合だと後でaを使う時に*aなどとしなくて良いので便利。(copyを実装している型だけの現象か?)
• 計算時間はO(n)
• イメージ的にはmin_tは一番真ん中に近い蟻が落ちるまでの時間、max_tは一番端に近い蟻が反対側の端から落ちるまでの時間、なのでアルゴリズム的にも真ん中に近い2匹の蟻と、両端の2匹の蟻を調べてそれぞれその2者を比較で良いかと思ったが、その場合、結局最初にxの並び替えや最大最小を求める必要が出てきて、それにO(nlogn)ないしO(n)の時間がかかるので、とくに計算時間上のメリットはなく、コードも冗長になる。

くじ引き

n個の数字たちkから重複ありで4つ選び、和をmにできるかどうか。
nの3重ループの中に計算時間がlog(n)のbinary_searchがあるアルゴリズム
(計算時間O(n³logn))

fn lottery(m: i32, mut k: Vec<i32>) -> bool {
    k.sort();
    for a in &k {
        for b in &k {
            for c in &k {
                if binary_search(m - a - b - c, &k) {
                    return true;
                }
            }
        }
    }
    false
}

fn binary_search(x: i32, k: &[i32]) -> bool {
    // looking for x in k[l], k[l+1], ..., k[r - 1]
    let mut l = 0;
    let mut r = k.len();
    while l < r {
        let i = (l + r) / 2;
        if x < k[i] {
            r = i;
        } else if x == k[i] {
            return true;
        } else {
            l = i + 1;
        }
    }
    false
}

2分探索は以下のように再帰で書く方が探索範囲を絞っていくイメージに合っていて好きだが、関数呼び出しのオーバヘッドで遅いのかもしれない。

fn binary_search(x: i32, k: &[i32]) -> bool {
    if k.len() == 0 {
        return false;
    }
    let i = k.len() / 2;
    if x < k[i] {
        binary_search(x, &k[..i])
    } else if x == k[i] {
        true
    } else {
        binary_search(x, &k[i + 1..])
    }
}

あらかじめ2数の和で実現できる数のリストを作ってループを減らす方法もあり、メモリ的には不利だが、計算時間をO(n²logn))に減らせる。

fn lottery(m: i32, k: &[i32]) -> bool {
    // 2数の和で実現できる数のリスト
    // 普通にfor文回して作っても良い
    let mut kk = k
        .iter()
        .flat_map(|x| k.iter().map(move |y| x + y))
        .collect::<Vec<i32>>();
    kk.sort();
    // ループの回数はn^2となる。
    for a in &kk {
        if binary_search(m - a, &kk) {
            return true;
        }
    }
    false
}

メモ

• kkを作るときのclosureでmoveキーワードが必要になるが、つけないとコンパイラに怒られるので付けたものの、理由はよく分かってない。closureがxより長生きするかもしれないとのことだったが、そんなことなさそうだが...。

部分和

ある整数k: i32と、n個の整数のリストa: &[i32]が与えられたとき、そのリストから任意個の整数を選んで和をkにできるか否か。

深さ優先探索

fn partial_sum(k: i32, a: &[i32]) -> bool {
    if a.is_empty() {
        // 最後まで探索した場合
        k == 0
    } else {
        // まだ数が残っているとき
        // その数を使わない or その数を使う(使ったときは目標値のkから引く)
        partial_sum(k, &a[1..]) || partial_sum(k - a[0], &a[1..])
    }
}

• 計算時間はO(2ⁿ)（nはaの長さ）である。
• 2ⁿ通りの計算をするので、なんとなくそうだとは思うが、よくわからない点もある。各状態の計算は関数呼び出しとk - a[0]という計算を最大n回伴うので、計算時間O(n)ではないか？それが2ⁿ通りあるのだから全体の計算時間はO(2ⁿn)ではないのか？O(2ⁿ)のアルゴリズムを考えるときは実質的にnはせいぜい100程度だろうから、定数と考えるということだろうか。

Lake Counting

n×mのフィールドから池の数を数える。池は上下左右斜めでつながっているとする。

fn main() {
    // lake counting
    let s = "
    W........WW.
    .WWW.....WWW
    ....WW...W..
    ..........W.
    .........W..
    WWW.........
    .W..W..WWW..
    ..W.WWW....W
    ";
    println!("lake count: {}", Lake::new(8, 12, s).count()); // => 5
}

struct Lake {
    n: usize,
    m: usize,
    field: Vec<u8>,
}

impl Lake {
    fn new(n: usize, m: usize, s: &str) -> Self {
        Self {
            n: n,
            m: m,
            field: s
                .chars()
                .flat_map(|c| match c {
                    'W' | '.' => Some(c as u8),
                    _ => None,
                })
                .collect(),
        }
    }
    fn dfs(&mut self, x: usize, y: usize) {
        self.field[x * self.m + y] = b'.';
        for nx in x.saturating_sub(1)..=std::cmp::min(x + 1, self.n - 1) {
            for ny in y.saturating_sub(1)..=std::cmp::min(y + 1, self.m - 1) {
                if self.field[nx * self.m + ny] == b'W' {
                    self.dfs(nx, ny);
                }
            }
        }
    }
    fn count(&mut self) -> i32 {
        let mut res = 0;
        for x in 0..self.n {
            for y in 0..self.m {
                if self.field[x * self.m + y] == b'W' {
                    self.dfs(x, y);
                    res += 1;
                }
            }
        }
        res
    }
}

メモ

• 1つのdfsは最大9回のループをまわす。dfsは'W'のところだけで呼ばれ、ひとつのマスでたかだか1回しかよばれない。したがって計算時間はO(n×m)
• 普通の関数だと外の変数にアクセスできず、一方クロージャならアクセスできるが再帰呼び出しができない。この回り道として構造体のメソッドとしてdfsを定義する。
  参考
  • Rustのクロージャで再帰してみた (ダメだった)
  • static mutの危険性
• rustの数値は他の数値型と直接演算ができず、安全だが書くのが面倒な時もある。usizeから1を引く方法としてはsaturating_subというのが、オーバーフローしたら0にしてくれるので便利とおもった。
• 二重配列はどう表現するのが一番良いかわからないが、メモリ上は1次元配列にしといて、アクセスするときに[self.m * x + y]とする方法にした。

迷路の最短経路

N, M ≦ 100の条件下で、大きさN×Mの迷路のスタートからゴールまでの最短経路の長さを求めよ。

幅優先探索

キューを用意する（rustではVecでok）。スタートからまず4つの方向（上下左右）で行ける場所（壁でなく、既に行ったところでもない）に移動し、その座標をキューに積む。それからキューの先頭を取り出し、そこからさらに4方向を探索してキューに積む。このとき、直前にいた場所は既に行っているので、探索しない。行ける場所がなくなったからキューをポップしていき、行ける場所が残されているのが見つかったら再び探索を開始する。

fn main() {
    let maze: Vec<u8> = "
    #S#.#.....
    ......#.#.
    #######.#.
    G##..#..#.
    ..#.##.##.
    #...#..#..
    ##.####..#
    ##..##..##
    ###....###
    ##########
    "
    .bytes()
    .filter(|b| [b'S', b'G', b'.', b'#'].contains(b))
    .collect();
    println!("{}", bfs(10, 10, &maze, Pair(0, 1), Pair(3, 0)));
}

#[derive(Clone, Copy, PartialEq, Eq)]
struct Pair(usize, usize);

const INF: i32 = 100000000;

fn bfs(n: usize, m: usize, maze: &[u8], s: Pair, g: Pair) -> i32 {
    let mut que = Vec::<Pair>::new();
    let mut d = vec![INF; n * m];
    que.push(s);
    d[s.0 * m + s.1] = 0;
    while let Some(p) = que.pop() {
        if p == g {
            break;
        }
        for (dx, dy) in [(1, 0), (0, 1), (-1, 0), (0, -1)] {
            let nx = p.0 as i32 + dx;
            let ny = p.1 as i32 + dy;
            if 0 <= nx && nx < n as i32 && 0 <= ny && ny < m as i32 {
                let nx = nx as usize;
                let ny = ny as usize;
                let ni = nx * m + ny;
                if maze[ni] != b'#' && d[ni] == INF {
                    que.push(Pair(nx, ny));
                    d[ni] = d[p.0 * m + p.1] + 1;
                }
            }
        }
    }
    d[g.0 * m + g.1]
}

メモ

• INFはN×Mより大きければなんでも良いと思われる。
• 本には書いてないようであるが、このアルゴリズムは後戻りしないという意味では最短の経路がもとまるが、ゴールまでの経路が複数ある場合はそのうちのどれか1つを進んでいくので、複数ある経路のうちの最短のものを見つけられるわけではないようだ。

経路が複数ある場合

1つの経路に入り込んでいかないで、近いところから並列に探索していけば良い。次の記事が非常に参考になった。「幅優先探索はわかるけどダイクストラ法は怪しい」あなたに

use std::collections::VecDeque;

#[derive(Clone, Copy, PartialEq, Eq)]
struct Pair(usize, usize);

const INF: i32 = 100000000;

fn bfs(n: usize, m: usize, maze: &[u8], s: Pair, g: Pair) -> i32 {
    let mut que = VecDeque::from([s]);
    let mut d = vec![INF; n * m];
    d[s.0 * m + s.1] = 0;
    'outer: while let Some(p) = que.pop_front() {
        for (dx, dy) in [(1, 0), (0, 1), (-1, 0), (0, -1)] {
            let nx = p.0 as i32 + dx;
            let ny = p.1 as i32 + dy;
            if 0 <= nx && nx < n as i32 && 0 <= ny && ny < m as i32 {
                let np = Pair(nx as usize, ny as usize);
                let ni = np.0 * m + np.1;
                if maze[ni] != b'#' && d[ni] == INF {
                    que.push_back(np);
                    d[ni] = d[p.0 * m + p.1] + 1;
                    if np == g {
                        break 'outer;
                    }
                }
            }
        }
    d[g.0 * m + g.1]
}

メモ

• 両端に高速に追加、取り出しができるVecDequeをを使い、新しく探索する遠い地点を後ろにpush(push_back)していくと、近いところから調べていける。

順列全列挙

0,...,n-1の並び替えを全て出力する

fn main() {
    let n = 10;
    Perm::permutation(n);
}

const MAX_N: usize = 100;

struct Perm {
    n: usize,
    used: [bool; MAX_N],
    perm: [usize; MAX_N],
}

impl Perm {
    fn permutation(n: usize) {
        Perm {
            n,
            used: [false; MAX_N],
            perm: [0; MAX_N],
        }
        .subfn(0);
    }
    fn subfn(&mut self, pos: usize) {
        if pos == self.n {
            // self.perm[..self.n]に順列が入っている
            println!("{:?}", &self.perm[..self.n]);
            return;
        }
        for i in 0..self.n {
            if !self.used[i] {
                self.perm[pos] = i;
                self.used[i] = true;
                self.subfn(pos + 1);
                self.used[i] = false;
            }
        }
    }
}

メモ

• used[i]==trueが1つずつ減っていくので、状態数はn×(n-1)×...×1となる。
• 本のコードの後半は意味がよく理解できません。

硬貨の問題

1円〜500円玉がそれぞれc: [i32; 6]枚あるとき、a円を払うのに必要な最小限の硬貨の枚数。

const V: [i32; 6] = [1, 5, 10, 50, 100, 500];
fn coin(mut a: i32, c: [i32; 6]) -> i32 {
    let mut ans = 0;
    for (&c_num, &val) in c.iter().zip(&V).rev() {
        let t = std::cmp::min(a / val, c_num);
        a -= t * val;
        ans += t;
    }
    ans
}


// 本質的違いはないが、変数ansを用意しなくていい方法
fn coin2(mut a: i32, c: [i32; 6]) -> i32 {
    c.iter().zip(&V).rev().map(|(&c_num, &val)| {
        let t = std::cmp::min(a / val, c_num);
        a -= t * val;
        t
    }).sum()
}

メモ

• 計算時間は定数
• 500円玉から順番に使えるだけ使っていく。
• このやり方でうまくいくのは高い硬貨の額面が安い硬貨の額面で常に割り切れるからである。例えば400円玉もある世界で、800円を払いたかったとすると、先に500円玉を使ってしまうと、たとえば300円 = 100円×3枚で払わないといけなくなったりする（400円玉2枚で済んだかもしれないのに）。（要証明）

区間スケジューリング問題

仕事の開始時間と終了時間のリストが与えられたとき、もっとも多くこなせる仕事の個数。

貪欲法

fn work(s: Vec<i32>, t: Vec<i32>) -> i32 {
    let mut itv: Vec<_> = t.into_iter().zip(s).collect();
    itv.sort();
    let mut ans = 0;
    let mut last_work_end = 0;
    for (end, start) in itv {
        if last_work_end < start {
            ans += 1;
            last_work_end = end;
        }
    }
    ans
}

辞書順最小の問題

単語が与えられたとき、先頭、あるいは末尾から文字を順番に取って並べたときに得られる辞書順最小の単語を求めよ。

fn best_cow_line(s: &str) -> String {
    let mut vd = VecDeque::from_iter(s.chars());
    (0..)
        .map_while(|_| {
            if vd.iter().lt(vd.iter().rev()) {
                vd.pop_front()
            } else {
                vd.pop_back()
            }
        })
        .collect()
}

メモ

• cow lineってどういう意味なんだろう。(文字通り牛の列のことだったhttp://poj.org/problem?id=3617)
• その場で最善な選択をひたすら選ぶ貪欲法の一種
• RangeFromやmap_whileという便利なものを知った。
  （記事を書いてみました Rustの無限イテレータ)
• イテレータ同士は辞書順の比較ができることを知った。iter().lt(...)

Saruman's Army

N個の点xがあり、ある点に印をつけると、その左右rの範囲をカバーできる。N個の点全てをカバーする場合、最低何個の点に印をつける必要があるか。

fn saruman(r: i32, x: &mut [i32]) -> usize {
    x.sort();
    let mut i = 0; // 現時点でカバーできていない左端
    let mut ans = 0;
    while i < x.len() {
        i += x[i + 1..].iter().take_while(|&&s| s <= x[i] + r).count();
        ans += 1; // x[i]に印をつける
        i += x[i + 1..].iter().take_while(|&&s| s <= x[i] + r).count() + 1; // x[i] + rより外にでるところ
    }
    ans
}

メモ

• x.len() == nのとき、x[n..]はパニックせず、たとえばx[n..].len() == 0となる。(x[n + 1..]はパニックする。)

Fence Repair

1枚の板から配列xで与えられる長さのn枚の板を切り出したい。板を切るコストはその板の長さである。最小の合計コストを求めよ。

fn fence(mut x: Vec<i32>) -> i32 {
    let mut ans = 0;
    while x.len() > 1 {
        let n = x.len();
        // 最小と2番目のインデックスを探す
        let mut i1 = 0;
        let mut i2 = 1;
        if x[i1] > x[i2] {
            std::mem::swap(&mut i1, &mut i2);
        }
        for i in 2..n {
            if x[i] < x[i1] {
                i2 = i1;
                i1 = i;
            } else if x[i] < x[i2] {
                i2 = i;
            }
        }
        // i1 < i2としておく
        if i2 < i1 {
            std::mem::swap(&mut i1, &mut i2);
        }
        x[i1] += x[i2]; // x[i1]は残るので、そこにx[i2]を足す。
        x.swap(i2, n - 1); // x[i2]を捨てるために後ろに回す。
        x.pop(); // 末尾を捨てる
        ans += x[i1]; // x[i1], x[i2]を分けたときのコスト
    }
    ans
}

メモ

• 計算時間はO(n²)（外側のwhileも内側のforもn回程度回る）
• 2つの変数の中身を入れ替えるときは、std::mem::swapを使う。ベクタや配列の要素を入れ替えるときは可変スライスのメソッドswapを使う。

長くなってきたので、この記事は一旦終了して動的計画法の章からは別の記事に移ります。