【Rust】ABC445感想（A~C）

AtCoder Beginner Contest 445

事後にバーチャル参加して、ABC3完でした。
今回はA~Cの感想を書きます。

A - Strong Word

文字列$S$の先頭と末尾を比較して、同じであればYes、異なればNoを出力します。

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

    if s[0] == s[s.len() - 1] {
        pr("Yes");
    }else {
        pr("No");
    }
}

B - Center Alignment

$S$の中での文字列長の最大値$\text{max}$を計算しておき、各文字列について左右に$(\text{max} - |S_i|) / 2$個の.を連結します。

fn main() {
    input! {
        n: usize,
        s: [Chars; n],
    }

    let mut s = s;
    let mut t = vec![];
    let max = s.iter().map(|x| x.iter().count()).max().unwrap();
    for i in 0..n {
        let k = (max - &s[i].len()) / 2;
        let dots = ['.'].repeat(k);
        let mut res = vec![];
        res.append(&mut dots.clone());
        res.append(&mut s[i]);
        res.append(&mut dots.clone());
        t.push(res.iter().join(""));
    }

    pr(t.iter().join("\n"));
}

C - Sugoroku Destination

$10^{100}$回ではなく、$10 \times 100$回しか移動しない嘘のダブリングを書いてしまってかなり時間を浪費してしまいました。

任意の10進数文字列を引数とする繰り返し二乗法のライブラリがあれば良かったのですが、持っていないのでダブリングの解法はあきらめて、グラフの解法で攻めることにしました。

$i \le A_i \le N$という条件が重要で、この条件によってサイクルが生じることはありません。
したがって、各ノードについて$A$に沿って移動できるだけ移動した終着点がそのまま答えとなります。
ここで、計算量を節約するため、訪問済みのノードに訪問した場合はそのノードの終着点を参照することにしましょう。
以上により、全体計算量$O(N)$でこの問題を解くことができました。

fn main() {
    input! {
        n: usize,
        a: [usize; n],
    }

    let a = a;
    let mut ans = vec![usize::MAX; n];
    for i in 0..n {
        if a[i] == i + 1 {
            ans[i] = i + 1;
        }
    }
    let mut st = vec![];
    for i in 0..n {
        let mut last = i;
        while ans[last] == usize::MAX {
            st.push(last);
            last = a[last] - 1;
        }
        while let Some(x) = st.pop() {
            ans[x] = ans[last];
        }
    }

    pr(ans.iter().join(" "));
}

まとめ

ライブラリを生成するにもAIが使えないというのはしんどいですね。
Xでも同じような意見を見かけましたが、競プロがそろばんみたいな競技になってきたなと思うところがあります。