AtCoder Beginner Contest 205

はい. AtCoder Beginner Contest 205 です

ずっと書いてなかったので、その間にいろいろありました。 最近は Rust で競プロをしているので、 Rust で書いて行きます(特殊な書き方はしてないので多分読めるはず…)。

当日は参加できなかったので、バーチャル参加をしました。 ABCDE の5完でした。 E は数式をガチャガチャしてたら通ったので、説明はできません… その後で F をやったら割とすんなり通せました。


A - kcal

問題文

100mL で $A$ kcal なので、 1 mL あたりは 100 で割れば求まりますね。 それが $B$ mL あるので それとかけたら答えです。

fn main() {
    input! {
        a : f64,
        b : f64
    }

    println!("{}", b * (a / 100.));
}

提出



B - Permutation Check

問題文

ソートして、 $1, 2, \cdots, N$ と比較しても良いんですが、$1 \leq A _ i \leq N$ なので 並びかえて $1, 2, \cdots, N$ にできないは被りがあるときです。

ソートして、重複削除してその長さを $N$ と比較したら良いです。

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

    a.sort(); a.dedup();    // 重複削除
    
    println!("{}", if a.len() == n {"Yes"} else {"No"});
}

提出



C - POW

問題文

まず、$A, B$ が正のときだけを考えます。 $A ^ C$ と $B ^ C$ の肩に乗っている値は同じなので、 $A$ と $B$ の比較をしたら良いですね。

では、負のときはどうでしょう。 負数を奇数回かけると負、偶数回かけると正になるので、  C の偶奇で場合分けをしたら良さそうです。

$C$ が偶数のときは、 $A, B$ の絶対値を取ってあげると、そのまま比較できます。

fn main() {
    input! {
        mut a : i64,
        mut b : i64,
        c : i64,
    }

    if c % 2 == 0 {
        a = a.abs();
        b = b.abs();
    }

    println!("{}",
        match a.cmp(&b) {
            Ordering::Equal   => "=",
            Ordering::Less    => "<",
            Ordering::Greater => ">"
        });
}

提出

なんか $A ^ { C \% 2 + 2 }$ と $B ^ { C \% 2 + 2 }$ を比較する天才方法もあるみたいです。



D - Kth Excluded

問題文

$A_i$ に含まれない正整数のうち、小さい方から $K$ 番目を直接求めるのは難しそうです。 そこで、「$B$ 以下の値のうち、 $A_i$ に含まれない正整数はいくつありますか?」ということを考えます。

これは、 $1$ から $B$ の $B$ 個の整数のうち、 $B$ 以下の $A_i$ の個数を引けばすぐに求められます($A$ が並んでいるなら lower_bound などで効率的に求められます)。
また、 $B$ を増やせば この個数は単調増加するので二分探索で個数が $K$ 個以下 になるギリギリの $B$ を探せば良さそうです。

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

    for k in k {
        println!("{}", calc(&a, k));
    }
}

fn calc(a : &Vec<i64>, k : i64) -> i64 {
    let mut l = -1;
    let mut r : i64 = 2_000_000_000_000_000_000;

    while l+1 < r {
        let m = (l+r) / 2;
        let index = a.lower_bound(&m) as i64;

        if k < (m - index) { r = m }
        else { l = m }
    }
    l
}

提出



E - White and Black Balls

問題文

数式をガチャガチャして、途中でカタラン数っぽいなとなって、カタラン数の求め方からガチャガチャしてたら通りました。

説明できることはありません…

fn main() {
    input! {
        n : i64,
        m : i64,
        k : i64
    }
    if n > m + k as i64 {
        println!("0");
        return
    }


    const MOD : i64 = 1_000_000_007;
    let comb = Combination::new(2_500_000, MOD);

    let n = n as i64; 
    let m = m as i64;

    let mut ans = comb.nCk(n+m, m) - comb.nCk(n+m, m+k+1) + MOD;
    println!("{}", ans % MOD);
}

提出



F - Grid and Tokens

問題文

あふれ出るフロー感を感じました。 $i$ 番目の人の要望が2つあって、どこのマス目を使うかみたいなものを考えるとマッチングに見えます。

$s$ を始点、 $t$ を終点として考察します。 初期方針として、$r$ を取るパートを考えて、 s --> i --> r --> t のようなグラフを書きたくなったんですが、 s --> i --> r --> c --> t とはできないので、 「$i$ 番目の人」というのを間にいれる方針で考えます。

s --> r --> i --> c --> t みたいなグラフにします。$r$ と $c$ はそれぞれ、 $s, t$ に繋げば良いですね。
そして、r --> ii --> c は要望通りに繋ぎます。 ただし、入る線と出る線が同じノードに入ると、 $i$ 番目の人を諦めたときに他の $r$ からの線(もしくは $c$ の線)も切らないといけなくなってしまうので、 頂点を増やして入と出を分けます。

フローのライブラリは Rust で作ってなかったので、rust-lang-ja/ac-library-rs からお借りしました。

fn main() {
    input! {
        h : usize,
        w : usize,
        n : usize,
        abcd : [(Usize1, Usize1, Usize1, Usize1); n]
    }
    
    let mut mf = MfGraph::new(450);
    let s = 440;
    let t = 441;

    for i in 0..h { mf.add_edge(s, i, 1); }
    for i in 0..w { mf.add_edge(h+i, t, 1); }

    for (id, &(a,b,c,d)) in abcd.iter().enumerate() {
        mf.add_edge(h + w + id, h + w + n + id, 1);
        for i in a..=c { mf.add_edge(i, h + w + id, 1); }
        for i in b..=d { mf.add_edge(h+w+n+id, h+i, 1); }
    }

    println!("{}", mf.flow(s, t));
}

提出



まとめ

久しぶりに記事を書いたので雰囲気が思い出せませんでした。

E,F はあんまり自信がないです。間違ってたらごめんなさい。

早く青になりたいです。