プログラミングのお題スレ Part22

**デフォルトの名無しさん** · 2025/08/16(土) 20:29:06.33

>>799 の問題B
R
https://ideone.com/SdWBKf
C++
https://ideone.com/90BpGt

**デフォルトの名無しさん** · 2025/08/16(土) 21:32:58.04

>>799
>>802 のC++のithDuplicatedPermutation関数は引数が別の値（例えばn = 5, m = 3）のとき
正しく計算できなかったので修正。Rの方はintではなくdoubleで計算しているので問題ない。

https://ideone.com/uH8dpO

**デフォルトの名無しさん** · 2025/08/16(土) 21:46:08.81

32bitだと階乗は12!が限界

**デフォルトの名無しさん** · 2025/08/17(日) 12:07:33.92

>>799 ruby
https://ideone.com/o2Qlkr

>>799 c
https://ideone.com/Q4XNBb

**805** · 2025/08/17(日) 15:08:29.44

>>799 ruby 若干の改善
https://ideone.com/oavxRo

>>799 c 若干の改善
https://ideone.com/34A07H

**デフォルトの名無しさん** · 2025/08/17(日) 15:21:28.95

ソートが消えて>>800と同じアルゴリズムになったね

**デフォルトの名無しさん** · 2025/08/17(日) 20:40:30.84

>>804
確かにそうだった。15!も14!もintの範囲内に収まらない。>>803でn = 5に変えた場合に正しい
出力になるのはたまたまだった。

>>802をBigInt化するだけで問題なかった。
R
https://ideone.com/OgBxTJ
C++
https://ideone.com/KLqe3g

**デフォルトの名無しさん** · 2025/08/19(火) 21:08:19.27

>>799 問題A
perl

use v5.42;

sub nthPermutation($digits, $rank) {
　　my @figures = (1..$digits);
　　my @fact = (1);
　　push @fact, $_ * $fact[-1] for @figures;
　　return join "", map { splice(@figures, $_, 1) } sub($n, $r) {
　　　　$n-- ? (int($r / $fact[$n]), __SUB__->($n, $r % $fact[$n])) : ();
　　　}->($digits, $rank - 1);
}

for my $i (1, 2, 3, 123456, 234567, 362880) {
　　say "$i -> " . nthPermutation(9, $i);
}

1 -> 123456789
2 -> 123456798
3 -> 123456879
123456 -> 416589732
234567 -> 684753219
362880 -> 987654321

**デフォルトの名無しさん** · 2025/08/19(火) 21:28:38.04

>>771 scheme (chicken 4.13)
https://ideone.com/RREeGy

**806** · 2025/08/21(木) 22:19:54.42

>>799 ruby
https://ideone.com/3TW9Vr
・問題A時に若干端折る

**デフォルトの名無しさん** · 2025/08/21(木) 23:15:48.39

>>799 の逆変換プログラム
R
https://ideone.com/TU73Yu
C++
https://ideone.com/dmETd5

問題A, 問題Bとは違って、順列に出現するユニークな整数は1～nの連番でなくても良いし、
出現回数はすべて同じでなくても良い。例えば、入力は [3, 1, 4, 1, 5, 9] でも良い
（ユニークな整数は1, 3, 4, 5, 9で、出現回数は1が2回、その他が1回）。

**デフォルトの名無しさん** · 2025/08/22(金) 01:14:43.39

>>799
Java
https://paiza.io/projects/F5kCIBu6BOVB9QTX7hHWMg

**デフォルトの名無しさん** · 2025/08/22(金) 06:55:21.34

>>812
Rust　>>799の逆変換の重複順列の何番目か算出

use itertools::Itertools;
use num::{BigUint, One};

// 重複順列の何番目かを求める ex. "222331434114" → "123456"番目
fn to_nth(input: &str) -> String {
// 出現数
let (mut counts, chars): (Vec<usize>, Vec<char>) = input.chars().sorted().dedup_with_count().multiunzip();
// index化input
let input: Vec<usize> = input.chars().map(|c| chars.iter().position(|&c0| c0 == c).unwrap()).collect();
// 階乗関数
fn factorial(x: usize) -> BigUint { (1..=x).fold(BigUint::one(), |p, x| p * x) }
// 重複順列の総数
let mut whole: BigUint = factorial(input.len()) / counts.iter().map(|&x| factorial(x)).product::<BigUint>();
// nth番目を算出
(1..=input.len()).rev().zip(input).fold(BigUint::one(), |mut nth, (len, index)| {
// 自分より前までの総数をnthに足す
nth += &whole * counts[..index].iter().sum::<usize>() / len;
// 自分の総数へ更新
whole *= counts[index];
whole /= len;
counts[index] -= 1;
nth
})
.to_string()
}

