zeronosu77108’s blog

AtCoder Beginner Contest 236

競プロ AtCoder ABC

はい． AtCoder Beginner Contest 236 です。

Unrated 参加しました。

4完 41:56 でした（1ペナ込み）

A - chukodai

問題文の通り、 $a$ 文字目と $b$ 文字目を入れ替えて出力します。

fn main() {
    input! {
        mut s : Chars,
        a : Usize1,
        b : Usize1
    }

    s.swap(a, b);
    println!("{}", s.into_iter().join(""));
}

B - Who is missing?

$1$ から$N$ までのカードが 4 枚ずつあって、そのうちの1枚が抜かれているのでそれを求める問題。

抜かれていなかったら、 $1$ から $N$ までの総和の $4$倍がカード全部の合計になっているので、残っているカードの和を引いたら抜かれているカードが分かります。

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

    let sum = a.into_iter().sum::<usize>();
    println!("{}", n*(n+1)/2*4 - sum);
}

C - Route Map

$S_i$ が $T_j$ の中にありますか？という問題。

$T$ の集合を Set などに乗せると存在判定が早くできるため、そうしたら愚直に判定できる。

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

    let t : FxHashSet<_> = t.into_iter().collect();

    println!("{}", s.into_iter().map(|s| if t.contains(&s) {"Yes"} else {"No"}).join("\n"));
}

D - Dance

「愚直に探索できるだろ！」をしたら TLE しました。（このミス何回するんだろう…） DFSするときに片方の INDEX は最小のものに固定しないと計算量が大変なことになります。

最初に見つけた !used なやつを使ったら break したら良いです。

fn main() {
    input! { n : usize }
    let mut a = vec![vec![0; 2*n]; 2*n];

    for i in 0..2*n {
        input! { aa : [usize; 2*n-1-i] }
        for j in 0..2*n-1-i {
            a[i][i+j+1] = aa[j];
            a[i+j+1][i] = aa[j];
        }
    }


    let mut used = vec![false; 2*n];
    let ans = dfs(0, n, &mut used, &a);
    println!("{}", ans);
}

fn dfs(s:usize, n:usize, used:&mut Vec<bool>, a:&Vec<Vec<usize>>) -> usize {
    if used.iter().all(|&f| f) { return s; }

    let mut res = 0;
    for i in 0..2*n {
        if used[i] { continue }
        used[i] = true;
        for j in i+1..2*n {
            if used[j] { continue }
            used[j] = true;
            res = res.max(dfs(s ^ a[i][j], n, used, a));
            used[j] = false;
        }
        used[i] = false;
        break
    }
    res
}

E - Average and Median

なんで解けなかったんだろう…？二分探索するのは分かったんだけど判定で迷ってました。

二分探索で平均の目標を決めて、 $A_i$ から引いておけばどれくらい目標値と離れているか分かるので、後は取る/取らないで条件を考慮しながら和の最大値を求めるDPをしたら良いです。

中央値も同じ感じで、目標値以上かどうかを判定して同じ感じで数を数えたら良いです。

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

    let ave = {
        let mut l = 0.0;
        let mut r = 1_000_000_001.0;

        for _ in 0..100 {
            let m = (l+r) / 2.0;
            let b = a.iter().map(|&i| i as f64 - m).collect_vec();

            let mut dp : Vec<Vec<f64>> = vec![vec![0.0; n+1]; 2];

            for i in 1..=n {
                dp[0][i] = dp[1][i-1]; // 取らない
                dp[1][i] = dp[0][i-1].max(dp[1][i-1]) + b[i-1]; // 取る
            }


            if dp[0][n].max(dp[1][n]) < 0. { r = m }
            else { l = m }
        }
        l
    };

    let med = {
        let mut l = 0;
        let mut r = 1_000_000_001;
        while l+1 < r {
            let mut m = (l+r) / 2;
            let b = a.iter().map(|&i| if i>=m {1} else {-1}).collect_vec();

            let mut dp = vec![vec![0; n+1]; 2];
            for i in 1..=n {
                dp[0][i] = dp[1][i-1]; // 取らない
                dp[1][i] = dp[0][i-1].max(dp[1][i-1]) + b[i-1]; // 取る
            }

            if dp[0][n].max(dp[1][n]) <= 0 { r = m }
            else { l = m }
        }
        l
    };

    println!("{}\n{}", ave, med);
}

F - Spices

XOR の基底だろうな～って思いながら考えていたんですが、 E で時間を使ってしまってあんまり時間がなかったです…

これは得意側な問題なので見た瞬間解けても良かった気がします…

安い方から使いたいので、$c_i$ の昇順に処理します。ある $c_i$ を採用するかどうか考えたときに、今まで採用したスパイスから作れるものであれば採用する必要がありません。

小さい順に、基底かどうかチェックしつつ採用するかどうかを決めたら良いです（参考）。

fn main() {
    input! {
        n : usize,
        c : [usize; (1<<n)-1]
    }

    let c = c.into_iter().enumerate().map(|(i,c)| (c,i+1)).sorted().collect_vec();
    let mut ans = 0;
    let mut base = vec![];

    for (c, mut i) in c {
        for &b in base.iter() { i = i.min(b ^ i); }
        if i == 0 { continue }
        base.push(i); ans += c;
    }

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

G - Good Vertices

見てません

Ex - Distinct Multiples

見てません

まとめ

E,F は解けたな～って感じですね…