プログラミングのお題スレ Part22 (863ﾚｽ)
上下前次1-新
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
1(4): デフォルトの名無しさん [] 2023/08/03(木)13:52 ID:/xW45k0z(1)
プログラミングのお題スレです。
【出題と回答例】
1 名前：デフォルトの名無しさん
お題：お題本文
2 名前：デフォルトの名無しさん
>>1 使用言語
回答本文
結果がある場合はそれも
【ソースコードが長くなったら】 (オンラインでコードを実行できる)
https://ideone.com/
http://codepad.org/
http://compileonline.com/
http://rextester.com/runcode
https://runnable.com/
https://code.hackerearth.com/
http://melpon.org/wandbox
https://paiza.io/
宿題は宿題スレがあるのでそちらへ。
※前スレ
プログラミングのお題スレ Part21
2chｽﾚ:tech
844: デフォルトの名無しさん [sage] 09/12(金)20:36 ID:I2wrB793(1)
>>438 scheme (chicken 4.13)
https://ideone.com/SlkO0l
・空白時にdrop-while
>>842 ruby
https://ideone.com/mY83rW
845(15): デフォルトの名無しさん [sage] 09/13(土)12:21 ID:nVmVuqdT(1)
退屈そうだからちょっと難易度高め
【問題】
各桁の数が1～5のいずれかで全ての桁の合計がMとなる正整数の集合をG[M]で表す。
例えば123、111111はG[6]の要素、255、222222はG[12]の要素となる。
整数M（1≦M≦32）、N（1≦N）が与えられたとき、N番目に小さいG[M]の要素を求めよ。
ただしNがG[M]の要素数より大きい場合の出力は0とする。
求める数値は文字列または各桁の数の配列による表現も可能とする（123⇔"123"⇔[1,2,3]）。
【例】 #入力は(M,N)
(2,1) → 2
(2,2) → 11
(2,3) → 0
(20,1) → 5555
(20,2) → 14555
(20,3) → 15455
(20,400096) → 11111111111111111111
(20,400097) → 0
(32,1) → 2555555
(32,2) → 3455555
(32,3) → 3545555
(32,1000) → 34355354
(32,1000000) → 11532334334
(32,1000000000) → 2141111311212411131
(32,1333610936) → 11111111111111111111111111111111
(32,1333610937) → 0
【ヒント(?)】
G[M]の要素数の数列は下記pentanacci数列a[n]から先頭の[0,0,0,0,1]を除いたものとなる（|G[M]| = a[M + 4]）。
・a[0,1,2,3,4] = [0,0,0,0,1]
・a[k] = a[k-1] + a[k-2] + a[k-3] + a[k-4] + a[k-5] (k≧5）
※a[37]までのリスト： https://oeis.org/A001591/list
846(1): デフォルトの名無しさん [] 09/13(土)21:09 ID:rhMflYHg(1)
>>845
R
https://ideone.com/R7chTY
ヒントはどう使うのかわからなかった。
847: デフォルトの名無しさん [] 09/14(日)02:07 ID:K9dbpWus(1)
>>845 c++
https://ideone.com/ezHz45
先越された
848(1): デフォルトの名無しさん [sage] 09/14(日)02:17 ID:ymjVQadn(1)
>>845 ruby
https://ideone.com/wrV2zh
・なんとなく動いてる版
・チマチマと次を探して行く
・G[20]まで出すのがやっと(4.05s)
849(2): デフォルトの名無しさん [] 09/14(日)21:00 ID:Yva1i9w5(1/2)
>>845
R
https://ideone.com/XhdJw4
>>846より行列計算が速くなった。変数名mとnが逆だったのを直した。
C++に移植
https://ideone.com/9dibE0
850(1): デフォルトの名無しさん [] 09/14(日)22:50 ID:Yva1i9w5(2/2)
>>845
Fortranに移植
https://ideone.com/CnJ0S9
行列計算を短く書けて、しかも実行が速い。
851(2): 848 [sage] 09/15(月)00:34 ID:aTaxsjKO(1/2)
>>845 ruby
https://ideone.com/3I72I6
・キャッシュ探りながら構築
・c[桁の合計][幅] = とりうるパターン
852(1): 851 [sage] 09/15(月)00:58 ID:aTaxsjKO(2/2)
https://ideone.com/GWbQAx
・動きは >>851 といっしょ
・若干の整理
853: デフォルトの名無しさん [] 09/15(月)22:27 ID:g8zilsSB(1)
>>850では行末に無駄な半角空白文字が出力される。消すには最後から3行目のnthPartition(m, n)を
trim( )で囲めば良い。
854(1): 852 [sage] 09/16(火)01:02 ID:3CKXdG+H(1)
>>845 ruby
https://ideone.com/n5Jqm3
・動きは >>851 といっしょ
・数値の内部表現を配列から整数へ変更
855(1): 854 [sage] 09/17(水)22:30 ID:U8XLHdaR(1)
>>845 ruby 2.5.5
https://ideone.com/oAQimi
・とりうるパターン数に着目し迫る
・tallyは2.7以降
856(1): デフォルトの名無しさん [] 09/17(水)22:43 ID:RlLGu0ST(1/2)
>>845
C++
https://ideone.com/I6K1tl
行列Aの計算で加減算・代入回数を>>849より減らした。実行時間の違いは分からなかった。
857: デフォルトの名無しさん [] 09/17(水)23:39 ID:RlLGu0ST(2/2)
>>856
BigInt化してm = 2000, n = 2¹⁰²⁴で実行したら違いが明確になった。
(1) >>849のBigInt版
https://ideone.com/S92L9G
(2) >>856のBigInt版
https://ideone.com/3x03xT
加減算・代入回数を削減した(2)の方が確かに速く、(1)の約4分の3の実行時間。
858(1): 855 [sage] 09/18(木)21:13 ID:mk4sIpUK(1)
>>845 ruby 2.5.5
https://ideone.com/Zm2433
・揃ってからcumsum、のリズムを廃止
859(1): 858 [sage] 09/19(金)21:59 ID:e72KvXSi(1)
>>845 ruby 2.5.5
https://ideone.com/iwQNCH
・若干の整理（loop廃止、fill三回へ置き換え）
860(1): 859 [sage] 09/20(土)21:39 ID:zrmIrXrK(1)
>>845 ruby 2.5.5
https://ideone.com/jHqv2L
・内部表現の変更
112225→[2,3,0,0,1]
861(1): 860 [sage] 09/22(月)21:37 ID:9W7EeSnZ(1)
>>845 ruby 2.5.5
https://ideone.com/MDHX6v
・内部表現のさらなる変更
・パターン数を直接キャッシュするようにした
cc[合計][幅] = とりうるパターン数
>>845 ruby
https://ideone.com/PB8S7w
・m = 2000, n = 1 << 1024
862(1): 861 [sage] 09/23(火)01:13 ID:XS9iE/WB(1)
>>845 c++
https://ideone.com/oma0Jf
・ruby版861の移植
・m = 2000, n = 1 << 1024
863: 862 [sage] 09/26(金)21:58 ID:rAOVnJgT(1)
>>845 ruby
https://ideone.com/YEGl7C
・実りの無い再帰を省略
・結果を配列で集めず整数で集める
>>845 c++
https://ideone.com/f62fkG
・rubyの移植版
>>845 ocaml
https://ideone.com/cHYmdv
・rubyの移植版
・任意精度整数は昔ながらのnumのBig_int使用
・ZarithのZは確かに速かったけどideoneでは使えずボツ
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.026s