**デフォルトの名無しさん** · 2025/08/22(金) 06:56:46.07

>>814の検証分

fn main() {
assert_eq!(to_nth("123456789"), "1");
assert_eq!(to_nth("123456798"), "2");
assert_eq!(to_nth("123456879"), "3");
assert_eq!(to_nth("416589732"), "123456");
assert_eq!(to_nth("684753219"), "234567");
assert_eq!(to_nth("987654321"), "362880");

assert_eq!(to_nth("111222333444"), "1");
assert_eq!(to_nth("111222334344"), "2");
assert_eq!(to_nth("111222334434"), "3");
assert_eq!(to_nth("222331434114"), "123456");
assert_eq!(to_nth("324424331112"), "234567");
assert_eq!(to_nth("444333222111"), "369600");

assert_eq!(to_nth("111333442545225"), "123456");
assert_eq!(to_nth("555444333222111"), "168168000");

assert_eq!(to_nth("11111222223333344444555556666677777899⑩⑩889889⑩⑩⑩9"), "123456");
assert_eq!(to_nth("⑩⑩⑩⑩⑩999998888877777666665555544444333332222211111"), "49120458506088132224064306071170476903628800");

assert_eq!(to_nth("314159"), "127");
assert_eq!(to_nth("3141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067"), "11503448027594046007734790817193859678406683579515952737315863863451534425766911708030454269");
assert_eq!(to_nth("なまむぎなまごめなまたまご"), "10515454");
assert_eq!(to_nth("かえるぴょこぴょこみぴょこぴょこあわせてぴょこぴょこむぴょこぴょこ"), "8273693808428448039784");
}

**811** · 2025/08/22(金) 20:26:43.82

>>799 ruby
https://ideone.com/vvp0kq
・問題A時に全体的な規則性に着目
・部分的に着目しちゃったのが>>811
・何も工夫を入れなかったのが>>806

**816** · 2025/08/23(土) 20:27:40.18

>>799 ruby 問題Bもケア
https://ideone.com/od17Hn

**デフォルトの名無しさん** · 2025/08/23(土) 21:01:55.02

>>799
java
https://ideone.com/qRTy1Z

**817** · 2025/08/23(土) 23:26:24.12

>>799 java
https://ideone.com/78psr6

**デフォルトの名無しさん** · 2025/08/24(日) 21:13:57.80

>>812の逆変換プログラムは>>808の順変換プログラムを流用したから処理に無駄があった。
逆変換用に一から書き直したらすっきりした。

R
https://ideone.com/jYUHe1
C++
https://ideone.com/Lne3AQ

**819** · 2025/08/25(月) 00:28:39.45

>>799 java Iterable<int[]>
https://ideone.com/NRTZpa

**デフォルトの名無しさん** · 2025/08/27(水) 00:40:48.46

>>799 ocaml
https://ideone.com/1Jx1Q8

>>799 scheme (chicken 4.13)
https://ideone.com/n7pIFw

**デフォルトの名無しさん** · 2025/08/27(水) 21:02:12.94

>>799 octave
https://ideone.com/RH6xXb

**デフォルトの名無しさん** · 2025/08/27(水) 21:46:51.59

>>820の逆変換プログラムのC#版
https://ideone.com/8HpCN9

LINQのTakeWhileメソッドとSumメソッドを組み合わせたらすっきり書けた。

**821** · 2025/08/28(木) 21:01:46.43

>>799 java
https://ideone.com/aKkfqN
・next()ごとに複製しない版。する版は >>821
・hasNext()側で次を準備。next()側なのは >>821

**デフォルトの名無しさん** · 2025/08/29(金) 13:52:26.21

>>799
https://ideone.com/JLM8r8
C++

**デフォルトの名無しさん** · 2025/08/29(金) 20:09:32.40

>>812 ruby 2.5.5
https://ideone.com/tzzN04
・tallyあるのは2.7以降

>>812 octave
https://ideone.com/ebJd9k

**デフォルトの名無しさん** · 2025/08/29(金) 22:34:59.67

>>802をCMD (Windowsバッチファイル) に移植

@echo off & setlocal EnableDelayedExpansion
echo 【問題A】
for %%i in (1, 2, 3, 123456, 234567, 362880) do call :ithDuplicatedPermutation 9 1 %%i
echo.
echo 【問題B】
for %%i in (1, 2, 3, 123456, 234567, 369600) do call :ithDuplicatedPermutation 4 3 %%i
exit /b

