[過去ﾛｸﾞ] プログラミングのお題スレ Part21 (1002ﾚｽ)

プログラミングのお題スレ Part21 http://mevius.5ch.net/test/read.cgi/tech/1668333636/

上下前次1-新
通常表示 512ﾊﾞｲﾄ分割 ﾚｽ栞
抽出解除 ﾚｽ栞

---

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ

---

761: 638 [sage] 2023/06/11(日) 02:58:42.46 ID:aJTqIDxz 力ずく問題は苦手なインタプリタ―だが、速度に配慮した書き方をすればこの規模だと数分程度で解ける… 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 出題者の解と合わん…＞＜ http://mevius.5ch.net/test/read.cgi/tech/1668333636/761

762: 638 [sage] 2023/06/11(日) 03:01:19.54 ID:aJTqIDxz >>761 アンカーしくった＞＜ >>738 Perl5 http://mevius.5ch.net/test/read.cgi/tech/1668333636/762

763: デフォルトの名無しさん [] 2023/06/11(日) 20:59:06.26 ID:MUXJWS2B >>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 = "") http://mevius.5ch.net/test/read.cgi/tech/1668333636/763

764: 638 [sage] 2023/06/11(日) 22:49:44.46 ID:7781B+HK >>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のコード短いな…も一回勉強してみようかな http://mevius.5ch.net/test/read.cgi/tech/1668333636/764

766: デフォルトの名無しさん [] 2023/06/12(月) 23:18:04.33 ID:Qrbs+YQO >>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行目の<=を<に変更すれば正解が得られる。 http://mevius.5ch.net/test/read.cgi/tech/1668333636/766

767: デフォルトの名無しさん [] 2023/06/12(月) 23:18:28.27 ID:Qrbs+YQO 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}通り" http://mevius.5ch.net/test/read.cgi/tech/1668333636/767

770: 638 [sage] 2023/06/13(火) 00:40:44.65 ID:XM8TxFLS >>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 http://mevius.5ch.net/test/read.cgi/tech/1668333636/770

---

ﾒﾓ帳

(0/65535文字)

---

上下前次1-新書関写板覧索設栞歴

---

ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

Google検索

Wikipedia

---

ぬこの手 ぬこTOP 0.037s