プログラミングのお題スレ Part22 (858ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
739(3): デフォルトの名無しさん [sage] 2025/04/08(火) 23:30:40.48 ID:OzdBhfzQ(2/2) AAS
>>738738(7): デフォルトの名無しさん [sage] 2025/04/08(火) 23:28:40.30 ID:OzdBhfzQ(1/2) AAS
>>712 Rust
fn solve(n: usize, limit: usize) -> Vec<usize> {
let mut answer = Vec::new();
let mut pnt = generate_primes(n).iter().skip(1).rev().map(|&p| (p, 0, 0)).collect::<Vec<_>>();
let (mut ci, mut cn, mut ct) = (0, n, 1_usize);
'advance: loop {
pnt[ci..].iter_mut().for_each(|(_p, n, t)| (*n, *t) = (cn, ct));
if cn & 1 == 0 && ct.leading_zeros() >= (cn >> 1) as u32 {
ct <<= cn >> 1;
if ct <= limit { answer.push(ct as usize); }
}
for (i, (p, n, t)) in pnt.iter_mut().enumerate().rev() {
if *n < *p { continue; }
*n -= *p; *t *= *p;
if *t > limit { continue; }
if *n == 1 { continue; }
if *n == 0 { answer.push(*t as usize); continue; }
(ci, cn, ct) = (i, *n, *t);
continue 'advance;
};
break;
}
answer.sort(); answer
}
素因数の総和が2025になる問題を可能な素数の組合せ総当りで挑戦してみました
20億以下で約0.4秒と規定時間以内に実行できました
実行時間 solve(2025, 20000000): 22.638309ms
実行時間 solve(2025, 2000000000): 418.607978ms
fn main() {
for (n, limit) in [(2025, 2000_0000), (2025, 20_0000_0000)] {
let start_time = std::time::Instant::now();
let answer = solve(n, limit);
let end_time = std::time::Instant::now();
println!("実行時間 solve({n}, {limit}): {:?}", end_time - start_time);
// 個数と最初と最後の検証
let (valid_len, valid_first, valid_last) = match (n, limit) {
(2025, 2000_0000) => (1265, 30255, 19970000),
(2025, 20_0000_0000) => (49942, 30255, 1999986740),
_ => (0, 0, 0),
};
assert_eq!(answer.len(), valid_len);
assert_eq!(*answer.first().unwrap(), valid_first);
assert_eq!(*answer.last().unwrap(), valid_last);
}
}
741(4): デフォルトの名無しさん [] 2025/04/09(水) 22:22:33.83 ID:Ip5PiQSs(1/3) AAS
>>738-739
出題時に作成した解答例
C++
外部ﾘﾝｸ:ideone.com
R
外部ﾘﾝｸ:ideone.com
と解の個数と最小値・最大値が一致するので正解だろう。
ローカルでコンパイルしようとしたら、
error[E0425]: cannot find function `generate_primes` in this scope
と表示されコンパイルできなかったので、実行時間の比較はできなかった。
743(1): デフォルトの名無しさん [] 2025/04/09(水) 23:40:58.68 ID:Ip5PiQSs(2/3) AAS
>>738-739 742と>>741のC++を解の標準出力なしに変更したものの実行速度を比較したら、
前者の方が2000万以下では27%、20億以下では11%速かった。
745: デフォルトの名無しさん [] 2025/04/09(水) 23:50:45.01 ID:Ip5PiQSs(3/3) AAS
>>744前者は>>738-739 742のRustプログラム。後者 (C++プログラム) はvectorへの要素追加回数が
多いので時間が掛かっていそう。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.047s