bouzuya.hatenablog.com

ぼうずやのにっき

bouzuya/rust-atcoder で cargo workspace を適用してみた / M-SOLUTIONS プロコンオープン A, B, C を解いた

bouzuya/rust-atcoder で cargo workspace を適用してみた。

cargo-atcoder で dependencies をコンテストごとに取得していて無駄そうだったので target/ を共有してみようと思った。これは cargo-compete がそうしているから。

cargo-compete では .cargo/config.toml で build.target-dir を指定することで target/ の共有を実現している。ぼくは cargo workspace でできるんじゃないかと思って試してみた。

結論としては cargo workspace だとまずかった。まずかったのは 2 点。

  • bin の name が一意でないと警告が出る
  • rust-analyzer が cargo workspace の members すべてを見に行く

結果的にコンテストごとに dependencies を取得する時間の無駄よりもっとまずそうな動きになった。 VS Code の動きがカクついたりする。

結局 cargo workspace をやめて .cargo/config.toml に target-dir を指定することにした。これは cargo-compete と同じ方法だ。

あとから教えてもらったことだけどこの方法は cargo-atcoder の README に書いてある。

https://github.com/tanakh/cargo-atcoder/blob/8382265062093652bc6bd50963dbe76db45c2ab1/README.md?plain=1#L25-L37

嘘でしょ……。

cargo-atcoder は使い慣れているのだけど problem 単位での操作が難しいので自分で何かつくってみようかと思っている。つくることで今回のような学びがありそうな気がしている。

M-SOLUTIONS プロコンオープン

use modint::ModInt1000000007 as ModInt;
use proconio::input;

fn main() {
    input! {
        n: usize,
        a: usize,
        b: usize,
        c: usize,
    };

    let (fact, finv) = {
        let maxn = 2 * n;
        let mut fact = vec![ModInt::new(1); maxn + 1];
        for i in 1..=maxn {
            fact[i] = fact[i - 1] * ModInt::new(i);
        }
        let mut finv = vec![ModInt::new(1); maxn + 1];
        finv[maxn] = fact[maxn].inv();
        for i in (1..=maxn).rev() {
            finv[i - 1] = finv[i] * ModInt::new(i);
        }
        (fact, finv)
    };
    let binom = |n: usize, k: usize| -> ModInt {
        if n < k {
            ModInt::new(0)
        } else {
            fact[n] * finv[k] * finv[n - k]
        }
    };

    let a = ModInt::new(a);
    let b = ModInt::new(b);
    let c = ModInt::new(c);
    let mut ans = ModInt::new(0);
    for m in n..=2 * n - 1 {
        ans += binom(m - 1, n - 1)
            * (((a.pow(n as u64) * b.pow((m - n) as u64)
                + a.pow((m - n) as u64) * b.pow(n as u64))
                * ModInt::new(m)
                * ModInt::new(100))
                / ((a + b).pow(m as u64) * (ModInt::new(100) - c)));
    }
    println!("{}", ans);
}

// modint

今日のコミット。