:ithDuplicatedPermutation
set /a n = %1, m = %2, i = %3, L = 0, P = 1
for /l %%j in (1, 1, %n%) do (
　　set /a c%%j = %m%
　　for /l %%k in (1, 1, %m%) do set /a L += 1, P = P * L / %%k
)
set a=%i% →
for /l %%j in (1, 1, %L%) do (
　　set /a done = 0
　　for /l %%k in (1, 1, %n%) do (
　　　　if !done! equ 0 (
　　　　　　set /a "q = P * c%%k / (L - %%j + 1)"
　　　　　　if !i! leq !q! (
　　　　　　　　set a=!a!%%k
　　　　　　　　set /a c%%k -= 1, P = q, done = 1
　　　　　　) else (
　　　　　　　　set /a i -= q
　　　　　　)
　　　　)
　　)
)
echo %a%

**デフォルトの名無しさん** · 2025/08/29(金) 22:35:22.12

-- 実行結果 --

【問題A】
1 → 123456789
2 → 123456798
3 → 123456879
123456 → 416589732
234567 → 684753219
362880 → 987654321

【問題B】
1 → 111222333444
2 → 111222334344
3 → 111222334434
123456 → 222331434114
234567 → 324424331112
369600 → 444333222111

**デフォルトの名無しさん** · 2025/08/30(土) 17:37:04.21

>>812 ocaml
https://ideone.com/SfsytC

>>812 scheme (chicken 4.13)
https://ideone.com/jwWrRt

**830** · 2025/09/02(火) 21:36:10.92

>>812 scheme (chicken 4.13)
https://ideone.com/fZufck
・集計部分をalistに変えてみただけ

**デフォルトの名無しさん** · 2025/09/06(土) 23:05:19.87

>>561 scheme (chicken 4.13)
https://ideone.com/lCgs9s

**832** · 2025/09/07(日) 12:29:41.48

>>561 scheme (chicken 4.13)
https://ideone.com/8VZv71
・m1m2を不必要にリストにしてたのを廃止

**833** · 2025/09/07(日) 14:22:59.56

>>561 scheme (chicken 4.13)
https://ideone.com/EsJWtG
・letを自然な位置に移動

**デフォルトの名無しさん** · 2025/09/08(月) 23:02:49.14

>>485 scheme (chicken 4.13)
https://ideone.com/feYtNB

>>500 scheme (chicken 4.13)
https://ideone.com/Svhv1y

**835** · 2025/09/08(月) 23:33:25.73

>>485 scheme (chicken 4.13)
https://ideone.com/ejvKat
・(product . lists)
・(product xs . rest) が >>835

**デフォルトの名無しさん** · 2025/09/09(火) 21:56:29.91

>>438 scheme (chicken 4.13)
https://ideone.com/6weUjU
・まずまとまりに分割して処理

>>438 scheme (chicken 4.13)
https://ideone.com/BCt6fd
・最初のを四つにして、残りはスキップ

**デフォルトの名無しさん** · 2025/09/10(水) 21:21:57.38

>>438
C#で短く書けた
https://ideone.com/SwAZsS

x.EndsWith(" ") でなく x.LastOrDefault() == ' ' の方が長くはなるが効率的かも知れない。

**836** · 2025/09/10(水) 22:49:33.81

>>485 scheme (chicken 4.13)
https://ideone.com/g8wtFG
・デカルト積の解釈を（勝手に）変更

**839** · 2025/09/10(水) 23:35:38.95

>>485 scheme (chicken 4.13)
https://ideone.com/A6K3XL
・(cons y x)して最後にreverseする
・(list x y)して最後にflattenするのが >>839

**840** · 2025/09/11(木) 23:05:23.09

>>485 scheme (chicken 4.13)
https://ideone.com/YqrvdM
・reverse回数減らした版

**デフォルトの名無しさん** · 2025/09/12(金) 15:41:31.15

お題
1行1単語のリストが、しりとりとして成立しているか判定するコードを書きなさい
成立していたら◯、不成立なら☓をしゅつりょくすること

【入力】
りんご
ごりら
らっぱ

**デフォルトの名無しさん** · 2025/09/12(金) 16:19:33.85

入力例に対する出力例が存在しなくて曖昧
それを補わないと問題が不成立

**デフォルトの名無しさん** · 2025/09/12(金) 20:36:05.46

>>438 scheme (chicken 4.13)
https://ideone.com/SlkO0l
・空白時にdrop-while

>>842 ruby
https://ideone.com/mY83rW

