Rust

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

Rust入門をかねて解いていく

You can share this article with

はじめに

最近、Rustを使い始めました。

せっかくなので競プロ典型90問をRustで解いていこうと思います。

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

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

#4 Cross Sum

問題はこちら

前処理をするために、0で初期化したベクタを生成します。
最初にパッと思いついたのは以下の2通りです。

これは、です。``rustPythonだと-(-a//b)`とも書けます。

let mut vec: Vec = (0..n).map(|_|0).collect(); let mut vec: Vec = std::iter::repeat(0).take(n).collect();

しかし、以下の方法があることを知りました。`vec!`マクロ、覚えていきましょう。

```rust
let mut vec = vec![0usize; n];
fn main(){
    proconio::input!{
        h:usize,
        w:usize,
        a:[[usize;w];h]
    }
    let mut r=vec![0usize;h];
    let mut c=vec![0usize;w];
    for i in 0..h{
        for j in 0..w{
            r[i]+=a[i][j];
            c[j]+=a[i][j];
        }
    }
    for i in 0..h{
        let mut l:Vec<String>=vec![];
        for j in 0..w{
            l.push((r[i]+c[j]-a[i][j]).to_string());
        }
        println!("{}",l.join(" "));
    }

}

#10 Score Sum Queries

問題はこちら

累積和ですね。またvec!マクロを使います。

タプルを使って、let (l,r)=lr[i];のように2つ一気に束縛をしています。

fn main(){
    proconio::input!{
        n:usize,
        cp:[(usize,usize);n],
        q:usize,
        lr:[(usize,usize);q]
    }
    let mut one=vec![0usize;n+1];
    let mut two=vec![0usize;n+1];
    for i in 0..n{
        if cp[i].0==1{
            one[i+1]=cp[i].1+one[i];
            two[i+1]=two[i];
        }else{
            one[i+1]=one[i];
            two[i+1]=cp[i].1+two[i];
        }
    }
    for i in 0..q{
        let (l,r)=lr[i];
        println!("{} {}",one[r]-one[l-1],two[r]-two[l-1]);
    }
}

#22 Cubic Cake

問題はこちら

Rustはgcd()がないので自分で実装します。関数の定義は戻り値などの型をちゃんと指定する必要があったり、(今回は必要ないですが、)読み取り値をグローバル変数に入れて参照させたりが(たぶん)できないので面倒ではあります。

fn main(){
    proconio::input!{
        a:isize, b:isize, c:isize
    }
    let d = gcd(gcd(a,b),c);
    println!("{}",a/d+b/d+c/d-3);
}

fn gcd(x:isize,y:isize)->isize{
    if y==0 {x} else {gcd(y,x%y)}
}

#24 Select + / - One

問題はこちら

各項で最低限必要な操作回数はAiBi|A_i-B_i|です。KK回ちょうどという条件があるため、回数が余ったらいったん足して元に戻すという偶数回の操作をすることで以降は現状維持できます。

Python等の他の言語とは違い、abs()メソッドが後置です。また、対象は負の数があるintfloatのみ。uintには当たり前ですが対応していません(そもそも負の数がありません)。

fn main(){
    proconio::input!{
        n:usize, k:isize,
        a:[isize;n],
        b:[isize;n]
    }
    let mut d=0;
    for i in 0..n{
        d+=(a[i]-b[i]).abs();
    }
    println!("{}",if d<=k && (k-d)%2==0{"Yes"}else{"No"});
}

#27 Sign Up Requests

問題はこちら

PythonでいうところのsetであるHashSetを使います。
ちなみにRustでは、アクセスにlog(N)log(N)かかることを代償に昇順で格納されるBTreeSetというデータ構造も標準ライブラリに搭載されています。名前の通り中身はB木です。

fn main(){
    proconio::input!{
        n:usize,
        s:[String;n]
    }
    let mut d = std::collections::HashSet::new();
    for i in 0..n{
        if !d.contains(&s[i]){ println!("{}",i+1) }
        d.insert(&s[i]);
    }
}

#33 Not Too Bright

問題はこちら

まんまと引っかかりました。問題文はよく読みましょう。

さて、除算に関するテクは以前に記事にしましたが、今回は切り上げ除算ですね。

これは、(a+b-1)/bです。Pythonだと-(-a//b)とも書けます。

fn main() {
  proconio::input!{ (h,w):(i32,i32) }
  let mut ans;
  if h==1 { ans=w }
  else if w==1 { ans=h }
  else { ans=((h+1)/2)*((w+1)/2) }
  println!("{}",ans);
}

おわりに

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

時間があれば★3の記事も書きたいと思っています書きました

★4も書きはじめました