AtCoder Beginner Contest 248 - zeronosu77108’s blog

A - Lacked Number

"0123456789" のうち $S$ の中にあるやつを削除します。文字数が少ないので多少計算量の悪い書き方しても大丈夫です。 filter で1つずつ contains で確認すると良いです。

fn main() {
    input! {
        s : Chars
    }
 
    let ans = "0123456789".chars().filter(|&c| !s.contains(&c)).collect_vec();
    println!("{}", ans[0]);
}

提出

B - Slimes

問題文

$A$ が $B$ 以上になるまで $K$ 倍していきます。 while 実装したら良い感じになります。その回数を数えたら良いです。

fn main() {
    input! {
        mut a : usize,
        b : usize,
        k : usize
    }
 
    let mut ans = 0;
    while a < b { a*=k; ans+=1; }
    println!("{}", ans);
}

提出

C - Dice Sum

問題文

$K$ 個のボールと $N-1$ 個の縦棒を良い感じに並べる組合せとか考えたんですが、筋が良く無さそう。 $A_i \leq 50$ と結構少ないので、 $A_i$ を1つずつ決めていけば良さそう。

とりあえず良い感じに再帰で $A_i$ を決めていって $K$ 以下となる組合せを数える。後は、$i$項決めた・合計が $j$ でメモ化したら良い。

fn main() {
    input! {
        n : usize,
        m : usize,
        k : usize
    }
 
    let mut memo = FxHashMap::default();
    let ans = f(0, 0, n, m, k, &mut memo);
    println!("{}", ans);
}
 
fn f(i:usize, sum:usize, n:usize, m:usize, k:usize, memo:&mut FxHashMap<(usize,usize), usize>) -> usize {
    if let Some(res) = memo.get(&(i, sum)) { return *res; }
    if i == n {
        if sum <= k { return 1; }
        else { return 0; }
    }
 
    let mut res = 0;
    for j in 1..=m {
        res += f(i+1, sum+j, n, m, k, memo);
        res %= MOD;
    }
 
    memo.insert((i, sum), res);
    res
}

提出

D - Range Count Query

問題文

なんかパッと見良い方法が思い浮かばなかったので、 Mo's algorithm を貼る。終わり。まともな方針は、値毎に index 持って、 lower_bound と upper_bound 使って間の数を数えたら良いっぽい。

fn main() {
    input! {
        n : usize,
        a : [Usize1; n],
        q : usize,
        queries : [(Usize1, usize, Usize1); q]
    }
 
    let mut queries = queries.into_iter().enumerate().map(|(i, (l, r, x))| (i, l, r, x)).collect_vec();
    queries.sort_by_cached_key(|&(_, l, r, _)| hilbertorder(l, r));
 
    let mut cnt = vec![0; n];
    let mut count = 0;
 
    let mut nowl = 0;
    let mut nowr = 0;
    let mut ans = vec![0; q];
    for (i, l, r, x) in queries {
        for i in (l..nowl).chain(nowr..r) {
            add(&mut count, &mut cnt, a[i]);
        }
 
        for i in (nowl..l).chain(r..nowr) {
            del(&mut count, &mut cnt, a[i]);
        }
 
        nowl = l; nowr = r;
        ans[i] = cnt[x];
    }
 
    println!("{}", ans.iter().join("\n"));
}
 
 
fn add(count :&mut usize, cnt:&mut Vec<usize>, x:usize) {
    if cnt[x] == 0 { *count += 1; }
    cnt[x] += 1;
}
 
fn del(count:&mut usize, cnt:&mut Vec<usize>, x:usize) {
    cnt[x] -= 1;
    if cnt[x] == 0 { *count -= 1; }
}
 
 
fn hilbertorder(mut x:usize, mut y:usize) -> usize {
    const LOG : usize = 20;
    const MAXN : usize = 1 << LOG;
 
    let mut d = 0;
    let mut s = 1 << (LOG - 1);
    while s > 0 {
        let rx = if x & s > 0 {1} else {0};
        let ry = if y & s > 0 {1} else {0};
        s /= 2;
 
        d = (d<<2) | ((rx*3) ^ ry);
 
        if ry>0 { continue }
        if rx>0 {
            x = MAXN - x;
            y = MAXN - y;
        }
        std::mem::swap(&mut x, &mut y);
    }
    d
}

提出

E - K-colinear Line

問題文

なんですか？この問題。

幾何ライブラリを貼って、 ccw を使うと良い感じになりそう。 image.png (92.6 kB) 引用

端点を2つ選んでその間に $K$ 個以上の点があるか確認したら良い。点 $A, B$ と $C$ の関係を決める。 $A,B$ の間ではなく先にあると困るので、良い感じにする必要がある。

$A$ と $B$ を端点に ccw して、 +2 または -2 なら $A, B$ を伸ばした先に $C$ があるのでスキップする。そういう点が無い場合は、 0 になる点を数えたら良い。

僕の幾何ライブラリが f64 でできているので多分誤差で WA。判定に必要な部分だけを i64 で書き直す……。つ、辛い…。$K = 1$ のときは、その点を通る直線は無限にあるので注意。

整数で求める幾何ライブラリも作ります……。

fn main() {
    input! {
        n : usize,
        k : usize,
        xy : [(i64, i64); n]
    }
 
    if k==1 && n>=1 { println!("Infinity"); return; }
 
    let cross = |p1:(i64, i64), p2:(i64, i64)| {
        p1.0 * p2.1 - p1.1 * p2.0
    };
    let dot = |p1:(i64, i64), p2:(i64, i64)| {
        p1.0 * p2.0 + p1.1 * p2.1
    };
    let dist = |p1:(i64, i64), p2:(i64, i64)| {
        (p1.0 - p2.0) * (p1.0 - p2.0) + (p1.1 - p2.1) * (p1.1 - p2.1)
    };
 
    let ccw = |p1:(i64, i64), p2:(i64, i64), p3:(i64, i64)| -> i64 {
        if cross((p2.0 - p1.0, p2.1 - p1.1), (p3.0 - p1.0, p3.1 - p1.1)) > 0 { return 1 }
        if cross((p2.0 - p1.0, p2.1 - p1.1), (p3.0 - p1.0, p3.1 - p1.1)) < 0 { return -1 }
        if dot((p2.0 - p1.0, p2.1 - p1.1), (p3.0 - p1.0, p3.1 - p1.1)) < 0 { return 2 }
        if dist((p2.0 - p1.0, p2.1 - p1.1), (0,0)) < dist((p3.0 - p1.0, p3.1 - p1.1), (0,0)) { return -2 }
        0
    };
 
    let mut ans = 0;
    for i in 0..n { for j in i+1..n {
        let mut cnt = 0;
        for l in 0..n {
            if i==l || j==l { cnt += 1; continue }
            if ccw(xy[i], xy[j], xy[l]).abs() == 2 { cnt = 0; break }
            if ccw(xy[i], xy[j], xy[l]).abs() == 0 { cnt += 1;}
        }
        if cnt >= k { ans += 1; }
    }}
 
    println!("{}", ans)
}