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