プログラミングのお題スレ Part22 (863ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
738(7): デフォルトの名無しさん [sage] 04/08(火)23:28 ID:OzdBhfzQ(1/2)
>>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
}
739(3): デフォルトの名無しさん [sage] 04/08(火)23:30 ID:OzdBhfzQ(2/2)
>>738
素因数の総和が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): デフォルトの名無しさん [] 04/09(水)22:22 ID:Ip5PiQSs(1/3)
>>738-739
出題時に作成した解答例
C++
https://ideone.com/y1YZlj
R
https://ideone.com/zvqAsg
と解の個数と最小値・最大値が一致するので正解だろう。
ローカルでコンパイルしようとしたら、
error[E0425]: cannot find function `generate_primes` in this scope
と表示されコンパイルできなかったので、実行時間の比較はできなかった。
743(1): デフォルトの名無しさん [] 04/09(水)23:40 ID:Ip5PiQSs(2/3)
>>738-739 742と>>741のC++を解の標準出力なしに変更したものの実行速度を比較したら、
前者の方が2000万以下では27%、20億以下では11%速かった。
745: デフォルトの名無しさん [] 04/09(水)23:50 ID:Ip5PiQSs(3/3)
>>744
前者は>>738-739 742のRustプログラム。後者 (C++プログラム) はvectorへの要素追加回数が
多いので時間が掛かっていそう。
750(3): デフォルトの名無しさん [sage] 04/11(金)07:38 ID:oaeJuxMT(1)
>>738 に手を加えて10倍速くしてみた
fn solve(n: usize, limit: usize) -> Vec<usize> {
let mut answer = Vec::new();
let mut pnt = generate_primes(n).windows(2).rev().map(|s| (s[1], s[0], 0, 0)).collect::<Vec<_>>();
let (mut ci, mut cn, mut ct) = (0, n, 1_usize);
'advance: loop {
pnt[ci..].iter_mut().for_each(|(_p, _q, 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); }
}
'back: for (i, (p, q, n, t)) in pnt.iter_mut().enumerate().rev() {
'again: loop {
if *n < *p { continue 'back; }
*n -= *p; *t *= *p;
if *n ==1 || *t > limit { continue 'back; }
if *n == 0 { answer.push(*t); continue 'back; }
if *q > 3 {
let mut tt = *t * (*n % *q);
for _ in 0..(*n / *q) { tt *= *q; if tt > limit { continue 'again; } }
}; break 'again;
}; (ci, cn, ct) = (i, *n, *t); continue 'advance;
}; break 'advance;
}; answer.sort(); answer
}
752: デフォルトの名無しさん [] 04/11(金)22:44 ID:4wK2/GRg(1)
>>750
これはとても速いな。ローカルで実行してみたら、>>738のRustプログラムと比較して
2000万以下で16倍、20億以下で55倍の速さだった。
761: デフォルトの名無しさん [sage] 04/17(木)00:32 ID:dz0qzhSq(3/3)
>>738
これも2025以下の素数を組み合わせて和が2025になる解を調べる方法。
解一覧を収めるベクタ以外は、固定の長さ305のベクタのみが使われている。
この長さの 305 とは2025以下～3以上の素数[2017, 2011, ... 5, 3]の数になってる。
各素数の冪乗の和 2017^e2017 + 2011^e2011 + ... + 5^e5 + 3^e3 及び積を計算していくが、
各指数のe2017などは解に不要なので使われておらず、
各冪乗の和自体も不要なので2025までの残りの数が使われていて、
固定長ベクタの値は(素数, 残りの数, ここまでの積)の3つ組となっている。
その素数を1つ使うと残りの数が減算されてて積が乗算されるのを繰り返していく。
素数2だけ特別扱いされており、残りの数の半分だけ左シフトすると解の積が出来上がる。
各if～continueが枝刈りとなっていて、残りの下限(=和の上限)や積の上限などがある
この改良版>>750では、次の素数以降の組み合わせで起き得る積の下限で枝刈りしている。
例えば7以下の素数で残り21ならば積の下限は7*7*7=343となるため、
ここまでの積に343を掛けた値が2000万(または20億)を超えていれば枝刈りできるようだ。
このアルゴリズムは作業メモリが固定で小さく常にL1キャッシュに乗り有利と思われる点と、
様々な枝刈りがしやすく処理する組み合わせを大きく減らしている点により、
他のアルゴリズムより桁違いに高速になっていると推測される。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.036s