[過去ﾛｸﾞ]
プログラミングのお題スレ Part21 (1002ﾚｽ)
プログラミングのお題スレ Part21 http://mevius.5ch.net/test/read.cgi/tech/1668333636/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索
歴削→次ｽﾚ
栞削→次ｽﾚ
過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制
です｡10分ほどで解除するので､
他のﾌﾞﾗｳｻﾞ
へ避難してください｡
738: デフォルトの名無しさん [] 2023/06/08(木) 22:14:54.10 ID:B/+C/EDE お題：1234567以下の素数 a, b, c で a + b + c = 1234567 かつ a ≤ b ≤ c を満たす組み合わせは何通りあるか計算せよ。 http://mevius.5ch.net/test/read.cgi/tech/1668333636/738
739: デフォルトの名無しさん [sage] 2023/06/09(金) 04:35:40.14 ID:Xuj67sW5 >>738 https://ideone.com/4YftKh 力業っぽくなったな、3で割って1余る整数計しか解けない http://mevius.5ch.net/test/read.cgi/tech/1668333636/739
742: デフォルトの名無しさん [] 2023/06/09(金) 20:08:26.01 ID:7Vf79qrZ >>738 c https://ideone.com/Dbl6mc #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; } http://mevius.5ch.net/test/read.cgi/tech/1668333636/742
754: デフォルトの名無しさん [sage] 2023/06/10(土) 15:57:09.17 ID:Hla24knV >>738 c ・>>742から若干の省メモリ化 判別用配列の要素をintからcharへ 素数の個数を数えてから一覧用領域を確保 ・組み合わせループの条件を>>746さんを参考に改善 https://ideone.com/CixK7I >>738 c ・上記からさらに省メモリ化 判別用配列はint配列だが判別はビットごと https://ideone.com/JDcFjV http://mevius.5ch.net/test/read.cgi/tech/1668333636/754
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
768: デフォルトの名無しさん [sage] 2023/06/12(月) 23:42:55.82 ID:y1IXQNpF >>738 rust https://ideone.com/THk6s8 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); } http://mevius.5ch.net/test/read.cgi/tech/1668333636/768
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
771: デフォルトの名無しさん [sage] 2023/06/13(火) 22:09:38.41 ID:5UrmlJw6 >>738 octave ・n = 1234567 でideone完走できず https://ideone.com/QzfFfY >>738 ruby ・n = 1234567 でideone完走できず https://ideone.com/OPplEt >>738 java https://ideone.com/pCHK8L ちなみに現時点ではそれぞれ C (gcc 8.3) Rust (rust 1.56) Octave (octave 4.4.1) Ruby (ruby 2.5.5) Java (HotSpot 12) http://mevius.5ch.net/test/read.cgi/tech/1668333636/771
774: デフォルトの名無しさん [] 2023/06/14(水) 03:58:19.40 ID:uNCnaso6 >>738 https://paiza.io/projects/fGIqMa8Tq4Q0FBxgaGrN7Q http://mevius.5ch.net/test/read.cgi/tech/1668333636/774
778: デフォルトの名無しさん [sage] 2023/06/14(水) 21:28:54.64 ID:i4vcABZv >>738 octave ・for無しでa,b,cを算出（ただしfor版>>771より遅い） ・n = 1234567 でメモリ不足でオチる（bがクソデカサイズ） ・データの型をint32にしてみたりもしたが焼け石に水だし少し遅くもなるのでdoubleに戻した https://ideone.com/aosEo2 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)) http://mevius.5ch.net/test/read.cgi/tech/1668333636/778
788: デフォルトの名無しさん [] 2023/06/15(木) 23:56:30.25 ID:h+F4OSrU >>787 忖度して読み取ると多倍長整数の乗算の話をしているのだと思うけれど >>738 の問題を解く上ではそもそもあまり関係がない 素数になる次数の係数が 1 でそれ以外が 0 の形式的冪級数を考えてそれを3回乗算して N = 1234567 の次数の係数を求める問題に帰着させているだけ http://mevius.5ch.net/test/read.cgi/tech/1668333636/788
792: デフォルトの名無しさん [] 2023/06/16(金) 09:00:10.71 ID:ly+Q1cW8 >>738 >>746 にもあるが >>785 が正論 http://mevius.5ch.net/test/read.cgi/tech/1668333636/792
797: デフォルトの名無しさん [] 2023/06/16(金) 20:29:55.57 ID:2udbfubS >>738 https://paiza.io/projects/0QCNbnKzWMHspiarmHa0Tw 細かいテクニックで高速化して出題者の方の解答例と同じくらいの実行時間にできた 総当たりの解法の計算量が N = 1234567 に対して O(pi(N)^2) なのに対してこの解法は O(N log N) なのできちんと書けば十分に速く動いてくれる http://mevius.5ch.net/test/read.cgi/tech/1668333636/797
849: デフォルトの名無しさん [sage] 2023/06/27(火) 17:20:06.80 ID:nTtoyom2 >>738 C https://ideone.com/JGH96u まぁスーパー亀レスなんだけど普段はHaskellerなのでなんとかHaskellで完走できないかとアレやコレやと考えてみたんだけどダメだったorz 多分競プロに出るようなスーパーHaskellerならなんとかなるのかもしれないけど諦めた、試合終了 しかしせっかく色々考えたので備忘録がわりにCに移植 やっぱりCはえー、Haskellだと1分近くかかる計算が0.5秒とか 使ったのは有限体上のFourier変換 p = 1272446977、buffer size = 524288 で計算、buffer sizeを稼ぐためにBuffer sizeが2べきでなくても使えるように組んだんだけどCならそんなもんこだわらなくても余裕の完走なので結局2^19で利用 逆フーリエ変換も不要だと後で分かったけどせっかく作ったので残してあります http://mevius.5ch.net/test/read.cgi/tech/1668333636/849
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.043s