Rust

競プロ典型90問の★3をRustで解く

知見を忘れないうちにストックする

You can share this article with

はじめに

最近、Rustをはじめたので競プロ典型90問を解くという試みです。

今回の記事は★3です。★2は前回、別の記事に書きました。
参考までに、普段はPythonを使っていて、この記事の作成時点ではコーダーです。

よりよいコードがあればGitHubにPRを送っていただければ助かります。

#2 Encyclopedia of Parentheses

問題はこちら

bit全探索ですね。Rustでは単純に数字をインクリメントするfor文は0..nを使います。

Pythonとやり方が似ていますが、0..=nというように末尾を含む場合も=で記載できるのが便利です。 これ、Pythonにも導入してほしいですね。

あとはRustの鬼門、文字列操作ですがmutableな文字列にはStringが使えます。

fn main() {
    proconio::input!{
        n:isize
    }
    for i in 0..1<<n {
        let mut r=0;
        let mut l=0;
        let mut f=true;
        let mut s="".to_string();
        for j in 0..n {
            if i>>(n-j-1)&1 == 1{
                r+=1;
                s+=")";
            }else{
                l+=1;
                s+="(";
            }
            if r>l {f=false}
        }
        if r==l && f {
            println!("{}",s);
        }
    }
}

#14 We Used to Sing a Song Together

問題はこちら

貪欲で解けます。こういうのは絵に描くといいですね。書かないと頭がバグる場合があります。

Rustにおいてmutableな配列は.sort()でソートできることを覚えておけばよいです。

下記はあえてメソッドチェーンで処理していますが、今回は単純なforで回すほうがシンプルに書けると思います。
あくまで勉強がてら、という感じです。

fn main() {
    proconio::input! {
        n:usize,
        mut a:[i64;n],
        mut b:[i64;n],
    }
    a.sort();
    b.sort();
    let ans: i64 = (0..n)
        .map(|i| (a[i] - b[i]).abs())
        .collect::<Vec<_>>()
        .iter()
        .sum();
    println!("{}", ans);
}
// 普通のforで書く場合
let mut ans = 0isize;
for i in 0..n{ ans+=(a[i]-b[i]).abs(); }
println!("{}",ans);

#16 Minumum Coins

問題はこちら

硬貨の枚数が最大で9999枚のため、O(N2)O(N^2)が許されます。Rustは速いのでこういうシーンは安心ですね。

また、min()関数は、std::cmpの中にあります。

さらに、答えの初期化にNNの最大値である10910^9を使いますが、ここで1<<3010737418241073741824であるため代替できます。これはRustに限った話ではないですが、地味に簡単に書けていい感じになりますので好きです。

fn main(){
    proconio::input!{
        n:usize,
        a:usize, b:usize, c:usize
    }
    let mut ans = 1<<30;
    for i in 0..10000{
        for j in 0..10000{
            let d = n-a*i-b*j;
            if d%c==0{
                ans=std::cmp::min(ans,i+j+d/c);
            }
        }
    }
    println!("{}",ans);
}

#18 Statue of Chokudai

問題はこちら

こういう問題文、クスッとなるので好きです。さて、アルゴリズムではなく数学の問題ですね。

実装面で誤差に気をつけるくらいで、問題としては高校生でも解析的に解くことのできる内容です。
ABCでもたまにこういう数学知識だけの問題が出ることがありますね。

Rustでの三角関数は、abs()とかと同じで後置であることに注意する必要があるでしょう。
また、π\pistd::f64::constsの中にいます。

今回は、入力をクエリごとに受け取るのではなく、ベクタへ一気に格納してしまっています。

for文でfor i in &eとしていますが、このコードでは別に所有権がムーブしてもあとから参照しないのでfor i in eでも問題ありません。

参照戻しなども混乱しやすいですが、Rustではプリミティブ型にはCopyトレイトが実装されていることを把握しておくのがよいでしょう。

use std::f64::consts::PI;
fn main() {
    proconio::input! {
        t:f64,
        l:f64, x:f64, y:f64,
        q:i64,
        e:[f64;q]
    }
    let l = l / 2.0;
    for i in &e {
        let rad = 2.0 * PI * i / t;
        let dy = -l * rad.sin();
        let dz = l * (1.0 - rad.cos());
        let dx = (x * x + (y - dy) * (y - dy)).sqrt();
        let deg = dz.atan2(dx) * 180.0 / PI;
        println!("{}", deg);
    }
}

#20 Log Inequality

問題はこちら

これも数学ですね。

べき乗のシンタックスを知らない場合O(N)O(N)ですが、知っている場合はほぼO(1)O(1)のようなものです(内部実装は調べてませんが、厳密にはおそらくO(logN)O(logN)とかのはず)。

pow()の引数は必ずu32型であることだけ覚えておけば問題ないでしょう。

fn main(){
    proconio::input!{
        a:i128, b:u32, c:i128,
    }
    println!("{}",if a<c.pow(b) {"Yes"} else {"No"});
}

#32 AtCoder Ekiden

問題はこちら

C++でいうところのnext_permutationを使う問題ですね。

Rustだとitertools::Itertoolsが使えます。よく使う全列挙の類は以下で利用できます。

  • nPr{}_n\mathrm{P}_r(0..n).permutations(r)
  • nCr{}_n\mathrm{C}_r(0..n).combinations(r)
  • nHr{}_n\mathrm{H}_r(0..n).combinations_with_replacement(r)
use itertools::Itertools;
use proconio::{marker::*, *};
fn main() {
    input! {
        n: usize,
        a: [[i32; n]; n],
        m: usize,
        l: [(Usize1, Usize1); m]
    }
    let mut ng = vec![vec![false; n]; n];
    for i in 0..m {
        let (x, y) = l[i];
        ng[x][y] = true;
        ng[y][x] = true;
    }
    let mut ans = 1 << 30;
    for i in (0..n).permutations(n) {
        let mut t = 0;
        let mut ok = true;
        for (j, &k) in i.iter().enumerate() {
            if j < n - 1 {
                let (x, y) = (i[j], i[j + 1]);
                if ng[x][y] {
                    ok = false
                }
            }
            t += a[k][j];
        }
        if ok {
            ans = ans.min(t)
        };
    }
    println!("{}", if ans == 1 << 30 { -1 } else { ans });
}

おわりに

問題が追加されたら、あわせて追記していこうと思います。

まだ解けていませんが、★4の記事もいずれ書きたいと思っています。