AtCoder Beginner Contest 265 - zeronosu77108’s blog

初めてカンストパフォ出しました。嬉し～

A - Apple

3個$Y$円で買った方が安い場合、7個中、3個セット1つ・バラ4個とかを買う意味がないので、全部バラで買うか、3個で買えるだけ買って余りをバラで買うかのどちらかをやれば良いです。

fn main() {
    input! {
        x : usize,
        y : usize,
        n : usize
    }
 
    println!("{}", (n * x).min(n/3*y + n%3*x));
}

提出

B - Explore

問題文

なんか問題文めんどくさい。次の部屋に移動するのに $A_i$ かかって持ち時間 $T$ で最後の部屋にたどり着けますか？という問題。たまにボーナスがある。 $N \leq 10 ^ 5$ なので $i$ 番目の部屋に到達すると $X_i$ 時間増えますみたいなのを全部配列に入れておく。ボーナスがなければ $0$ にしておけば良い。

$0$ 以下か未満かを雑に読んでて 1 ペナ。

fn main() {
    input! {
        n : usize,
        m : usize,
        t : usize,
        a : [usize; n - 1],
        xy : [(Usize1, usize); m]
    }
 
    let mut xv = vec![0; n];
    for (x, y) in xy { xv[x] = y; }
 
    let mut now = t;
    for (i, &a) in a.iter().enumerate() {
        now += xv[i];
        if now <= a { println!("No"); return; }
        now -= a;
    }
 
    println!("Yes");
}

提出

C - Belt Conveyor

問題文

愚直にシミュレーションする。はみ出たり、既に訪れている所に来たら終わる。

fn main() {
    input! {
        h : usize,
        w : usize,
        g : [Chars; h]
    }
 
    let mut now = (0, 0);
    let mut visited = vec![vec![false; w]; h];
    loop {
        if visited[now.0][now.1] { println!("-1"); return; }
        visited[now.0][now.1] = true;
        match g[now.0][now.1] {
            'R' => {
                if now.1 + 1 >= w { break }
                now.1 += 1;
            }
            'L' => {
                if now.1 == 0 { break }
                now.1 -= 1;
            }
            'U' => {
                if now.0 == 0 { break }
                now.0 -= 1;
            }
            'D' => {
                if now.0 + 1 >= h { break }
                now.0 += 1;
            }
            _ => unreachable!()
        }
    }
 
    println!("{} {}", now.0 + 1, now.1 + 1);
}

提出

D - Iroha and Haiku (New ABC Edition)

問題文

最初全部 $P$ になるやつだと思って、適当に紙に書いたらサンプル全然合わなくて「？？？」ってなってた。累積和を取っておいて、その地点から +P, +P+Q, +P+Q+R を二分探索すると良い。

ok 関数のダメ判定を index > n で書いてたんだけど提出直前に index >= n にして 1 WA。累積和なので index > n で良かった…。

fn main() {
    input! {
        n : usize,
        p : usize,
        q : usize,
        r : usize,
        a : [usize; n]
    }
 
    let mut csum = vec![0; n + 1];
    for i in 0..n { csum[i + 1] = csum[i] + a[i]; }
 
    let ok = |x:usize, k:usize, a:&Vec<usize>| {
        let index = a.lower_bound(&(x + k));
        if index > n { (false, 0) }
        else { (a[index] == x + k, index) }
    };
 
    for i in 0..n {
        let (f1, index1) = ok(csum[i], p, &csum);
        if !f1 { continue }
        
        let (f2, index2) = ok(csum[index1], q, &csum);
        if !f2 { continue }
        
        let (f3, index3) = ok(csum[index2], r, &csum);
        if !f3 { continue }
        
        println!("Yes");
        return;
    }
 
    println!("No");
}

提出

E - Warp

問題文

$A,B,C,D,E,F$ が固定なので、そんなに状態が多く無さそうなので、再帰で書いて後から適当にメモ化した。

fn main() {
    input! {
        n : usize,
        m : usize,
        a : i64,
        b : i64,
        c : i64,
        d : i64,
        e : i64,
        f : i64,
        xy : [(i64, i64); m]
    }
 
    let xy : FxHashSet<_> = xy.into_iter().collect();
    let mut memo = FxHashMap::default();
    let ans : Mint = dp(0, n,0i64, 0i64, a,b,c,d,e,f,&xy, &mut memo);
    println!("{}", ans);
}
 
fn dp(i:usize, n:usize, x: i64, y: i64, a: i64, b: i64, c: i64, d: i64, e: i64, f: i64, xy: &FxHashSet<(i64, i64)>, memo:&mut FxHashMap<(usize,i64,i64), Mint>) -> Mint {
    if xy.contains(&(x, y)) { return Mint::new(0); }
    if i == n { return Mint::new(1); }
    if let Some(res) = memo.get(&(i, x, y)) { return *res; }
 
    let mut res = Mint::new(0);
    res += dp(i+1, n,x + a, y + b, a, b, c, d, e, f, xy, memo);
    res += dp(i+1, n,x + c, y + d, a, b, c, d, e, f, xy, memo);
    res += dp(i+1, n,x + e, y + f, a, b, c, d, e, f, xy, memo);
 
    memo.insert((i, x, y), res);
    res
}

提出

F - Manhattan Cafe

問題文

これ成分ごとに $ \ [ \max(p_i, q_i) - D, \min(p_i, q_i) + D ] $ くらいの範囲で、$p$ に関する差の絶対値の和と $q$ に関する差の絶対値の和を持って適当にやれば良さそう。 E と同じく再帰で適当に書いて後でメモ化した。

後で解説を読んでみたんだけど、何を言っているか分からない。困った

fn main() {
    input! {
        n : usize,
        d : i64,
        p : [i64; n],
        q : [i64; n]
    }
 
    let mut memo = FxHashMap::default();
    let ans = f(0, n, 0, 0, d, &p, &q, &mut memo);
    println!("{}", ans);
}
 
fn f(i: usize, n: usize, pd:i64, qd:i64, d: i64, p: &Vec<i64>, q: &Vec<i64>, memo:&mut FxHashMap<(usize, i64, i64), Mint>) -> Mint {
    if i == n {
        return if pd <= d && qd <= d { Mint::new(1) } else { Mint::new(0) };
    }
    if let Some(res) = memo.get(&(i, pd, qd)) { return *res; }
 
    let mut res = Mint::new(0);
 
    let min = p[i].min(q[i]);
    let max = p[i].max(q[i]);
    for r in max-d ..= min+d {
        let pd = pd + (p[i] - r).abs();
        let qd = qd + (q[i] - r).abs();
        if pd > d || qd > d { continue }
        res += f(i+1, n, pd, qd, d, p, q, memo);
    }
 
    memo.insert((i, pd, qd), res);
    res
}