AtCoder Beginner Contest 246 - zeronosu77108’s blog

A - Four Points

長方形の3点の座標が与えられるので、残り1点を求めて下さいという問題。長方形の各辺は $x$軸か $y$軸に平行になっているので、必ず2点はペアになっているはずです。ということで $x_1 == x_2$ なら $x_4$ は $x_3$ と同じになるはずです。他の組合せも同じ感じで場合分けして書きます。

fn main() {
    input! {
        (x1, y1) : (i64, i64),
        (x2, y2) : (i64, i64),
        (x3, y3) : (i64, i64)
    }
 
    let x4 = if x1==x2 {x3} else if x1==x3 {x2} else {x1};
    let y4 = if y1==y2 {y3} else if y1==y3 {y2} else {y1};
 
    println!("{} {}", x4, y4);
}

提出

ちなみに同じ値を xor すると $0$ になるので、 $x_4 = x_1 \oplus x_2 \oplus x_3$ として求める事もできます（コード）。

B - Get Closer

問題文

$(0,0)$ から $(A,B)$ に向かって距離1だけ進んだ座標を求める問題。

これは、$(A, B)$ までの距離が分かればそれで割れば良いです。 $\sqrt{A²+B²}$ で求められます。 C++ や Rust には hypot という関数があってそれで求めるのが楽です（他の言語はあるか知りません…）。

fn main() {
    input! {
        a : f64,
        b : f64
    }
 
    let dist = hypot(a, b);
    let ans = (a/dist, b/dist);
    println!("{} {}", ans.0, ans.1);
}

提出

C - Coupon

問題文

クーポンを使うと1枚につき $X$円安くなるのでできるだけ安く買ったときの金額を求める問題。

$k$ 枚使って、 $kX$円値引きして $0$ 未満になると $0$ 円になってしまうので、 $X$円きっちり引かれる方を優先したいです。そこで一旦、$kX$ が $a_i$ を超えないように値引きをして、後で超える分の値引きをします。

超える分に関しては、$1$ 円の商品と $2$ 円の商品があったときに、どちらに $3$ 円クーポン使いますか？というのを考えると $2$ 円に使った方が良いので、大きい方から貪欲に割り当てていきます。

fn main() {
    input! {
        n : usize,
        mut k : usize,
        x : usize,
        mut a : [usize; n]
    }
 
    a.sort(); a.reverse();
    for a in a.iter_mut() {
        let c = k.min(*a / x);
        k -= c; *a -= c * x;
    }
 
    a.sort(); a.reverse();
    let mut ans = 0;
    for &a in a.iter() {
        if a > 0 && k > 0 { k -= 1; continue }
        ans += a;
    }
 
    println!("{}", ans);
}

提出

D - 2-variable Function

問題文

$X = a³ + a^2b + ab² + b³$ としたとき、 $N$ 以上となる $X$ の最小値を求める問題。 $N \leq 10^{18}$ と制約がかなり大きいです。ただ、 $a³$ ということに注目すると、 $a³ = 10^{18}$ になる値を考えると $10⁶$ くらいで良いことが分かります。そこで、 $a$ を全探索してみます。 $a$ の値を決め打ったときに、 $b$ の値が増加すると $X$ の値も単調増加することが分かります。よって、 $N$ 以上となるような $b$ を二分探索などで求めたら良いです。

fn main() {
    input! {
        n : u128
    }
 
    let z = |a:u128, b:u128| { a*a*a + a*a*b + a*b*b + b*b*b };
 
    let mut ans = std::u128::MAX;
    for a in 0..=1_000_000 {
        let mut l = 0;
        let mut r = 1_000_001;
 
        while l+1 < r {
            let b = (l+r)/ 2;
            if z(a,b) >= n { r = b; }
            else { l = b; }
        }
 
        let zi = z(a,l);
        if n <= zi { ans = ans.min(zi); }
 
        let zi = z(a,r);
        if n <= zi { ans = ans.min(zi); }
    }
 
    println!("{}", ans);
}

提出

E - Bishop 2

問題文

障害物がある盤面で、ある座標からスタートしてある座標までビショップの動きをしてたどり着けますか？たどり着けるとしたらなん手で行けますか？という問題。障害物は取ったり飛び越えたりはできません。

