Go to Qiita Advent Calendar 2024 Top
LoginSignup
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@jikei

RustでABC288復習

Last updated at Posted at 2023-02-19

はじめに

Rustの勉強のためにAtCoderのコンテストでRustを使うことにしました。
解説を読んだりして自分がわかった範囲で復習します。

復習

A - Many A+B Problems

2つの数字を足して出力する問題。
そのままループを回してそれぞれ足したものを出力する。

use proconio::input;


fn main() {
    input! {
        n: usize,
    }
    for _ in 0..n {
        input! {
            a: i64,
            b: i64,
        }
        println!("{}", a+b);
    }
}

B - Qualification Contest

上位$K$人のハンドルネームを辞書順に出力する問題。
まずは上位$K$人のハンドルネームを別のリストに分ける。
その後にそのリストをソートして出力する。

use proconio::input;


fn main() {
    input! {
        n: usize,
        k: usize,
        s: [String; n],
    }
    let mut ans = vec![];
    for i in 0..k {
        ans.push(s[i].clone());
    }
    ans.sort();
    for i in 0..k {
        println!("{}", ans[i]);
    }
}

C - Don’t be cycle

単純無向グラフからできるだけ少なく辺を消して閉路を持たないグラフにする問題。
閉路を持たないグラフというのはつまり木であるので、最小全域木と同じ要領で行う。
具体的には、辺がない状態から開始し、辺を一つずつ足していく。このとき、グラフに閉路を作ってしまう辺は削除する。こうして削除した辺の数が答えになる。
足した辺がグラフに閉路を作るかどうかはUnionFindを用いると簡単に判定できる。
実は最終的にできた木の数を$L$と置くと、最終的に残った辺の数は$N-L$になる(木の頂点の数を$K$とすると辺の数は$K-1$になり頂点の数より一つ少なくなるため)ので、$M-N+L$でも答えが出たかもしれない。(未検証)

use proconio::input;
use proconio::marker::Usize1;


struct UnionFind {
    roots: Vec<i64>,
}

impl UnionFind {
    fn new(n: usize) -> Self {
        UnionFind {
            roots: vec![-1; n],
        }
    }

    fn root(&mut self, x: usize) -> usize {
        if self.roots[x] < 0 {
            return x;
        } else {
            self.roots[x] = self.root(self.roots[x] as usize) as i64;
            return self.roots[x] as usize;
        }
    }

    fn is_same(&mut self, x: usize, y: usize) -> bool {
        self.root(x) == self.root(y)
    }

    fn size(&mut self, x: usize) -> usize {
        let root_x = self.root(x);
        (-self.roots[root_x]) as usize
    }

    fn unite(&mut self, x: usize, y: usize) -> bool {
        if self.is_same(x, y) {
            false
        } else {
            let mut root_x = self.root(x);
            let mut root_y = self.root(y);
            if self.size(root_x) < self.size(root_y) {
                std::mem::swap(&mut root_x, &mut root_y);
            }
            self.roots[root_x] -= (self.size(root_y)) as i64;
            self.roots[root_y] = root_x as i64;
            true
        }
    }
}

fn main() {
    input! {
        n: usize,
        m: usize,
        edges: [(Usize1, Usize1); m],
    }
    let mut ans = m;
    let mut uf = UnionFind::new(n);
    for &(u, v) in &edges {
        if uf.unite(u, v) {
            ans -= 1;
        }
    }
    println!("{}", ans);
}

D - Range Add Query

数列$A$の連続部分列に対して、さらにその任意の幅$K$の連続部分列に同じ値を足していくことでその連続部分列の要素を全て0にできるか判定する問題。
元の数列と元の数列に対して直前の数との差をとった数列を見てみる。すると$i=2, c=4$として操作を行うと、差をとった数列は図のようにインデックス$2$の場所に$+4$、$5$の場所に$-4$されることがわかる。つまりインデックスの$\mathrm{mod} K$が同じ場所の和は常に一定になる。
d1.png
また、良い配列である条件を見ると図のように差をとった数列の方で

  • 最初と最後より一つ後ろのインデックスに相当する値が$0$との差になるように更新される
  • そのほかの値は$0$になる(元の数列で全て$0$になるため)
    d2.png
    となっていることがわかる。
    つまり、操作を行うことで上記のような最初と最後の次のインデックスの差分以外が$0$にできるかを判定することがこの問題と答えと言える。
    ここで、インデックスが$\mathrm{mod} K$で同じものの和が変わらないことを利用し、問題の範囲($l_i$から$r_i$)でインデックスの$\mathrm{mod} K$が$j$となるものの和をすぐに取り出せるようにしておくと、各$j$での和が期待しているものになっているかを判定するだけで解くことができる。
    今回は和をすぐに取り出す方法としてSegmentTreeを使用して、$O(KQ \log N)$で解くことができた。解説は累積和を使っているように見えたし、計算量の観点でもあちらが$O(\log N)$倍早い。