**デフォルトの名無しさん** · 2025/09/13(土) 12:21:51.23

退屈そうだからちょっと難易度高め

【問題】
各桁の数が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

**デフォルトの名無しさん** · 2025/09/13(土) 21:09:19.41

>>845
R
https://ideone.com/R7chTY

ヒントはどう使うのかわからなかった。

**デフォルトの名無しさん** · 2025/09/14(日) 02:07:05.25

>>845　c++
https://ideone.com/ezHz45
先越された

**デフォルトの名無しさん** · 2025/09/14(日) 02:17:37.66

>>845 ruby
https://ideone.com/wrV2zh
・なんとなく動いてる版
・チマチマと次を探して行く
・G[20]まで出すのがやっと(4.05s)

**デフォルトの名無しさん** · 2025/09/14(日) 21:00:58.83

>>845
R
https://ideone.com/XhdJw4

>>846より行列計算が速くなった。変数名mとnが逆だったのを直した。

C++に移植
https://ideone.com/9dibE0

**デフォルトの名無しさん** · 2025/09/14(日) 22:50:48.82

>>845
Fortranに移植
https://ideone.com/CnJ0S9

行列計算を短く書けて、しかも実行が速い。

**848** · 2025/09/15(月) 00:34:43.20

>>845 ruby
https://ideone.com/3I72I6
・キャッシュ探りながら構築
・c[桁の合計][幅] = とりうるパターン

**851** · 2025/09/15(月) 00:58:49.72

https://ideone.com/GWbQAx
・動きは >>851 といっしょ
・若干の整理

**デフォルトの名無しさん** · 2025/09/15(月) 22:27:44.05

>>850では行末に無駄な半角空白文字が出力される。消すには最後から3行目のnthPartition(m, n)を
trim( )で囲めば良い。

**852** · 2025/09/16(火) 01:02:30.84

>>845 ruby
https://ideone.com/n5Jqm3
・動きは >>851 といっしょ
・数値の内部表現を配列から整数へ変更

**854** · 2025/09/17(水) 22:30:29.22

>>845 ruby 2.5.5
https://ideone.com/oAQimi
・とりうるパターン数に着目し迫る
・tallyは2.7以降

**デフォルトの名無しさん** · 2025/09/17(水) 22:43:48.03

>>845
C++
https://ideone.com/I6K1tl

行列Aの計算で加減算・代入回数を>>849より減らした。実行時間の違いは分からなかった。

**デフォルトの名無しさん** · 2025/09/17(水) 23:39:47.32

>>856
BigInt化してm = 2000, n = 2¹⁰²⁴で実行したら違いが明確になった。

(1) >>849のBigInt版
https://ideone.com/S92L9G
(2) >>856のBigInt版
https://ideone.com/3x03xT

加減算・代入回数を削減した(2)の方が確かに速く、(1)の約4分の3の実行時間。

**855** · 2025/09/18(木) 21:13:33.56

>>845 ruby 2.5.5
https://ideone.com/Zm2433
・揃ってからcumsum、のリズムを廃止

**858** · 2025/09/19(金) 21:59:08.62

>>845 ruby 2.5.5
https://ideone.com/iwQNCH
・若干の整理（loop廃止、fill三回へ置き換え）

**859** · 2025/09/20(土) 21:39:31.29

>>845 ruby 2.5.5
https://ideone.com/jHqv2L
・内部表現の変更
　112225→[2,3,0,0,1]

**860** · 2025/09/22(月) 21:37:36.11

>>845 ruby 2.5.5
https://ideone.com/MDHX6v
・内部表現のさらなる変更
・パターン数を直接キャッシュするようにした
　cc[合計][幅] = とりうるパターン数

>>845 ruby
https://ideone.com/PB8S7w
・m = 2000, n = 1 << 1024

**861** · 2025/09/23(火) 01:13:48.01

>>845 c++
https://ideone.com/oma0Jf
・ruby版861の移植
・m = 2000, n = 1 << 1024

**862** · 2025/09/26(金) 21:58:13.14

>>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では使えずボツ

**デフォルトの名無しさん** · 2025/10/19(日) 18:23:02.12

お題
硬貨の種類と金額が与えられます。
硬化の合計がちょうど金額と同じになるように硬貨を選ぶとき、使用枚数の最小値を求めてください。
支払いが不可能なときは-1を出力します。
各硬貨は無制限に使用できます。
額面の大きい硬貨を優先して選ぶ貪欲法が常に最適解を与えるとは限らないことに注意。

入力
硬貨：[1,7,10]
金額：14

出力
使用枚数：2