愚直に探索すると、ちょっと難しそうなのでビショップについて考えてみます。ビショップのは障害物が無いかぎり斜めの全てのマスに1手で移動できます。よって進む向きに番号を振ってみます。左上に$0$、右上に$1$…という感じです。そして、同じ方向に進み続ける限り移動の手数は $0$ だと考えて良いです。つまり、同じ方向に進む場合のコストは$0$、方向を変える場合のコストは$1$ として各マスへの最短経路を求めたら良いです。辺に重みがある最短経路なので dijkstra法をしたくなりますが、今回は $0,1$ しかないため deque などをしようし、 $0$ の場合は先頭、 $1$ の場合は末尾に追加することで正しく探索できます（01-BFSと呼ばれてたりします）。

fn main() {
    input! {
        n : usize,
        a : (Usize1, Usize1),
        b : (Usize1, Usize1),
        s : [Chars; n]
    }
 
 
    let mut q = VecDeque::new();
    for i in 0..4 { q.push_back((a.0, a.1, i, 1)); }
 
    let mut dist = vec![vec![vec![None; 4]; n]; n];
    for i in 0..4 { dist[a.0][a.1][i] = Some(Reverse(1)); }
 
 
    while let Some((y, x, e, c)) = q.pop_front() {
        if let Some(Reverse(d)) = dist[y][x][e] {
            if d > c { continue }
 
            for (i, (dx, dy)) in vec![(!0, !0), (!0, 1), (1, !0), (1, 1)].into_iter().enumerate() {
                let cost = if e == i { 0 } else { 1 };
                let mut xi = x.wrapping_add(dx);
                let mut yi = y.wrapping_add(dy);
                if n <= xi || n <= yi || s[yi][xi] == '#' { continue }
 
                if chmax(&mut dist[yi][xi][i], Some(Reverse(d + cost))) {
                    if cost == 0 { q.push_front((yi, xi, i, d + cost)); }
                    else { q.push_back((yi, xi, i, d + cost)); }
                }
            }
        }
    }
 
 
    if let Some(Reverse(ans)) = dist[b.0][b.1].iter().max().unwrap() {
        println!("{}", ans);
    } else {
        println!("-1");
    }
}

提出

F - typewriter

問題文

各行で与えられる文字だけを使って $L$ 文字入力するとしたとき、その文字列は何通りありますか？という問題。

まず、$N=1$ のときを考えて見ます。このとき、$L$ 桁の文字列のうち、1文字目は $S_1$ の種類数分あってそれが $L$ 桁あるので、 $S_1$ の文字の種類数を $|S_1|$ とすると、 $|S_1|^L$ になります。では、 $N=2$ のときはどうでしょう？$S_1$ と $S_2$ それぞれで作れる物を足して、両方から作れる物を引けば良いです。では、 $N=3$ では？ $|S_1|^L + |S_2|^L + |S_3|^L - |S_1 \cap S_2|^L - |S_1 \cap S_3|^L - |S_2 \cap S_3|^L$ としたくなりますが、これでは、 $S_1, S_2, S_3$ 全部で共通して作れる物が余計に引かれます。つまり、 $|S_1 \cap S_2 \cap S_3|^L$ を足してあげれば良いです（包除原理）。

拡張すると、$S$ が何個変わった式かっていうのの偶奇で良い感じにします（詳しくは自分で調べて下さい…）。良い感じに足し引きすると求まります。

fn main() {
    input! {
        n : usize,
        l : usize,
        s : [Bytes; n]
    }
    const MOD : usize = 998_244_353;

    let s = s.into_iter().map(|s|{
        s.into_iter().map(|c|{ (c - b'a') as usize }).collect_vec()
    }).collect_vec();

    let mut ans = 0;
    for i in 1usize..1<<n {
        let mut cnt = vec![0; 26];
        for j in 0..n {
            if i>>j & 1 == 1 {
                for &c in s[j].iter() { cnt[c] += 1; }
            }
        }

        let c = cnt.iter().filter(|&&cnt| cnt == i.count_ones()).count();
        if i.count_ones() % 2 == 1 { ans += pow(c, l, MOD); }
        else { ans = ans + MOD - pow(c, l, MOD); }
        ans %= MOD;
    }

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