use proconio::input;
use proconio::marker::Usize1;


#[derive(Clone)]
struct SegmentTree {
    n: usize,
    data: Vec<i64>,
}

impl SegmentTree {
    fn new(n: usize) -> Self {
        let mut i = 1;
        while i < n {
            i *= 2;
        }
        SegmentTree {
            n: i,
            data: vec![0; 2*i-1],
        }
    }

    fn add(&mut self, index: usize, value: i64) {
        let mut index = self.n + index - 1;
        self.data[index] += value;
        while 0 < index {
            index = (index - 1) / 2;
            self.data[index] = self.data[2*index+1] + self.data[2*index+2];
        }
    }

    fn _query(&mut self, index: usize, l: usize, r: usize, left: usize, right: usize) -> i64 {
        if r <= left || right <= l {
            return 0;
        } else if l <= left && right <= r {
            return self.data[index];
        } else {
            let mid = (left + right) / 2;
            return self._query(2*index+1, l, r, left, mid)
                + self._query(2*index+2, l, r, mid, right);
        }

    }

    fn query(&mut self, l: usize, r: usize) -> i64 {
        return self._query(0, l, r, 0, self.n);
    }
}


fn main() {
    input! {
        n: usize,
        k: usize,
        a: [i64; n],
        q: usize,
        queries: [(Usize1, Usize1); q],
    }
    let mut st = vec![SegmentTree::new(n); k];
    for i in 0..n-1 {
        st[i%k].add(i, a[i+1]-a[i]);
    }
    for &(l, r) in &queries {
        let mut is_valid = true;
        for i in 0..k {
            let mut v = st[i].query(l, r);
            if (k + l - 1) % k == i {
                v += a[l];
            }
            if r % k == i {
                v -= a[r];
            }
            if 0 < v {
                is_valid = false;
            }
        }
        println!("{}", if is_valid {
            "Yes"
        } else {
            "No"
        });
    }
}

E - Wish List

$N$個の商品の中から指定されたものを含むいくつかの商品をできるだけ安く買う問題。
商品は買うタイミングで値段が変わるため厄介だが、$N$と$M$が小さいので動的計画法で解くことを考える。
具体的には安い順に$i$番目までの商品の中から$j$個買う時に一番安く買う方法を求める。ただし、買わないといけない商品は必ず買うようにする。
遷移としては$\mathrm{dp}[i][j]$を「安い順に$i$番目に安い商品までの中から$j$個買う場合に支払う最小金額」と置く。
また、$\mathrm{cost}[i][j]$を$i \le k \le j$で最小の$C_k$と置く。つまり商品を買う時に$i$番目から$j$番目に安い時があるとして、一番安い手数料($C_k$)が何かを事前に計算しておく。
遷移は以下のようになる。
まず、$0$番目のものまでを$0$個買う場合は$0$円で初期化する。

\mathrm{dp}[0][0] = 0

次に、商品を買う場合と買わない場合で$\mathrm{dp}[i][j]$から2パターンに遷移する。
買う場合は$\mathrm{dp}[i+1][j+1]$に、下の式のように$\mathrm{dp}[i][j]$に商品$i$の値段、$i-j$から$i$番目のどこかで買う時に一番安い手数料を足したものに遷移する。このとき、商品$i$が欲しい商品であるならば必ず遷移し、欲しい商品でない場合はすでに$\mathrm{dp}[i+1][j+1]$が一度も計算されていないか、既に計算されているが今回の金額よりも高い場合に遷移する。
買わない場合は商品$i$が欲しい商品でない場合にのみ$\mathrm{dp}[i+1][j]$に遷移する。買う場合と同様に今回も以前より安い金額になる場合にのみ遷移する。

