結果

問題 No.3422 Sazanka's hobby
コンテスト
ユーザー NakLon131
提出日時 2026-01-11 15:13:12
言語 Rust
(1.92.0 + proconio + num)
結果
AC  
実行時間 231 ms / 2,000 ms
コード長 1,187 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 25,757 ms
コンパイル使用メモリ 414,692 KB
実行使用メモリ 33,380 KB
最終ジャッジ日時 2026-01-11 15:14:14
合計ジャッジ時間 28,854 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// use itertools::Itertools;
use proconio::input;

fn main() {
    input! {
		n: usize, // 花の数
		m: usize, // 部屋の高さ
		ab: [(usize, usize); n], // (元の高さ,1日に伸びる高さ)
	}

	// 各花が最大何日まで放置可能かを調べる
	let mut day = calc_stay_day(n, m, &ab);

	// 日数が少ない順にソート
	day.sort();

// {
// 	println!("{}", day.iter().join(" "));
// }

	// 1日にとる本数kを二分探索
	let ans = bin_search(n, &day);
	println!("{}", ans);
}

fn calc_stay_day(_n: usize, m: usize, ab: &Vec<(usize, usize)>) -> Vec<usize> {
	let mut ret = Vec::new();
	for &(a, b) in ab {
		let day = (m - a) / b;
		ret.push(day);
	}
	ret
}

fn bin_search(n: usize, day: &Vec<usize>) -> usize {
	let mut ng = 0;
	let mut ok = n+1;
	while ok - ng > 1 {
		// 1日にとる本数
		let mid = (ng + ok) / 2;
		if isok(n, day, mid) {
			ok = mid;
		}
		else {
			ng = mid;
		}
	}
	ok
}

fn isok(n: usize, day: &Vec<usize>, k: usize) -> bool {
	let mut cur_day = 0;
	let mut cnt = 0;	
	for i in 0..n {
		if day[i] < cur_day {
			return false;
		}
		cnt += 1;
		if cnt == k { 
			cur_day += 1; 
			cnt = 0;
		}
	}
	true
}

/*
2 1000000
8 8
8 8


*/
0