304(6): デフォルトの名無しさん [sage] 2024/03/09(土) 22:47:01.30 ID:v99WCN19(1) AAS
お題

460円 580円 600円 の3種類の商品があります
これらを組み合わせて合計10個買ったら5360円になりました
組み合わせを求めるプログラムを書いてください

ちなみに答えの一つは
・600円×2
・580円×4
・460円×4
だそうです

2chｽﾚ:cigaret

301(3): デフォルトの名無しさん [] 2024/03/06(水) 22:35:52.23 ID:lIZep5aT(1) AAS
>>282
C++
外部ﾘﾝｸ:ideone.com
>>300の実行時間を分析すると、最も時間が掛かっているのは46〜と47行目だと判明した。
そこで配列ABの第1次元と第2次元を入れ替えてみると、n = 5000では変わらないが、
1万, 2万, 5万, 10万, 20万では35%前後高速になった。これは、改良前には第2次元の添字が
小さい要素に書き込みが集中しているため、改良後のように第1次元に入れ替えた方が
纏まったメモリ領域に書き込みが集中しキャッシュの効きが良くなるからだと考えられる。
一方、n = 100万で高速化しないのは、書き込み集中領域が大きすぎるからだろう。

外部ﾘﾝｸ:ideone.com
n = 100万の場合にはr2の値によってデータを多数の列へ振り分けるのをやめ、列を1つにして、
その内部でr2の値により2種類に区分し、それぞれの内部で2種類にさらに区分し、…と再帰的に
区分していけば（要するにクイックソートの変形版）、1つの配列内での要素のスワップだけで済み、
キャッシュの効きが改善されるとの予想通り、n = 100万で実行速度は>>296より25%速くなった。
(原理的には>>300より非効率なのでn = 5000では>>300より当然遅い)

422(1): デフォルトの名無しさん [sage] 2024/09/03(火) 13:38:16.60 ID:Jxau6mSM(3/3) AAS
ちょっと試すだけならウェブサービスを使う手も

Common Lispを動かせるオンラインコンパイラーサイト
外部ﾘﾝｸ:rextester.com
外部ﾘﾝｸ:www.jdoodle.com
外部ﾘﾝｸ:wandbox.org

これらはideoneとは異なり "Share" とか "Save" とかをクリックしない限り保存・公開されない(はず)

510(21): デフォルトの名無しさん [] 2025/01/30(木) 21:27:24.39 ID:te1+SH0T(1) AAS
お題
ソース文字列と検索文字列が入力されます
検索文字列の文字をすべて含むソース文字列の部分文字列のうち
一番短い部分文字列を出力してください

DHBICEJAFG EIC → ICE
FDGJHCBIEA EIC → CBIE
FBHDCIJGEA EIC → CIJGE
JDIBGHCEAF EIC → IBGHCE
JBCIAGDHEF EIC → CIAGDHE
EJFBCAGIHD EIC → EJFBCAGI
IADCGJFBEH EIC → IADCGJFBE
IDFHBJGAEC EIC → IDFHBJGAEC

544(2): 9 [sage] 2025/02/08(土) 00:22:55.52 ID:vma3KbbM(1/2) AAS
>>510 Perl5、>>537 の修正版

外部ﾘﾝｸ:ideone.com

修正点
・>>537では間違って一番長い範囲を検出していたが、一番短い範囲に修正した。（サンプルデータではそれらの解はたまたま一致）
・パターンが3文字であることに依存する定数「2(=3 -1 )」をハードコードしている箇所があったので、パターン文字数次第で処理するように修正
・検出した候補文字列リストのうち一番短い物の検索のためにわざわざ候補リスト全体をsortするのをやめて
　reduceによって長さが一番短い文字列を検索するように修正

List::Utils は言語処理系にデフォルトで付属のコアモジュール、
List::MoreUtils はCPANのオプションノジュールだがideoneのperlにはｲﾝｽｺされていたので使っちゃいましたﾃﾍﾍﾟﾛ

なお、候補文字列リストを作らず、ループの最内ifの中で一番短い文字列だけを記録していく様に記述すれば
大規模問題で若干効率が良くなるだろうけど、
まあいいや、もういいや。

485(20): デフォルトの名無しさん [] 2025/01/22(水) 21:35:12.82 ID:JtEnwxKE(1) AAS
お題

文字列と長さを入力として受け取り
デカルト積のリストを出力してください

入力：ABC 1
出力：[A, B, C]

入力：ABC 2
出力：[AA, AB, AC, BA, BB, BC, CA, CB, CC]

入力：ABC 3
出力：[AAA, AAB, AAC, ABA, ABB, ABC, ACA, ACB, ACC, BAA, BAB, BAC, BBA, BBB, BBC, BCA, BCB, BCC, CAA, CAB, CAC, CBA, CBB, CBC, CCA, CCB, CCC]

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