**デフォルトの名無しさん** · 2025/10/19(日) 21:36:07.90

>>864
R
https://ideone.com/bUDu3l

**デフォルトの名無しさん** · 2025/10/22(水) 21:34:32.83

>>864
金額が大きい場合でも高速に求められるようにした。

R
https://ideone.com/NC6lV7
C++
https://ideone.com/52TbeF

**デフォルトの名無しさん** · 2025/10/26(日) 09:31:44.23

お題というか、協力してほしい感じなんですが、素因数分解関数をHaskellで書いて色んな数を素因数分解して遊んでいたら確認したい事実に出くわしたので。

31 <- 素数
331 <- 素数
3331 <- 素数
33331 <- 素数
333331 <- 素数

と、３が５個並んで末尾が１の数字までは素数という事が分かりましたが、いかんせん、ノートだと力不足。
それにCとかで書き直したらもっと先まで行けるかも？という事で、この先、どこまで33...31が素数なのかを調べて欲しいのです。
協力お願いします<(_ _)>

一応、Haskellではこんなコードです。

factorization n = f primes n
　where　primes = 2:(sieve [3,5..])
　　　　　　where sieve (p:xs) = p:(sieve [x | x <- xs, x `mod` p /= 0])

　　　　　f (p:ps) n | n <= p = [n]
　　　　　f (p:ps) n | n `mod` p == 0 = p:f (p:ps) (n `div` p)
　　　　　f (p:ps) n = f ps n

**デフォルトの名無しさん** · 2025/10/26(日) 09:50:23.90

あ、ただの素数判定でも良いです。
ちなみに、66..61の場合は6661までは素数ですが66661は素数じゃなくなりました。
なので、33..31もどこかで素数じゃなくなるのか？それともずっと素数になりそうなのか？って疑問が持ち上がりました。

**デフォルトの名無しさん** · 2025/10/26(日) 10:13:01.91

>>867
興を削いですまんが、「33...331は素数か」でググったら、AIが（あまり大きくない桁数で）答えを示してくれた…

**デフォルトの名無しさん** · 2025/10/26(日) 10:19:15.38

near-repdigit素数とかで研究されてるらしい

結果だけ知りたいなら↓がまとめてる
https://stdkmd.net/nrr/3/33331.htm

**869** · 2025/10/26(日) 10:21:11.68

>>869
ちなみに、以下の思考経路だったのでプログラミング的な思考がゼロだった訳では無い。
1.多倍長整数で組むべきかな？
2.でも64bit整数の範囲で合成数だったら馬鹿馬鹿しいな
3.組む前にカンニングしちゃえ
4.>>869

**デフォルトの名無しさん** · 2025/10/26(日) 17:08:32.87

>>869-871
いえいえ、ああ、やっぱりずっと素数という訳にはいかないんですね…。
何か素数の秘密に触れるヒントか？と心躍ったけど、そんな訳なかったですね(´・ω・｀)

あやうく数学スレで鼻息荒く書き込むところでした。

ありがとうございました<(_ _)>

**デフォルトの名無しさん** · 2025/10/26(日) 17:55:12.41

29bitで収まる範囲内
333333331 = 17 × 19607843
これを求められなかったHaskellはすごく遅い？

**デフォルトの名無しさん** · 2025/10/26(日) 23:06:07.50

>>873
速いアルゴリズムに変えたら何とか1分ほどでその数字まで届きました。
（そもそも、>867 のは美しいとか短いとかの枕詞が付くコードですし。33...31に気付かなかったら4桁ぐらいが実用的ならおｋだったので）

改良版Haskell
pfactorization = f primes
　where primes =2:3:5#primes
　　　　　where n#x@(m:q:y)=[n|gcd m n<2]++(n+2)#last(x:[m*q:y|q^2-3<n])

というか、それより1桁少ない方が少し時間かかりますね。
19607843 < 33333331 なので、素数比較回数が多いのかと。

**デフォルトの名無しさん** · 2025/10/26(日) 23:07:37.04

あ、f の方を忘れた。
f のコードは変更なしです。

**デフォルトの名無しさん** · 2025/11/07(金) 05:48:17.42

>>868
cだとこんな感じでいいのかな？
3333333333333331くらいまで一瞬でできる

#include <stdio.h>

int main(void) {
long long d, n;

printf("Enter a number: ");
scanf("%lld", &n);

for (d = 2; d * d <= n; d++) {
if (n % d == 0)
break;
}
if (d * d <= n)
printf("%lld is divisible by %lld\n", n, d);
else
printf("%lld is prime.\n", n);

return 0;
}