AtCoder Beginner Contest 376 | zeronosu77108's Page

AtCoder Beginner Contest 376 です。 Unrated 参加で、 ABCDEの5完 91:58（6ペナ）でした。

A - Candy Button

ボタンを押すと飴が貰えるけど、前に飴を貰ってから$C$秒未満だと飴が貰えない。 $T_i$秒にボタンを押すから何個飴が貰えますか？という問題。前回貰えた時間を管理しながら$C$秒経っているか確認していく感じ。

fn main() {
    input! {
        n : usize,
        c : i64,
        t : [i64; n]
    }
    
    let mut pref = i64::MIN;
    let mut ans = 0;
    for &t in t.iter() {
        if pref + c <= t { ans += 1; pref = t; }
    }
    
    println!("{}", ans);
}

提出

B - Hands on Ring (Easy)

問題文

リングがあるので、左手と右手を指示通りに動かすみたいな問題。最初指示がない方の手も動かせると思って悩んでいたが、よく読むと指示がある方しか動かせなかった。右回りと左回りを丁寧に管理したら良い。

fn main() {
    input! {
        n : usize,
        q : usize,
        queries : [(char, Usize1); q]
    }
    
    
    let mut l = 0;
    let mut r = 1;
    let mut ans = 0;
    
    let f = |l:usize, r:usize, t:usize| {
        // l -> t
        if l < t {
            if (l<r && r<t) {
                l + 1 + (n - 1 - t)
            } else {
                t - l
            }
        } else {
            if t<r && r<l {
                t + 1 + (n - 1 - l)
            } else {
                l - t
            }
        }
    };
    
    for (h, t) in queries {
        match h {
            'L' => {
                if l == t { continue }
                ans += f(l, r, t);
                l = t;
            }
            'R' => {
                if r == t { continue }
                ans += f(r, l, t);
                r = t;
            }
            _ => unreachable!()
        }
    }
    
    println!("{}", ans);
}

提出

C - Prepare Another Box

問題文

おもちゃ箱を1個足して、おもちゃを全部箱に入れたい。おもちゃと箱には大きさがあり、可能な限り小さな箱を購入したいという問題。二分探索で箱の大きさを決め打ちして、箱に入りきるかチェックする。

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

    a.sort();

    let mut l = 0;
    let mut r = 2_000_000_000;
    while l + 1 < r {
        let m = (l + r) / 2;
        let mut c = b.clone();
        c.push(m); c.sort();

        let ok = a.iter().zip(c.iter()).all(|(a, c)| a<=c);
        if ok { r = m; } else { l = m; }
    }

    if 1_000_000_001 < l { println!("-1"); return;}
    println!("{}", r);
}

提出

D - Cycle

問題文

単純有向グラフが与えられるので、頂点$1$を含む閉路が存在するか、存在するなら辺数が最小の閉路の辺数を求める問題。 BFSで閉路を探す。$1$の距離を一旦リセットしておいて、後で$1$への距離を出力すると良い

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

    let mut g = vec![vec![]; n];
    for (a, b) in edges { g[a].push(b); }
    
    let mut dist = vec![None; n];
    dist[0] = Some(0);
    let mut que = VecDeque::new();
    que.push(0);
    
    let mut pref = vec![None; n];
    let mut first = true;
    while let Some(v) = que.pop_front() {
        for &u in g[v].iter() {
            if dist[u].is_some() { continue }
            pref[u] = Some(v);
            dist[u] = Some(dist[v].unwrap() + 1);
            que.push_back(u);
        }
        if first && v==0 { first=false; dist[0] = None; }
    }
    
    if let Some(ans) = dist[0] { println!("{}", ans); }
    else { println!("-1"); }
}

提出

E - Max × Sum

問題文

数列$A,B$から（同じインデックスの）大きさ$K$の部分集合$S$を選び、$A$の最大値と$B$の合計値の積を最小化する問題。 $A$ を小さい方から追加していって、$B$ は小さい方$K$個を残すような感じで解く。

fn solve() {
    input! {
        n : usize,
        k : usize,
        a : [usize; n],
        b : [usize; n]
    }
    
    let mut mp = BTreeMap::new();
    for i in 0..n {
        mp.entry(a[i]).or_insert(vec![]).push(b[i]);
    }
    
    let mut ans = usize::MAX;
    let mut amax = 0;
    
    let mut pq1 = BinaryHeap::new();
    let mut sum = 0;
    
    for (key, v) in mp {
        amax = amax.max(key);
        for v in v {
            if pq1.len() < k { sum += v; pq1.push(v); }
            else {
                if *pq1.peek().unwrap() > v {
                    sum -= pq1.pop().unwrap();
                    sum += v;
                    pq1.push(v);
                }
            }
        }
        if pq1.len()>=k { ans = ans.min(amax * sum); }
    }
    
    println!("{}", ans);
}

提出

F - Hands on Ring (Hard)

問題文

なんか丁寧にDPしたら解けそうだなと思ったけど、細かいこと考えられず…。

G - Treasure Hunting

問題文

見てない

まとめ

Unrated 参加とはいえ、ちょっとペナが酷すぎた。