[過去ﾛｸﾞ]
プログラミングのお題スレ Part21 (1002ﾚｽ)
プログラミングのお題スレ Part21 http://mevius.5ch.net/test/read.cgi/tech/1668333636/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索
歴削→次ｽﾚ
栞削→次ｽﾚ
過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制
です｡10分ほどで解除するので､
他のﾌﾞﾗｳｻﾞ
へ避難してください｡
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
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.047s