bouzuya.hatenablog.com

ぼうずやのにっき

いろんなくるま / ARC050 B を解いた

「いろんなくるま！」と、子どもが『はたらくくるま』の動画を観たがるので、『マッドマックス 怒りのデス・ロード』を観せておいた。

(おおむね nostr に類似の投稿済み)

  • ARC050 B - 花束 (AtCoder Regular Contest 050 B問題) https://atcoder.jp/contests/arc050/tasks/arc050_b
    • https://atcoder.jp/contests/arc050/submissions/41306763
    • 花束の個数 (答え) を二分探索する
    • 作ることのできるものとできないものに二分する
    • 花束の個数を X とする
    • どちらの花束を選んでも赤・青を 1 本ずつ使うとすることで 1 の扱いが楽になる
    • 先に赤い花および青い花から X 本を引く
    • 赤い花が x - 1 本でひとつめの花束をつくれる
    • 青い花が y - 1 本でふたつめの花束をつくれる
    • 足せばつくれる花束の個数の合計になる、これが X 以上なら作ることができる
use proconio::input;

fn main() {
    input! {
        r: usize,
        b: usize,
        x: usize,
        y: usize,
    }

    let mut ok = 0_usize;
    let mut ng = r + b;
    while ng - ok > 1 {
        let mid = ok + (ng - ok) / 2;
        if (mid <= r) && (mid <= b) && (((r - mid) / (x - 1)) + ((b - mid) / (y - 1)) >= mid) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    let ans = ok;
    println!("{}", ans);
}

今日のコミット。