[過去ﾛｸﾞ] プログラミングのお題スレ Part21 (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
738(13): デフォルトの名無しさん [] 2023/06/08(木) 22:14:54.10 ID:B/+C/EDE(2/2) AAS
お題：1234567以下の素数 a, b, c で a + b + c = 1234567 かつ a ≤ b ≤ c を満たす組み合わせは何通りあるか計算せよ。
739(1): デフォルトの名無しさん [sage] 2023/06/09(金) 04:35:40.14 ID:Xuj67sW5(1) AAS
>>738
外部ﾘﾝｸ:ideone.com
力業っぽくなったな、3で割って1余る整数計しか解けない
742(2): デフォルトの名無しさん [] 2023/06/09(金) 20:08:26.01 ID:7Vf79qrZ(1) AAS
>>738 c
外部ﾘﾝｸ:ideone.com
#include <stdlib.h>
#include <math.h>
#include <stdio.h>
void sieve_of_eratosthenes(int n, int **isprime, int **primes_beg, int **primes_end) {
int i, m, j, nbytes = (1 + n) * sizeof **isprime, *map = malloc(nbytes), *beg = malloc(nbytes), *end;
for (i = 2; i <= n; i++) map[i] = 1;
for (i = 2, m = sqrt(n); i <= m; i++)
if (map[i]) for (j = i * i; j <= n; j += i) map[j] = 0;
for (i = 2, end = beg; i <= n; i++) if (map[i]) *end++ = i;
*isprime = map, *primes_beg = beg, *primes_end = end;
}
int main() {
int n = 1234567, *isprime, *primes_beg, *primes_end;
sieve_of_eratosthenes(n, &isprime, &primes_beg, &primes_end);
int *a, *b, c, count = 0;
for (a = primes_beg; a < primes_end && *a <= n / 3; a++)
for (b = a; b < primes_end && *b <= (c = n - *a - *b); b++)
if (isprime[c]) count++;
printf("count = %d\n", count);
return 0;
}
754(1): デフォルトの名無しさん [sage] 2023/06/10(土) 15:57:09.17 ID:Hla24knV(1/2) AAS
>>738 c
・>>742から若干の省メモリ化
判別用配列の要素をintからcharへ
素数の個数を数えてから一覧用領域を確保
・組み合わせループの条件を>>746さんを参考に改善
外部ﾘﾝｸ:ideone.com
>>738 c
・上記からさらに省メモリ化
判別用配列はint配列だが判別はビットごと
外部ﾘﾝｸ:ideone.com
762: 638 [sage] 2023/06/11(日) 03:01:19.54 ID:aJTqIDxz(2/2) AAS
>>761761(6): 638 [sage] 2023/06/11(日) 02:58:42.46 ID:aJTqIDxz(1/2) AAS
力ずく問題は苦手なインタプリタ―だが、速度に配慮した書き方をすればこの規模だと数分程度で解ける…
use feature qw{:5.16 signatures say};
$m = 1234567;
%h = map{$_ => ++$k} 2..$m;
for $i (2..int(sqrt $m)) {
if (exists $h{$i}) {
for ($i..(int($m / $i)+1)) { delete $h{$i * $_} }
}
}
@p = sort{$a <=> $b} keys %h;
%o = map{$p[$_] => $_} 0..$#p;
for $i (0..$#p-2) {
$p1 = $p[$i];
last if $m <= 3 * $p1;
for $j ($i+1..$#p-1) {
$p2 = $p[$j]; $s = $p1 + $p2;
$r = $m - $s; last if $r <= $p2;
$n++ if exists $o{$r};
}
}
print "n = $n\n";
実行結果 (CPUは Core-i7 8995u、Mem: 32GB)
$ time perl 21_738_prime+1234567.pl
n = 151055501
real 5m48.035s
user 5m44.468s
sys 0m3.250s
出題者の解と合わん…＞＜
アンカーしくった＞＜
>>738 Perl5
768: デフォルトの名無しさん [sage] 2023/06/12(月) 23:42:55.82 ID:y1IXQNpF(1) AAS
>>738 rust
外部ﾘﾝｸ:ideone.com
fn sieve_of_eratosthenes(n: u32) -> (Vec<bool Vec<u32>) {
if n < 2 {return (Vec::new(), Vec::new())};
let mut isprime = vec![true; 1 + n as usize];
isprime[0..2].fill(false);
(2..=(n as f64).sqrt() as usize).for_each(|i| if isprime[i] {
(i*i..=n as usize).step_by(i).for_each(|j| isprime[j] = false);
});
let primes = (2..=n).filter(|&i| isprime[i as usize]).collect();
(isprime, primes)
}
fn main() {
let n = 1234567;
let (isprime, primes) = sieve_of_eratosthenes(n);
let count = primes.iter().enumerate().take_while(|(i, &a)| a <= n / 3).map(|(i, &a)|
primes[i..].iter().take_while(|&&b| b <= (n - a) / 2).map(|&b|
isprime[(n - a - b) as usize] as u32
).sum::<u32>()
).sum::<u32>();
println!("count = {}", count);
}
770: 638 [sage] 2023/06/13(火) 00:40:44.65 ID:XM8TxFLS(1) AAS
>>738 Perl5 高速化版、>>766766(2): デフォルトの名無しさん [] 2023/06/12(月) 23:18:04.33 ID:Qrbs+YQO(1/2) AAS
>>763のプログラムの8〜11行目は以下のように書いた方がすっきりして良い。
for (i in 1:q[n %/% 3L]) {
m <- n - p[i]
k <- k + sum(isprime[m - p[i:q[m %/% 2L]]])
}
>>761のプログラムはa ≤ b ≤ cではなくa < b < cの場合の組み合わせ数を計算している。
14行目の$i+1を$iに、13行目と16行目の<=を<に変更すれば正解が得られる。
のおかげで不具合解決したし、>>761 の1/3に時間短縮できたので俺としてはこのお題これで一区切りつけたい。
$m = 1234567;
$o = '1' x $m; #substr $o, 0, 2, '00';
for $i (2..int(sqrt $m)) {
if (substr $o, $i, 1) {
for ($i..(int($m / $i)+1)) {
$j = $i * $_; last if $m <= $j; substr $o, $j, 1, '0';
}
}
}
for (2.. $m) { push @p, $_ if substr($o, $_, 1) }
for $i (0..$#p) {
$p1 = $p[0];
last if $m < 3 * $p1;
for $p2 (@p) {
$s = $p1 + $p2;
$r = $m - $s;
last if $r < $p2;
$n++ if substr $o, $r, 1;
}
shift @p;
}
print "n = $n\n";
実行結果：（CPU Core-i7 8995u）
$ time perl 21_738_prime+1234567_charVec.pl
n = 151060650
real 1m57.390s
user 1m56.375s
sys 0m0.093s
771(2): デフォルトの名無しさん [sage] 2023/06/13(火) 22:09:38.41 ID:5UrmlJw6(1) AAS
>>738 octave
・n = 1234567 でideone完走できず
外部ﾘﾝｸ:ideone.com
>>738 ruby
・n = 1234567 でideone完走できず
外部ﾘﾝｸ:ideone.com
>>738 java
外部ﾘﾝｸ:ideone.com
ちなみに現時点ではそれぞれ
C (gcc 8.3)
Rust (rust 1.56)
Octave (octave 4.4.1)
Ruby (ruby 2.5.5)
Java (HotSpot 12)
774(1): デフォルトの名無しさん [] 2023/06/14(水) 03:58:19.40 ID:uNCnaso6(1) AAS
>>738
外部ﾘﾝｸ:paiza.io
778: デフォルトの名無しさん [sage] 2023/06/14(水) 21:28:54.64 ID:i4vcABZv(1) AAS
>>738 octave
・for無しでa,b,cを算出（ただしfor版>>771より遅い）
・n = 1234567 でメモリ不足でオチる（bがクソデカサイズ）
・データの型をint32にしてみたりもしたが焼け石に水だし少し遅くもなるのでdoubleに戻した
外部ﾘﾝｸ:ideone.com
function [isprime, primes] = sieve_of_eratosthenes(n)
if n < 2; isprime = [], primes = [], return; end
isprime = [false true(1, n-1)];
for i = 2:sqrt(n)
if isprime(i); isprime(i*i:i:n) = false; end
end
primes = find(isprime);
end
n = 123456
[isprime, primes] = sieve_of_eratosthenes(n);
a = primes(primes <= n / 3)';
b = primes.*(a <= primes & primes <= (n - a) / 2);
c = (n - a - b)(b ~= 0);
count = sum(isprime(c))
788: デフォルトの名無しさん [] 2023/06/15(木) 23:56:30.25 ID:h+F4OSrU(2/2) AAS
>>787忖度して読み取ると多倍長整数の乗算の話をしているのだと思うけれど >>738 の問題を解く上ではそもそもあまり関係がない
素数になる次数の係数が 1 でそれ以外が 0 の形式的冪級数を考えてそれを3回乗算して N = 1234567 の次数の係数を求める問題に帰着させているだけ
792: デフォルトの名無しさん [] 2023/06/16(金) 09:00:10.71 ID:ly+Q1cW8(1/2) AAS
>>738
>>746 にもあるが
>>785785(2): デフォルトの名無しさん [sage] 2023/06/15(木) 22:01:30.16 ID:4JYva2qR(1/2) AAS
fftなんぞ使って早くなんかならんというに
原理わかってんの？
例えばHaskellの標準のinteger型は何万桁でも計算できる、その際fftで掛け算するので数万桁まで行ってもそこそこ早い
しかし逆に32bitで収まるような計算だと遅くなる
だから“この計算はfftなんか使わなくていいよ、int32の範囲で収まるからそれで計算してね”と専用の型がいっぱいある
Rがそれで早くなるなら素の標準計算がしょぼいとかインタプリタ特有の話
そもそも計算速度気にする場合にRを選択してる時点で筋違い
が正論
797(2): デフォルトの名無しさん [] 2023/06/16(金) 20:29:55.57 ID:2udbfubS(1/2) AAS
>>738
外部ﾘﾝｸ:paiza.io
細かいテクニックで高速化して出題者の方の解答例と同じくらいの実行時間にできた
総当たりの解法の計算量が N = 1234567 に対して O(pi(N)^2) なのに対してこの解法は O(N log N) なのできちんと書けば十分に速く動いてくれる
849: デフォルトの名無しさん [sage] 2023/06/27(火) 17:20:06.80 ID:nTtoyom2(1) AAS
>>738
C
外部ﾘﾝｸ:ideone.com
まぁスーパー亀レスなんだけど普段はHaskellerなのでなんとかHaskellで完走できないかとアレやコレやと考えてみたんだけどダメだったorz
多分競プロに出るようなスーパーHaskellerならなんとかなるのかもしれないけど諦めた、試合終了
しかしせっかく色々考えたので備忘録がわりにCに移植
やっぱりCはえー、Haskellだと1分近くかかる計算が0.5秒とか
使ったのは有限体上のFourier変換
p = 1272446977、buffer size = 524288
で計算、buffer sizeを稼ぐためにBuffer sizeが2べきでなくても使えるように組んだんだけどCならそんなもんこだわらなくても余裕の完走なので結局2^19で利用
逆フーリエ変換も不要だと後で分かったけどせっかく作ったので残してあります
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 1.476s*