[過去ﾛｸﾞ] プログラミングのお題スレ Part16 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
498: 2019/12/30(月)19:31 ID:fFRqMrLq(10/13) AAS
>>462
そういえばこの問題って.NETのLINQとかJavaのStreamとか
使ってソートすればたぶんヒープが使われて逐次処理が行われるんで
全部の値をソートせずに答えが求められるんじゃないかと思った
ほぼ線形探索
499: 2019/12/30(月)19:34 ID:2F+fuXCx(2/3) AAS
>>486
数列が重複要素可で、>>495の条件で求めるなら、>>496のdの右辺をunique()で囲めば良い。
500(1): 2019/12/30(月)19:38 ID:JZjS6BbQ(3/8) AAS
>>495
アルゴリズム的にはどっちもかわらん
特定の言語で記述しにくいってことはあるかもしれないけど
501: 2019/12/30(月)19:39 ID:fFRqMrLq(11/13) AAS
>>500
マジですか・・・
502: 2019/12/30(月)20:14 ID:2F+fuXCx(3/3) AAS
>>484
Rのマニュアルを調べたら確かにそういう仕様だね。sort関数のmethod引数で
ソート方式を指定できるが、省略時は2^31要素未満の数値ベクトルに対しては
基数ソート、それ以外に対してはシェルソートが選択されると書かれている。
ということで、method引数を明示的に指定して実行時間を比較してみると、
基数、クイック、シェルソートがそれぞれ50.8, 45.2, 38.2ミリ秒で、基数ソートが
何故か一番遅いな。PCで実行したら基数<クイック<シェルの順だったのに。
RのクイックソートでもC++ STLのsortよりはまだ速い。外部ﾘﾝｸ:ideone.com
二分探索をCで書けば爆速で、実行時間は0.042マイクロ秒。Rの二分探索と3桁違う。
(キャッシュの影響があるのかも知れないが)。外部ﾘﾝｸ:ideone.com
省3
503: 2019/12/30(月)20:30 ID:0ybHI6rZ(1/2) AAS
>>492
重複なしなら
縦の数列をハッシュテーブルに入れる
横の数値に対して...
・0 ならスキップ
・面積を横の数値で割った余りが０でないならスキップ
・面積を横の数値で割った値がハッシュテーブルになければスキップ
・カウントアップ
を繰り返せばいいだけだからO(n)
（要するに>>496なんだけど）
省1
504(1): 2019/12/30(月)20:46 ID:JZjS6BbQ(4/8) AAS
ハッシュテーブルの検索はオーダー1じゃないと思うんだ
505: 2019/12/30(月)21:43 ID:0ybHI6rZ(2/2) AAS
>>504
実装とかによるけど大抵の実装だとほぼO(1)だよ
506(1): 2019/12/30(月)22:39 ID:JZjS6BbQ(5/8) AAS
ほぼ1ってなんだよwww
オーダー1の実装だと
値の範囲という別のオーダーが生まれる
507: 2019/12/30(月)22:44 ID:fFRqMrLq(12/13) AAS
>>506
平均のことかと
508: 2019/12/30(月)22:53 ID:JZjS6BbQ(6/8) AAS
ああ平均か
最悪値は非常に悪いよね
509: 2019/12/30(月)22:55 ID:JZjS6BbQ(7/8) AAS
てっきり超巨大ハッシュテーブルを作るのかと思った
510: 2019/12/30(月)22:58 ID:fFRqMrLq(13/13) AAS
たしかにハッシュテーブルの最悪の計算量はO(n)だけれども
そうなることってマレだよ
むかしVBで使われてたScripting.Dictionaryはテーブルサイズが1万固定のようで
それ以上になると計算コストがバク上がりしてた
最近のライブラリだとテーブルサイズが可変になってるので問題ない
あとはWebサービスに対する攻撃としてキーが衝突するデータを大量に送りつけるってのが
数年前に話題になったかな
ハッシュ関数を予測してデータを作為的に作らない限り最悪の計算コストになることはないかと
ハッシュテーブル使うときはO(1)で考えて良いと思う
511: 2019/12/30(月)23:12 ID:p3QJuMJ/(1) AAS
Ruby のハッシュでは、データ数と共に、バケット数を増やしていく。
バケット数は、2 の累乗の次に現れる素数。
2^n + a, 2 <= n <= 30
8 + 3 = 11
16 + 3 = 19
32 + 5 = 37
64 + 3 = 67
128 + 3 = 131
256 + 27 = 283
512 + 9 = 521
省4
512: 2019/12/30(月)23:30 ID:JZjS6BbQ(8/8) AAS
最近は結構インテリジェントに作られてるんだね
unordered_set/map もたまには使ってみようかな
513(1): 2019/12/31(火)07:26 ID:kRQlhKMg(1) AAS
制約論理型言語だと変数の上限下限を自動的に切ってくれる。
514(6): 2019/12/31(火)09:03 ID:hkax3Wzu(1) AAS
お題
フィボナッチ数列のn番目をF(n)とした時
F(F(80))の下位8桁を求めよ
フィボナッチ数列は以下で定義される数列である
F(1)=1
F(2)=1
F(n)=F(n-2)+F(n-1)
515(2): 2019/12/31(火)10:24 ID:NKLtpqnc(1/2) AAS
>>514
21055810
あってるかな。
フィボナッチ数列は行列を使うアルゴリズムでO(log n)で計算できるもんね。外側の計算はmod100000000 で計算すればいい。
516(1): 2019/12/31(火)12:24 ID:5aZymNkm(1/3) AAS
>>515
Rは整数が32ビットまでで桁あふれするから、Juliaで書く。
F = Int64[1 1; 1 0]
n = (F ^ 80)[1, 2]
P = Int64[1 0; 0 1]
R = F
while n > 0
global r = n % 2
global n = div(n, 2)
if r > 0
省7
517: 2019/12/31(火)12:26 ID:5aZymNkm(2/3) AAS
>>515じゃなくて>>514だった。
518: 2019/12/31(火)13:18 ID:5aZymNkm(3/3) AAS
>>514
Rでも多桁計算パッケージgmpを使ったら、正しく計算できた。
外部ﾘﾝｸ:ideone.com
519: 2019/12/31(火)17:23 ID:NKLtpqnc(2/2) AAS
>>514
>>516
515です。コード上げてなかった。
外部ﾘﾝｸ:ideone.com
520: 513 2019/12/31(火)18:46 ID:H+c+1UtF(1/2) AAS
>>513
64ビットに収まるようにしたので簡単でしたかね
C++
外部ﾘﾝｸ:ideone.com
521: 2019/12/31(火)18:47 ID:H+c+1UtF(2/2) AAS
>>514でした
すみません
522(1): 2019/12/31(火)19:45 ID:5fWgt8Ro(1/2) AAS
>>449
外部ﾘﾝｸ:ideone.com
C++。問題勘違いして全探索かいたんだよ〜。
おわらねー。Orz
523(2): 2019/12/31(火)20:25 ID:W8YPZd1D(1) AAS
>>522
100億人に2020になる素数をプレゼント出来そうだ。
524: 2019/12/31(火)20:58 ID:5fWgt8Ro(2/2) AAS
>>523
100億！！？？？マジで？？
そら手に余るわ。教えてくれてありがとう。
プレゼントするときは、「あなたに特別な2020を！」って感じか。
525: 2020/01/01(水)07:48 ID:W9Zu1XGU(1) AAS
>>523
素数2個の2020は41人しかあげられない。
526: 【さん吉】 2020/01/01(水)12:10 ID:WIYGoppO(1/2) AAS
あけおめ
527(1): 2020/01/01(水)12:56 ID:WIYGoppO(2/2) AAS
お題
a^n + b^n + c^n = 2020
の整数解のうちnが最大の物を求めよ
528: 【大吉】 2020/01/01(水)15:06 ID:/JBKhr80(1) AAS
あけおめ〜
529: 2020/01/01(水)15:29 ID:qVK/11PV(1) AAS
A HAPPY NEW YEAR !!!
というコード。
530: 2020/01/02(木)04:45 ID:cCzcmPOa(1) AAS
>>451
531: 2020/01/02(木)14:00 ID:2eGsq/cP(1) AAS
(´；ω；｀)
532(5): 2020/01/03(金)03:43 ID:ct9N0pK8(1/2) AAS
お題
a^3 + b^3 + c^3 = 2020 * 2
の整数解を求めよ。
533(4): 2020/01/03(金)03:49 ID:ct9N0pK8(2/2) AAS
追加
a^3 + b^3 + c^3 = 2020 / 2･2
の整数解を求めよ。
534: 2020/01/03(金)03:54 ID:pVliia9g(1/3) AAS
>>486
Kotlin
外部ﾘﾝｸ:paiza.io
こんなので良いの？単に掛け算して一致するか比較しているだけなんだけど。
オマケとして重複しないようにはしているが。
535: 2020/01/03(金)04:17 ID:pVliia9g(2/3) AAS
>>532
C
外部ﾘﾝｸ:paiza.io
どう?
536(1): 2020/01/03(金)04:18 ID:pVliia9g(3/3) AAS
>>533
最後の 2･2 の部分って何? 2.2? こっちで文字化けしてちゃんと表示されてないだけ?
537: 2020/01/03(金)09:45 ID:+RiBlMC+(1) AAS
>>536
2020 / 2･2 = 2020 / 2 * 2 = 2020
538: 2020/01/03(金)12:48 ID:3k7MKqlh(1/3) AAS
>>532
200万以下だと38通り
(並び替えも数えるとその6倍)
>>533
2020は解無し
1010は100万までには解は無い
505は100万までに18個
539: 2020/01/03(金)12:51 ID:3k7MKqlh(2/3) AAS
>>527
n乗して64bitの範囲だとn=2しか発見出来なかった
540(2): 2020/01/03(金)20:05 ID:3k7MKqlh(3/3) AAS
>>532
C
外部ﾘﾝｸ:ideone.com
38個見つけるのに1時間くらいかかりました
38個目 (1661082, 440694, -1671358)
こういうのはC/C++が得意でしょう
他の言語で出来ます？ (挑戦)
541(1): 2020/01/04(土)17:22 ID:HJ66bOYq(1/2) AAS
お題
>>514に関連して、F(F(80))の桁数を求めよ。
計算式は簡単だが…
542(1): 2020/01/04(土)17:47 ID:6lKY6ugm(1) AAS
over flow周りはあってるんだかわからん
画像ﾘﾝｸ[png]:i.imgur.com
543: 2020/01/04(土)19:01 ID:hAlxX0tq(1) AAS
Mathematica ?
544(12): 2020/01/04(土)20:28 ID:rMjoeVI8(1/2) AAS
お題: 文字列を逆順にしてコピーするreverse関数を定義せよ（既存のライブラリを使ってはならない）
545: 2020/01/04(土)20:40 ID:YRTK1M0u(1) AAS
>>544 Ruby
puts 'ABCDEF'.chars.then{|a| a.size.times.map{a.pop}}.join
# => FEDCBA
546(1): 2020/01/04(土)20:46 ID:HJ66bOYq(2/2) AAS
>>544 PowerShell
function reverse($s) {-join $s[-1..-$s.length]}
reverse 文字列を逆順にしてコピーするreverse関数を定義せよ
-- 実行結果 --
よせ義定を数関esreverるすーピコてしに順逆を列字文
547: 2020/01/04(土)21:12 ID:AqMdau2S(1) AAS
>>544 Ruby
def reverse( s ); s.chars.inject(:prepend); end
548: 2020/01/04(土)21:13 ID:rMjoeVI8(2/2) AAS
>>544 C
外部ﾘﾝｸ:ideone.com
549: 2020/01/04(土)21:26 ID:e7dEja3I(1) AAS
>>544
Java
外部ﾘﾝｸ:paiza.io
550: 2020/01/05(日)00:51 ID:Y4p4/H36(1) AAS
>>544
Kotlin
外部ﾘﾝｸ:paiza.io
Kotlin の String には reversed() という文字列順序逆転のための拡張関数が最初からあって紛らわしいので rev() という名前で自作した。
551: 2020/01/05(日)08:25 ID:h+ccWvVu(1/3) AAS
>>532
{a, b, c} = {-12, -4, 18} {-4, 2, 16} など
>>533
{a, b, c} = {-6, -2, 9} {-2, 1, 8} など
552: 2020/01/05(日)08:35 ID:OU8kozEP(1) AAS
>>544 Ruby
def rev(s)
(1..s.size).map{|i|s[-i]}.join
end
553: 2020/01/05(日)11:04 ID:Z8HxF2cT(1) AAS
>>544 Common Lisp
外部ﾘﾝｸ:ideone.com
外部ﾘﾝｸ:ideone.com
554: 2020/01/05(日)15:25 ID:+tGOF19X(1) AAS
>>544 Python
def reverse(s):
return s[::-1]
555(1): 2020/01/05(日)16:01 ID:8nvrboOv(1) AAS
>>540
こういうのを見ると我々は離散数学についてはほぼ無力と思う。
556: 2020/01/05(日)17:02 ID:x729cdax(1) AAS
>>555
勉強しとけ
557: 2020/01/05(日)21:49 ID:2Fq0AHrI(1/4) AAS
>>544 R
外部ﾘﾝｸ:ideone.com
>>546のPowerShellと違って、U+10000以上の文字が含まれていても正しく逆順にできる。
558: 2020/01/05(日)21:52 ID:2Fq0AHrI(2/4) AAS
>>542
仮数部も指数部も間違っている。整数で1の位まで正確に求められるよ。
559: 2020/01/05(日)22:31 ID:h+ccWvVu(2/3) AAS
>>540 ｻﾝｸｽ
>>532 の解
{13, 11, 8}
{15, 9, -4}
{8, 1, -2} * 2
{9, -2, -6} * 2
{16, -6, -15} * 2
{74, -23, -73}
{43, -27, -39} * 2
{171, -75, -166}
省18
560: 2020/01/05(日)22:41 ID:h+ccWvVu(3/3) AAS
>>533 の解
{8, 1, -2}
{9, -2, -6}
{16, -6, -15}
{43, -27, -39}
{169, 64, -172}
{414, 385, -504}
{530, 337, -572}
{2673, 1114, -2736}
{10102, 674, -10103}
省3
561: 2020/01/05(日)22:48 ID:bLPoA6E7(1/2) AAS
>>541
C++
外部ﾘﾝｸ:ideone.com.VJk9QA
倍精度だと微妙に精度が足りないので
擬似4倍精度で計算してみた
4倍精度や多倍長が使える言語やライブラリを使えば一瞬で書けるんだけど
562(2): 2020/01/05(日)22:49 ID:bLPoA6E7(2/2) AAS
↑
外部ﾘﾝｸ:ideone.com
でした
563: 2020/01/05(日)23:29 ID:2Fq0AHrI(3/4) AAS
>>562
正解。
Rには多倍長浮動小数点パッケージRmpfrがあるので、120ビット精度での計算をさっと書ける。
多倍長整数パッケージgmpにはフィボナッチ数列の第n項を求める関数があるので、第80項を
自分で求める必要すらない。
外部ﾘﾝｸ:ideone.com
C/C++にもlong double型があるので楽勝!と思っていると罠に嵌まる。Visual C++では
long doubleは移植性（単にコンパイルが通るという意味で）のために定義されているだけで、
double精度しかないので使えない。GNU C++ではlong doubleが本当のlong doubleなので使える。
外部ﾘﾝｸ:ideone.com
省2
564: 2020/01/05(日)23:41 ID:2Fq0AHrI(4/4) AAS
GNU C++にも罠があって、外部ﾘﾝｸ:ideone.com はideoneでは結果が正しく
表示されているが、Windows版でコンパイルすると「-0桁」になってしまう。
printfの%Lf書式指定子が何故か正常に機能しないようなので、long longに変換して
%lld書式指定子を使う必要がある。
565: 2020/01/05(日)23:58 ID:Z3Lsb/Mg(1) AAS
>>562は擬似4倍精度の四則演算やルートがコンパクトにまとまっており参考になるかと思います
logは手抜きですが
566(1): 2020/01/06(月)00:24 ID:MKFPBGLf(1) AAS
x87の80bit形式久々に聞いた
intelの失敗仕様
本当のlong doubleって言ったら128bitの事だと思う
567: 2020/01/07(火)12:16 ID:lAASQTDH(1) AAS
本当の？
568: 2020/01/07(火)13:02 ID:PuPIfAOU(1/2) AAS
大きさと精度が一致しないということでは。
例えば、16ビット整数の加算において255+1で桁あふれが発生するのは、勘弁してほしい。
16ビット整数であれば精度も16ビットあってほしい。
569(1): 2020/01/07(火)13:13 ID:4oL1Xwrc(1) AAS
intelの拡張小数は箱も中身も80bitだぞ
隠れた1bitも隠さないから中身は79bitとも言えるかもしれないけど
570: 2020/01/07(火)13:43 ID:PuPIfAOU(2/2) AAS
GCCのlong doubleは128ビットあるから。
571(1): 2020/01/07(火)22:24 ID:Y9qs9jpB(1/3) AAS
ひさびさにx87命令を使ってみた
masm形式なのでideoneでは動作しませんが
外部ﾘﾝｸ:ideone.com
572: 2020/01/07(火)22:38 ID:Y9qs9jpB(2/3) AAS
↑の出力結果
4893806799921043 (4893806799921042 + 0.855469)
丸める前の正確な値は
4893806799921042.8564973677594677....
なので小数第二位まで合っています
80bitでもギリギリって感じ
2進数だと
上位62bitまで正確、下位2bitが計算誤差
ということになります
573: 2020/01/07(火)23:09 ID:Y9qs9jpB(3/3) AAS
外部ﾘﾝｸ[htm]:pc.watch.impress.co.jp
574(1): 2020/01/08(水)17:55 ID:E2HYW9Z+(1/2) AAS
お題
フィボナッチ数列のn番目をF(n)とした時
F(F(F(80)))の下位4桁を求めよ
フィボナッチ数列は以下で定義される数列である
F(1)=1
F(2)=1
F(n)=F(n-2)+F(n-1)
575: 2020/01/08(水)18:47 ID:bVQLyL/p(1) AAS
フィフィフィボナッチ数列はお腹いっぱい
576: ◆QZaw55cn4c 2020/01/08(水)19:48 ID:npJkZznC(1) AAS
>>571
x87 すごくいいです！私も 9801FA に i487SX をようやく搭載して準備完了です！
577: 2020/01/08(水)20:00 ID:naqRCa+g(1) AAS
お前は昭和何年からタイムスリップしてきたんだ
578: 2020/01/08(水)20:33 ID:DEoUiUkq(1) AAS
>>574
R
外部ﾘﾝｸ:ideone.com
579: 2020/01/08(水)21:16 ID:E2HYW9Z+(2/2) AAS
正解
C++
外部ﾘﾝｸ:ideone.com
580: 2020/01/08(水)23:38 ID:3Vg9kR1l(1) AAS
>>544 Perl5
use feature qw{say signatures};
sub reverse($s) {
map {substr $s, -$_, 1} 1..length $s;
}
say &reverse('reverse');
581(6): 2020/01/10(金)10:41 ID:lJ/gG0sx(1/3) AAS
お題：自分用expm1()的なもの。底はe以外でも良い。不正な引数でのエラー処理は
考慮しなくても良い。
582(1): 2020/01/10(金)13:20 ID:KXQq2+DU(1) AAS
目的が高精度なのかSIMDなのか単に出題者が勉強したいだけなのか
もしかしてx87命令を使わせたい？
583(1): 2020/01/10(金)20:53 ID:1usNcOvE(1) AAS
>>581
expm1()って何？
584: [age] 2020/01/10(金)21:01 ID:jjOShzcG(1) AAS
エキスペディション・マグニチュードワンのことやろな
585: 581 2020/01/10(金)22:06 ID:lJ/gG0sx(2/3) AAS
>>582
SIMDやx87命令は考えてませんでした。
四則演算とexpm1()以外のライブラリ関数は使用可って事で。
やっぱし無難にテイラー展開で求めるのが楽？
>>583
例えば
外部ﾘﾝｸ[html]:linuxjm.osdn.jp
586(1): 2020/01/10(金)22:10 ID:lApN4p1F(1) AAS
四則演算も使ったらダメなのかい
587: 581 2020/01/10(金)22:42 ID:lJ/gG0sx(3/3) AAS
>>586
訂正：
四則演算と、「expm1()以外の」ライブラリ関数は使用可
588: 2020/01/11(土)06:32 ID:wIXPHQcF(1) AAS
出題者が方法を知りたいだけだよね？
なら質問スレ/宿題スレの方が適切
589(4): 2020/01/11(土)09:22 ID:R1f0qLP3(1) AAS
お題
素数番目の素数をスーパー素数と言う。
スーパー素数の最初の100個を求める。
590: 2020/01/11(土)10:27 ID:LQrvWU7L(1/2) AAS
>>589 Ruby 2.7.0
require 'Prime'
p Prime.take(100).then{|p| Prime.take(p.last).select.with_index{p.include?(-~_2)}}
# => [3, 5, 7, [中略], 3761, 3911]
591: 2020/01/11(土)10:31 ID:LQrvWU7L(2/2) AAS
typo
# => [3, 5, 11, 17, 31, [中略], 3733, 3761, 3911]
592(1): 2020/01/11(土)10:52 ID:VG9fEjGe(1) AAS
お題
5の倍数の素数を5の倍数素数という
5の倍数素数を全て求めよ
593: 2020/01/11(土)11:10 ID:V+Dyph4l(1) AAS
5の倍数の素数ってどういうことですか？
文字通りの意味なら5だけだと思うんですけど
594(1): 2020/01/11(土)13:10 ID:JM9/51Sk(1/2) AAS
>>544 Perl4
use feature qw{say signatures};
sub rev($s) {
$s ne '' and substr ($s, -1, 1, '') . rev($s)
}
say rev('string');
てす
595(1): 2020/01/11(土)13:14 ID:JM9/51Sk(2/2) AAS
>>594 Perl5 だった…orz
しかし、このソースの「substr (」のrと(の間のスペース文字を省くと
スレへの書き込みで
HTTP/1.1 403 Forbidden
が起きて書き込めなかったのは謎…
596: 2020/01/11(土)14:01 ID:M68szGrA(1) AAS
>>592
echo 5
597(1): 2020/01/11(土)20:08 ID:go77StkR(1) AAS
お題
20200111の階乗を素因数分解したとき、すべての因数の積は20200111の階乗だが、
すべての因数の和は何か。
上下前次1-新書関写板覧索設栞歴
あと 405 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.322s*