プログラミングのお題スレ Part22 (858ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
845(10): デフォルトの名無しさん [sage] 2025/09/13(土) 12:21:51.23 ID:nVmVuqdT(1) AAS
退屈そうだからちょっと難易度高め
【問題】
各桁の数が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]までのリスト： 外部ﾘﾝｸ:oeis.org
846(1): デフォルトの名無しさん [] 2025/09/13(土) 21:09:19.41 ID:rhMflYHg(1) AAS
>>845
R
外部ﾘﾝｸ:ideone.com
ヒントはどう使うのかわからなかった。
847: デフォルトの名無しさん [] 2025/09/14(日) 02:07:05.25 ID:K9dbpWus(1) AAS
>>845 c++
外部ﾘﾝｸ:ideone.com
先越された
848(1): デフォルトの名無しさん [sage] 2025/09/14(日) 02:17:37.66 ID:ymjVQadn(1) AAS
>>845 ruby
外部ﾘﾝｸ:ideone.com
・なんとなく動いてる版
・チマチマと次を探して行く
・G[20]まで出すのがやっと(4.05s)
849(2): デフォルトの名無しさん [] 2025/09/14(日) 21:00:58.83 ID:Yva1i9w5(1/2) AAS
>>845
R
外部ﾘﾝｸ:ideone.com
>>846より行列計算が速くなった。変数名mとnが逆だったのを直した。
C++に移植
外部ﾘﾝｸ:ideone.com
850(1): デフォルトの名無しさん [] 2025/09/14(日) 22:50:48.82 ID:Yva1i9w5(2/2) AAS
>>845
Fortranに移植
外部ﾘﾝｸ:ideone.com
行列計算を短く書けて、しかも実行が速い。
851(2): 848 [sage] 2025/09/15(月) 00:34:43.20 ID:aTaxsjKO(1/2) AAS
>>845 ruby
外部ﾘﾝｸ:ideone.com
・キャッシュ探りながら構築
・c[桁の合計][幅] = とりうるパターン
854(1): 852 [sage] 2025/09/16(火) 01:02:30.84 ID:3CKXdG+H(1) AAS
>>845 ruby
外部ﾘﾝｸ:ideone.com
・動きは >>851 といっしょ
・数値の内部表現を配列から整数へ変更
855(1): 854 [sage] 2025/09/17(水) 22:30:29.22 ID:U8XLHdaR(1) AAS
>>845 ruby 2.5.5
外部ﾘﾝｸ:ideone.com
・とりうるパターン数に着目し迫る
・tallyは2.7以降
856(1): デフォルトの名無しさん [] 2025/09/17(水) 22:43:48.03 ID:RlLGu0ST(1/2) AAS
>>845
C++
外部ﾘﾝｸ:ideone.com
行列Aの計算で加減算・代入回数を>>849より減らした。実行時間の違いは分からなかった。
858: 855 [sage] 2025/09/18(木) 21:13:33.56 ID:mk4sIpUK(1) AAS
>>845 ruby 2.5.5
外部ﾘﾝｸ:ideone.com
・揃ってからcumsum、のリズムを廃止
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.048s