AtCoder Beginner Contest 255 - zeronosu77108’s blog

A - You should output ARC, though this is ABC.

2行2列の行列が与えられるので、その $R$ 行 $C$ 列のものを出力して下さいという問題。2次元の配列で受け取りができれば簡単です。

fn main() {
    input! {
        r : Usize1,
        c : Usize1,
        a : [[i64; 2]; 2]
    }
 
    println!("{}", a[r][c]);
}

提出

B - Light It Up

問題文

$N$ 人それぞれ、明かりを持っている $K$ 人の最短距離の最大値が答えになります。

fn main() {
    input! {
        n : usize,
        k : usize,
        a : [Usize1; k],
        p : [(f64, f64); n]
    }
 
    let mut ans: f64 = 0.;
    for &(x1,y1) in p.iter() {
        let mut t = std::f64::MAX;
        for &i in a.iter() {
            t = t.min( hypot(x1 - p[i].0, y1 - p[i].1));
        }
        ans = ans.max(t);
    }
 
    println!("{}", ans);
}

提出

C - ±1 Operation 1

問題文

算数をします。終わり。上限よりも大きいか、下限よりも小さいなら上限か下限に合わせれば良いです。間なら、そこから一番近い上側の要素か、下側の要素に合わせたら良いです。僕の書き方だと、 $d=0$ で最初から一致しているときにバグるので場合分けしておきます。

fn main() {
    input! {
        mut x : i64,
        a : i64,
        d : i64,
        n : i64
    }
 
    if d == 0 && a == x { println!("0"); return; }
 
    let min = a.min(a + d*(n-1));
    let max = a.max(a + d*(n-1));
 
    let ans;
    if max < x || x < min {
        ans = (x - (a+d*(n-1))).abs().min((x-a).abs())
    } else {
        let p = x - a;
        let mut t = std::i64::MAX;
 
        if (min..=max).contains(&((p/d+1)*d+a)) {
            t = t.min(((p/d+1)*d+a - x).abs());
        }
 
        if (min..=max).contains(&(p/d*d+a)) {
            t = t.min((x - p/d*d-a).abs());
        }
 
        ans = t;
    }
 
    println!("{}", ans);
}

提出

D - ±1 Operation 2

問題文

こっちの方が（競プロチックで）僕にとっては簡単でした。 $X$ に揃えるとき、 $X$未満の要素数・ $X$ 未満の要素の総和、 $X$以上の要素数・ $X$ 以上の要素の総和が分かれば計算できます。$A$ をソートしておて $X$ がどこに入るか二分探索で求めてそこから良い感じにやれば良いです。累積和を取っておくと総和はすぐ求まります。

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

    a.sort();
    let mut csum = vec![0; n+1];
    for i in 0..n { csum[i+1] = csum[i] + a[i]; }
    
    let mut ans = vec![];
    for x in queries {
        let index = a.lower_bound(&x);
        let left = csum[index];
        let leftc = index;
        let rightc = n - index;
        let right = csum[n] - csum[index];

        ans.push(x*leftc - left + right - x*rightc);
    }

    println!("{}", ans.iter().join("\n"));
}

提出

E - Lucky Numbers

問題文

式を書くと $A _ 0$ を決めたら全部決まる事が分かります。後は、 $A_0$ から求められるように累積和みたいなものを取っておいて、 $ A _ i$ を $X_j$ にするとき他の値がラッキーナンバーになっているかチェックしたら良いです。

よく考えたら、 $A _ i$ 要素を $X _ j$ にするときの $A _ 0$ を全部探索して、最も多い $A _ 0$ を採用したら良いので、$ M $ のループ 1個減らせる。実装してみたが、O($ N M ^ 2 $) とそんなに変わらなかった。

fn main() {
    input! {
        n : usize,
        m : usize,
        s : [i64; n-1],
        x : [i64; m]
    }

    let y : FxHashSet<_> = x.iter().cloned().collect();

    let mut csum = vec![0; n];
    for i in 0..n-1 {
        csum[i+1] = csum[i] + if i%2==0 {s[i]} else {-s[i]}
    }

    let mut cnt1 = FxHashMap::default();
    let mut cnt2 = FxHashMap::default();
    for (i, &a) in csum.iter().enumerate() {
        if i%2 == 0 { *cnt1.entry(a).or_insert(0) += 1; }
        else { *cnt2.entry(a).or_insert(0) += 1; }
    }

    let mut ans = 0;
    for (i, &ai) in csum.iter().enumerate() {
        for &xj in x.iter() {
            // ai を xj  にするための a_0 の値
            let a0 = if i%2!=0 {ai - xj} else {xj - ai};
            let mut t = 0;

            for &xp in x.iter() {
                let p = xp + a0;
                if let Some(&c) = cnt2.get(&p) { t += c; }
                let p = a0 - xp;
                if let Some(&c) = cnt1.get(&p) { t += c; }
            }

            chmax(&mut ans, t);

        }
    }

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