【Rust】ABC443感想（A~E）

AtCoder Beginner Contest 443

unrated参加しまして、ABCD4完でした。
今回はA~Eの感想を書きます。

A - Append s

$S$に"s"を足して終了ですね。
一瞬&"s"のように書かないといけないかなと思ったのですが、"s"はStringではなく&str変数なのでそのまま"s"書けばOKです。

fn main() {
    input! {
        s: String,
    }

    pr(s + "s");
}

B - Setsubun

$N,K \le 10^8$なので、$1$年ごとに愚直に食べた豆の累計数を数えていってもTLEしません。
したがって、累計数を数え$K$を超えた年を記載して終了となります。

fn main() {
    input! {
        n: usize,
        k: usize,
    }

    let mut sum = 0;
    let mut ans = 0;
    for i in 0..10usize.pow(7u32) {
        sum += n + i;
        if sum >= k {
            ans = i;
            break;
        }
    }
    pr(ans);
}

C - Chokutter Addiction

chokutterを眺めた時間$\text{ans}$と現在の時間$\text{cur}$を変数で管理します。
具体的には、$A_i$を左から順番に見ていき、以下のように更新します。

• $A_i \ge \text{cur}$ならば、$\text{ans} \leftarrow \text{ans} + \min({A_i-\text{cur},T-\text{cur}) }$、$\text{cur} \leftarrow \min(T, A_i +100)$
• $A_i < \text{cur}$ならば、chokutterを閉じているのでなにもしない

上のように、$\text{cur}$を次にchokutterを開ける時間に更新しておけば、計算がしやすいです。

fn main() {
    input! {
        n: usize,
        t: usize,
        a: [usize; n],
    }
    let mut a = a;
    a.push(t);

    let mut ans = 0;
    let mut cur = 0;
    for i in 0..n + 1 {
        if a[i] < cur {
            continue;
        }
        ans += (t - cur).min(a[i] - cur);
        cur = (a[i] + 100).min(t);
    }
    pr(ans);
}

D - Pawn Line

解説とは解法が全然違っていて笑いましたが、一応簡単に説明します。
考え方としては、最初に全てのポーンを最上段にセットしておいて、適切な順番で一つずつ「どこまで下に下げられるか？」を考え、最終的なポーンの位置を確定させていきます。
なるべく下に下げたいのは、そのほうが上に移動させるコストを下げることができるからです。
また、ポーンの下限は初期位置となります。
さらに、隣の列の駒と$1$行以内の差でなければいけないのですが、すでに位置が確定したポーンの中で最も近い列のポーンの高さから、自分のポーンまでの間にある列数分だけ下に下げることができます。

最も近いポーンはBTreeSetのようなデータ構造を使えば$O(NlogN)$で求めることができます。
以上で、全体として$O(NlogN)$でこの問題を解くことができました。

fn main() {
    input! {
        t: usize,
    }

    let mut ans: Vec<usize> = vec![];
    for _ in 0..t {
        input! {
            n: usize,
            r: [usize; n],
        }

        let mut bset: BTreeSet<usize> = BTreeSet::new();
        let indexed_r = r.iter().enumerate().sorted_by(|a, b| a.1.cmp(&b.1)).collect::<Vec<(usize, &usize)>>();
        let mut fixed = vec![1; n];
        for (i, x) in indexed_r {
            let mut cur = 3 * 10usize.pow(5u32);
            let r = bset.range(i..).next();
            if let Some(k) = r {
                cur = cur.min(fixed[*k] + k - i);
            }
            let l = bset.range(..i).last();
            if let Some(k) = l {
                cur = cur.min(fixed[*k] + i - k);
            }
            fixed[i] = cur.min(*x);
            bset.insert(i);
        }

        let mut res = 0;
        for i in 0..n {
            res += r[i] - fixed[i];
        } 
        ans.push(res);
    }
    pr(ans.iter().join("\n"));
}

E - Climbing Silver

解説を見るとこれはDP（動的計画法）という説明がされていましたが、
上に壁マスがあっても壊せる列と、移動可能な列を各行について管理して、下からどんどん更新していけば簡単に解くことができました。
D問題で多大な時間をかけていなければコンテスト時間内に解けたと思います。

fn main() {
    input! {
        t: usize,
    }

    let mut ans = vec![];
    for _ in 0..t {
        input! {
            n: usize,
            c: usize,
            s: [Chars; n],
        }
        let mut s = s;
        let mut hset = HashSet::new();
        let mut can_break = vec![1; n];
        let mut res = vec![0; n];
        hset.insert(c - 1);

        for i in (0..n).rev() {
            for j in 0..n {
                if s[i][j] == '#' {
                    can_break[j] = 0;
                }
            }
            if i > 0 {
                let mut nex_hset = HashSet::new();
                for &x in &hset {
                    if x > 0 {
                        if can_break[x - 1] == 1 {
                            s[i - 1][x - 1] = '.';
                        }
                        if s[i - 1][x - 1] == '.' {
                            nex_hset.insert(x - 1);
                        }
                    }
                    if can_break[x] == 1 {
                        s[i - 1][x] = '.';
                    }
                    if s[i - 1][x] == '.' {
                        nex_hset.insert(x);
                    }
                    if x < n - 1 {
                        if can_break[x + 1] == 1 {
                            s[i - 1][x + 1] = '.';
                        }
                        if s[i - 1][x + 1] == '.' {
                            nex_hset.insert(x + 1);
                        }
                    }
                }
                hset = nex_hset;
            }else {
                for &x in &hset {
                    res[x] = 1;
                }
            }
        }

        ans.push(res.iter().join(""));
    }
    pr(ans.iter().join("\n"));
}

まとめ

少しずつRustを書く時のエラーが減ってきました。
ただし、まだまだレートが同じくらいのRustaceanに比べても実装速度が遅いので、もっと書き慣れていかないとなと思いました。