AtCoder Beginner Contest 210

はい． AtCoder Beginner Contest 210 です。

バーチャル参加をしました。ペナ込みで 5完 70:13 でした。

A - Cabbages

問題文

$Y < X$ が保証されているので、 $X$円で買って、安くなる分引けば良いです。

$N$ が $A$ よりも小さい場合があるので、引き算で求めるときに負にならないように気をつけましょう。

fn main() {
    input! {
        n : i64,
        a : i64,
        x : i64,
        y : i64
    }
 
    println!("{}",
        x * n - 0.max(n - a) * (x - y)
    )
}

提出

B - Bouzu Mekuri

問題文

左から見ていって、 1 が来たらどちらかの負けなのでそこから後ろは関係ありません。

交互にカードを食べるので、 1 が来るまでの偶奇が大切です。 take_while で前半から連続する 0 の個数を取って偶奇で判定します。

fn main() {
    input! {
        n : usize,
        s : Chars
    }
 
    println!("{}",
        if s.iter().take_while(|&&c| c == '0').count() % 2 == 0 {"Takahashi"}
        else {"Aoki"}
    )
}

提出

C - Colorful Candies

問題文

$K$ が固定なので、最初に $K$ 個の区間を取って、後は１つずつ区間をずらして求めていけば良いです。右側を１つ伸ばして左側を１つ縮める感じですね。

このとき、見ている区間に現れる種類のそれぞれの個数が分かれば、 $0$ 個の状態から $1$ 個以上になったら種類数が増えるし、 $1$ 個以上の状態から $0$ 個になれば種類数が減ったことが分かります。

今回は、 $ 1 \leq C_i \leq 10^{9} $ と種類数が多いので、 HashMap みたいなものを使うか座標圧縮をして配列で持つなどをしましょう。

fn main() {
    input! {
        n : usize,
        k : usize,
        c : [Usize1; n]
    }

    let mut cnt = 0;
    let mut mp = HashMap::new();

    // 初期化：最初の k 個の区間を求めておく
    for &ci in c.iter().take(k) {
        let t = mp.entry(ci).or_insert(0);
        if *t == 0 { cnt += 1; }
        *t += 1;
    }

    let mut ans= cnt;

    // 区間をずらして見ていく
    for i in k..n {
        {   // 左端を消す
            let t = mp.entry(c[i-k]).or_insert(0);
            *t -= 1;
            if *t == 0 { cnt -= 1; }
        }

        {   // 右端を追加する
            let t = mp.entry(c[i]).or_insert(0);
            if *t == 0 { cnt += 1; }
            *t += 1;
        }
        ans = ans.max(cnt);
    }

    println!("{}", ans);
}

提出

D - National Railway

問題文

難しい…

適当に $2$ 箇所選んで駅を建てたときのコストを最小化してくださいという問題。

１点（$A _ {i,j}$）を決めたときに、そこよりも左上とのペアにするときの（ $A_{i,j}$ を除く）コストが分かれば良いので、DP っぽく移動するたびに $c$ を足しつつ最小コストを求めつつ答えを求めます。

これを、左上・右上・左下・右下の４方向からやれば良いです（対称になるのでうまく２方向からやれば良さそう）。

fn main() {
    input! {
        h : usize,
        w : usize,
        c : usize,
        a : [[usize; w]; h]
    }
 
    let mut ans = std::usize::MAX;
    let mut lu = vec![vec![std::usize::MAX; w]; h];
    for i in 0..h {
        for j in 0..w {
            if i > 0 { lu[i][j] = lu[i][j].min(lu[i-1][j] + c); }
            if j > 0 { lu[i][j] = lu[i][j].min(lu[i][j-1] + c); }
            if i!=0 || j!=0 { ans = ans.min(lu[i][j] + a[i][j]); }
            lu[i][j] = lu[i][j].min(a[i][j]);
        }
    }
 
    let mut ru = vec![vec![std::usize::MAX; w]; h];
    for i in 0..h {
        for j in (0..w).rev() {
            if i > 0 { ru[i][j] = ru[i][j].min(ru[i-1][j] + c); }
            if j+1 < w { ru[i][j] = ru[i][j].min(ru[i][j+1] + c); }
            if i!=0 || j!=w-1 { ans = ans.min(ru[i][j] + a[i][j]); }
            ru[i][j] = ru[i][j].min(a[i][j]);
        }
    }
 
    let mut ld = vec![vec![std::usize::MAX; w]; h];
    for i in (0..h).rev() {
        for j in 0..w {
            if i+1 < h { ld[i][j] = ld[i][j].min(ld[i+1][j] + c); }
            if j > 0 { ld[i][j] = ld[i][j].min(ld[i][j-1] + c); }
            if i!=h-1 || j!=0 { ans = ans.min(ld[i][j] + a[i][j]); }
            ld[i][j] = ld[i][j].min(a[i][j]);
        }
    }
 
    let mut rd = vec![vec![std::usize::MAX; w]; h];
    for i in (0..h).rev() {
        for j in (0..w).rev() {
            if i+1 < h { rd[i][j] = rd[i][j].min(rd[i+1][j] + c); }
            if j+1 < w { rd[i][j] = rd[i][j].min(rd[i][j+1] + c); }
            if i!=h-1 || j!=w-1 { ans = ans.min(rd[i][j] + a[i][j]); }
            rd[i][j] = rd[i][j].min(a[i][j]);
        }
    }
 
    println!("{}", ans);
}

提出

E - Ring MST

問題文

明らかに最小全域木なので、最小全域木に思いを馳せます。しかし、$N$ が大きいので最小全域木を素直に求めることはできません。

そこで、コストが小さい順に処理をしていくことを考えます。

コストが小さい順に見ているので、今見ているやつをできるだけ使いたいです。

ある $(a, c)$ の組を考えたとき、好きに $x$ を決めて $x + a$ との間に辺が張れるので張れるだけ張ります。

例えば、$N = 6, A = 2$ だったら、 0 のノードからたどり着けるだけ張ったら以下のようになりますね。

1 からたどり着けるところにも全部張ってみましょう。

こんな感じで２つのグループに分かれました。 このとき $4 + A$ をしても $\mod 6$ で 0 に戻ってきてしまいます。 $5 + A$ も同様に 1 に戻りますね。

そのため、 $N = 6, A = 2$ のとき最大限辺を張っても２グループにしか分けられません。では、$N = 7, A = 2$ のときはどうでしょう？

結論から言うと、全部つなげることができます。以下のように $6 + A$ をしたときにズレてすべてが繋がります。

では、 $N, A$ が与えられたときに、 これが何個に分かれるか知りたいです。

ある $x$ を $A$ ずつずらしていったものが同じグループに属します。そして、最終的なグループ数は $\gcd(A, N)$ になります。

その最終的なグループ数にするための操作回数ですが、１回につき１つのノードをグループに加えることができるので、$N - \gcd(A, N)$ で求められます。

fn main() {
    input! {
        mut n : usize,
        m : usize,
        mut ac : [(usize, usize); m]
    }
 
    ac.sort_by_key(|&(_,c)| c);
 
    let mut ans = 0;
    for &(a, c) in ac.iter() {
        let gcd = gcd(n, a);
        if gcd >= n { continue }
        ans += c * (n - gcd);
        n = gcd;
    }
 
    println!("{}", match n {
        1 => ans as i64,
        _ => -1,
    });
}

提出

まとめ

バーチャル参加しました。 F は眠くて見ていません。

もう少しやる気が出たら ABC 復活します。