[過去ﾛｸﾞ] プログラミングのお題スレ Part21 (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
761(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
出題者の解と合わん…＞＜
762: 638 [sage] 2023/06/11(日) 03:01:19.54 ID:aJTqIDxz(2/2) AAS
>>761 アンカーしくった＞＜
>>738738(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 を満たす組み合わせは何通りあるか計算せよ。
Perl5
763(2): デフォルトの名無しさん [] 2023/06/11(日) 20:59:06.26 ID:MUXJWS2B(2/2) AAS
>>761
インタプリタでもRだともっと速い。以下のプログラムを https: //tio.run で実行すると
9.96秒で完了し、解は>>746の151060650通りと合う。>>761は制限時間 (1分) 以内に
完了しない。Rは自前のループをなるべく書かずにベクトル演算にすれば割と速い。
n <- 1234567L
isprime <- c(FALSE, rep(TRUE, n - 1))
for (i in 2:sqrt(n)) if (isprime[i]) isprime[seq(i + i, n, i)] <- FALSE
p <- which(isprime)
q <- cumsum(isprime)
k <- 0L
for (i in p[1:q[n %/% 3L]]) {
m <- n - i
k <- k + sum(isprime[m - p[q[i]:q[m %/% 2L]]])
}
cat(k, "通り\n", sep = "")
764: 638 [sage] 2023/06/11(日) 22:49:44.46 ID:7781B+HK(1) AAS
>>763
Perlの（多分Pythoも,Rubyはｼﾗﾈ）配列はリストなのでインデックスで回すとリンク辿りをloopで繰り返し
こういったコードでは遅さに拍車をかけていると思う。あとhashを多用するのもペナルティーがあると思う。
配列の代わりにBit Vectorが使える場面ではそれにより改善できる可能性がある
たとえば序盤のエラトステネスの篩で素数求めるloopについては>>761のコードだと5.2秒くらいなんだけれど
長い文字列をVectorとし、個々の文字をflag要素とみなし、
use feature qw{say};
$m = 1234567;
$o = '1' x $m;
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) {
$n++ if substr($o, $_, 1);
}
print "$n\n";
と書くと0.3秒くらいに短縮される。ただし5分のうち5秒なので焼け石に…
しかしこの方法は151060650通りを求める後半のループにはうまく効かない。
つかそれ以前に解が合ってない。多分俺が勘違いしてバグ仕込んだと思う。
しかしRのコード短いな…も一回勉強してみようかな
766(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行目の<=を<に変更すれば正解が得られる。
767(1): デフォルトの名無しさん [] 2023/06/12(月) 23:18:28.27 ID:Qrbs+YQO(2/2) AAS
PowerShell 7は前のバージョンよりは速くなっていて、以下のプログラムは>>761の
3分の1ほどの時間で実行できた。
$n = 1234567
$isprime = @($false) * 2 + @($true) * ($n - 1)
foreach ($i in 2..[Math]::sqrt($n)) {
if ($isprime[$i]) {for ($j = $i + $i; $j -le $n; $j += $i) {$isprime[$j] = $false}}
}
$j = 0
$p = $q = @(0) * ($n + 1)
foreach ($i in 2..$n) {
if ($isprime[$i]) {$p[$j++] = $i}
$q[$i] = $j - 1
}
$k = 0
foreach ($i in 0..$q[$n / 3]) {
$m = $n - $p[$i]
foreach ($j in $i..$q[$m / 2]) {
if ($isprime[$m - $p[$j]]) {$k++}
}
}
"${k}通り"
770: 638 [sage] 2023/06/13(火) 00:40:44.65 ID:XM8TxFLS(1) AAS
>>738 Perl5 高速化版、>>766のおかげで不具合解決したし、>>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
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.059s