ABC389:Rustで解く！問題解説

AtCoder Beginner Contest 389のA~E問題をRustで解いた際の解法をまとめました。

A問題

• 問題

https://atcoder.jp/contests/abc389/tasks/abc389_a

• 解説

1文字目と3文字目を数値に変換して掛け算します。

• コード

use proconio::{input, marker::Chars};
fn main() {
    input!{
        s: Chars,
    }
    let s1 = s[0] as usize - 0x30;
    let s2 = s[2] as usize - 0x30;
    println!("{}", s1*s2);
}

B問題

• 問題

https://atcoder.jp/contests/abc389/tasks/abc389_b

• 解説

$N$ を1から順番に全探索して、 $N!$ が $X$ と一致するものを見つけます。

• コード

use proconio::input;
fn main() {
    input!{
        x: u128
    }
    const LIMIT : u128 = 3_000_000_000_000_000_000;
 
    let mut ans = 1;
    let mut now = 1;
 
    loop {
        if now == x {
            println!("{}", ans);
            return;
        }
        if now * (ans + 1) > LIMIT { break; }
        now *= ans + 1;
        ans += 1;
    }
    // 問題文の制約上、ここには来ない
    println!("-1");
}

C問題

• 問題

https://atcoder.jp/contests/abc389/tasks/abc389_c

• 解説

$Q$ 個のクエリを順番に処理します。
ただし、クエリのタイプ3で現在いるヘビの先頭から順番に長さを数えていくと、クエリ1回あたり最大 $N$ 回の計算が必要になります。クエリのタイプ3で、最後尾ばかりを答えるような入力が与えられていると、計算量が $O(N^2)$ となってしまい、実行時間内に解くことができません。
そこで、以下の2点を管理した上で(1)～(3)の処理を行い、クエリのタイプ3でヘビの長さを効率よく答えられるようにします。

• 逃げたヘビの数
• 次に追加するヘビの先頭座標

(1) タイプ1の場合
ヘビの先頭座標を配列の末尾に追加し、またその長さ分を加算した値を次の先頭座標とします。

(2) タイプ2の場合
逃げたヘビの数をカウントします。

(3) タイプ3の場合
「逃げたヘビの数と指定されたヘビの数を加えた番号」の先頭座標から、「逃げたヘビの数」の先頭座標を引いた長さを出力します。

• コード

use proconio::{input, marker::Usize1};

fn main() {
    input!{
        q: usize,
    }

    // 逃げたヘビの数
    let mut cnt = 0;
    // 次に追加するヘビの先頭座標
    let mut top_pos = 0;
    // ヘビの先頭座標リスト
    let mut vec = Vec::new();
    
    for _ in 0..q {
        input!{
            nm: usize,
        }

        if nm == 1 {
            input!{
                l: usize,
            }
            // 先頭座標を追加
            vec.push(top_pos);
            top_pos += l;
        }
        else if nm == 2 {
            // 逃げたヘビの数を更新
            cnt += 1;
        }
        else {
            input!{
                k: Usize1,
            }
            // 「逃げたヘビの数+k番目」の先頭座標 - 「逃げたヘビの数」の先頭座標
            let val = vec[k + cnt] - vec[cnt];
            println!("{}", val);
        }
    }
}

D問題

• 問題

https://atcoder.jp/contests/abc389/tasks/abc389_d

• 解説

半径 $R$ の円に内包するマス目を数え上げます。
(例えば、半径 $R$ が5の場合、以下の図に示す赤色・黄色・青色の正方形のマス目を数え上げればよいです。)

具体的には以下の(1)~(3)に分けて数え上げます。

(1) x軸上かつy軸上に位置するもの (図中の赤色のマス目)
原点 $(0,0)$ の1個のみ存在します。

(2) x軸上、y軸上のどちらか一方に位置するもの (図中の黄色のマス目)
x軸の正に注目すると、$(1,0)$ ～ $(r-1,0)$ の計 $r-1$ 個が該当します。
同様に、x軸の負、y軸の正、y軸の負にもそれぞれ $r-1$ 個あるため、全体では $4(r-1)$ 個になります。

(3) x軸上、y軸上のどちらにも位置しないもの (図中の青色のマス目)
第1象限 $(x > 0, y > 0)$ に注目します。各正方形について原点から最も遠い座標は、常に正方形の右上にあります。y座標を $1$ から $r-1$ の間で調べていく中で、以下の不等式を満たす最大のx座標を、マス目の個数として数えていきます。