\mathrm{dp}[i+1][j+1] = \mathrm{dp}[i][j]+A[i]+\mathrm{cost}[i-j][i] \\
\mathrm{dp}[i+1][j] = \mathrm{dp}[i][j]

以上を繰り返して$\mathrm{dp}[X_m]$の最小値が答えになる。

use proconio::input;
use proconio::marker::Usize1;
use std::collections::HashSet;
use std::cmp::min;


fn main() {
    input! {
        n: usize,
        m: usize,
        a: [u64; n],
        c: [u64; n],
        x: [Usize1; m],
    }
    let mut costs = vec![vec![1_000_000_000u64; n]; n];
    let maxx = x[m-1];
    let x: HashSet<usize> = x.into_iter().collect();
    for i in 0..n {
        let mut cost = c[i];
        for j in i..n {
            cost = min(cost, c[j]);
            costs[i][j] = cost;
        }
    }
    let mut dp = vec![vec![None; n+1]; n+1];
    dp[0][0] = Some(0u64);
    for i in 0..n {
        for j in 0..=i {
            if dp[i][j] == None {
                continue;
            }
            let v = dp[i][j].unwrap();
            if x.contains(&i) {
                dp[i+1][j+1] = Some(v + a[i] + costs[i-j][i]);
            } else {
                dp[i+1][j+1] = Some(match dp[i+1][j+1] {
                    Some(pv) => min(pv, v+a[i]+costs[i-j][i]),
                    None => v+a[i]+costs[i-j][i],
                });
                dp[i+1][j] = Some(match dp[i+1][j] {
                    Some(pv) => min(pv, v),
                    None => v,
                });
            }
        }
    }
    println!("{}", dp[maxx+1].iter().map(|&x| x).filter(|&x| x != None).map(|x| x.unwrap()).min().unwrap());
}

F - Integer Division

$N$桁の正の整数$X$の任意の場所で区切り、区切られた数同士の積を全ての区切りパターンで求めて和を求める問題。
$X$の$i$文字目までを$Y_1, Y_2, ... , Y_j$で分割した場合、$\displaystyle \prod_{k=1}^{j-1} Y_k$を$z_i$、$Y_j$を$y_i$とおくと、$i$文字目を入れた値は

z_i y_i x_i \\
z_i(10y_i+x_i) = 10z_i y_i + z_i x_i

に遷移します。
このとき、$y_i$と$z_i$は$X$の分け方によって同じ$i$でも異なる値をとるため,
$z_i y_i$を管理できないため動的計画法に持ち込めない。
そのため、$a_i = y_i z_i$、$b_i = z_i$とおき、上記に代入すると

z_i y_i x_i = a_i x_i \\
10z_i y_i + z_i x_i = 10a_i + b_i x_i

となり、$a_i$と$b_i$を別で使えるため動的計画法に持ち込める。
遷移を考えると、$a_i$は$i$文字目までを見たときの答えとなっているため上記の二つの式の和に遷移する。

a_{i+1} = a_i x_i + 10a_i + b_i x_i

また、$b_i$は$x_i$が独立して$y_i$倍される場合と、$x_i$が$y_i$にひっついて変わらない場合があるため

\begin{align}
b_{i+1} &= y_i b_i + b_i \\
&= y_i z_i + b_i \\
&= a_i + b_i
\end{align}

となる。初期化処理としては$a_0$は空数列の部分集合の和は$0$なので$0$にし、$b_0$は掛け算の初期値として$1$を設定する。
このまま遷移を繰り返し、$a_N$が答えになる。

use proconio::input;
use proconio::marker::Chars;


const MOD: u64 = 998244353;

fn main() {
    input! {
        n: usize,
        x: Chars,
    }
    let x = x.iter().map(|&xi| (xi as u8 - '0' as u8) as u64).collect::<Vec<_>>();
    let mut a = vec![0u64; n+1];
    let mut b = vec![0u64; n+1];
    b[0] = 1u64;
    for i in 0..n {
        a[i+1] = (x[i] * a[i] + 10 * a[i] + b[i] * x[i]) % MOD;
        b[i+1] = (a[i] + b[i]) % MOD;
    }
    println!("{}", a[n]);
}
1
0
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?