$$(x+0.5)^2 + (y+0.5)^2 \leq r^2$$

第2～4象限についても同じ個数存在するため、第1象限で見つけた個数の4倍分あります。

• コード

use proconio::input;
fn main() {
    input!{
        r: usize,
    }

    // 以下の3つについて数え上げ
    // 1.x軸上かつy軸上に位置するもの
    // -> (0,0)の1個のみ
    // 2.x軸上、y軸上のどちらか一方に位置するもの
    // -> (1,0) ~ (r-1,0)の(r-1)個。「正と負」*「x軸,y軸」の4通り
    // -> 4(r-1)
    // 3.x軸上、y軸上のどちらにも位置しないもの
    // -> 1 ~ (r-1)の間で行毎に数え上げ。計x個。「正と負」*「x軸,y軸」の4通り。
    // -> 4x

    let mut ans = 0;
    // (1) 原点のマス目
    ans += 1;
    // (2) x軸上、y軸上のどちらか一方に位置するマス目
    ans += (r-1)*4;

    // (3) x軸上、y軸上のどちらにも位置しないマス目
    // (x+0.5)^2 + (y+0.5)^2
    // ↓ 式変形
     // (2x+1)^2 + (2y+1)^2 <= 4*R^2 となるものを数え上げ
    let mut x = r-1;
    for y in 1..r {
        while !is_inner(x, y, r) {
            x -= 1;
        }
        ans += x*4;
    }
    println!("{}", ans);
}

fn is_inner(x: usize, y: usize, r: usize) -> bool {
    (2*x+1)*(2*x+1) + (2*y+1)*(2*y+1) <= 4*r*r
}

E問題

• 問題

https://atcoder.jp/contests/abc389/tasks/abc389_e

• 解説

商品を1個ずつ追加で購入しようとした際に、その時点で価格が最も安いものを貪欲に選んでいけばよいです。各商品は1個購入時は計 $P$ 円、2個購入時は計 $4P$ 円、3個購入時は計 $9P$ 円、・・・となっていますが、価格の差分を考えて、1個目購入時は $P$ 円、2個目購入時は $3P$ 円、3個目購入時は $5P$ 円・・・というように読み替えます。
しかし、上のように読み替えて商品を選んでいくだけでは、購入する商品の個数が多いケースで計算量が増加し、実行時間内に解くことができません。
そこで、商品を購入する度に選ぶ価格が大きくなる点に注目し、以下を二分探索で決定します。

• 単価が $X$ 円以下の商品を全て購入すると決めた際に、部分的に買えるまたは全く買うことができない商品の価格

二分探索で $X$ 円を決定し、実際に単価が $X$ 円以下の商品を全て購入すると、$M$ 円を超えてしまいますが、「 $M$ 円を超過した金額 / $X$円」 が購入できない個数となるので、その分を引けばよいです。

• コード

use proconio::input;

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

    // 単価X円以下の全てを購入しようとして、購入出来ない商品が含まれる価格を
    // 二分探索で決める。
    let mut ng = 0;
    let mut ok = m + 1;
    
    for _ in 0..100 {
        let mid = (ng + ok) / 2;
        if can_buy(mid, m, &p) {
            ng = mid;
        } else {
            ok = mid;
        }
    }

    // 価格と個数を取得
    let (total_cost, total_cnt) = calculate_total_buy(ok, &p);

    // M円を超えて購入した分を引く
    let over_cnt = (total_cost - m + ok - 1) / ok;
    println!("{}", total_cnt - over_cnt);
}

// 単価X円以下を全て購入しようとしたときの、費用がM円以下かどうかを確認
fn can_buy(x: u128, m: u128, p: &Vec<u128>) -> bool {
    let cost_cnt = calculate_total_buy(x, p);
    cost_cnt.0 <= m
}

// 価格と個数を取得
fn calculate_total_buy(x: u128, p: &Vec<u128>) -> (u128, u128) {
    let mut total_cost = 0;
    let mut total_cnt = 0;
    
    for &pp in p {
        let cnt = ((x / pp) + 1) / 2;  // 何個購入できるか計算
        total_cost += cnt * cnt * pp;  
        total_cnt += cnt;
    }
    
    (total_cost, total_cnt)
}