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

9 · 2025/03/18(火) 21:41:48.53

>>683
>やはり想定通り気の利いた高速解放が要りますﾃﾍﾍﾟﾛ。

そのﾋﾝﾄになるかいな…？
・16進数を10進数に変換すると桁数は同じまたは高々1桁増えるのみ（だともう、証明略）
・桁数が同じ場合、16進数と10進数が同じということはあり得ない、自明
・一桁増える場合は先頭または末尾に一桁増える。残りが16進数と同じ部分文字列であるかが評価対象となる

9 · 2025/03/18(火) 21:42:49.00

>>685
あそうなんだ。じゃオレ様が一番乗りということでヨロ
ﾉｼ

9 · 2025/03/18(火) 21:52:10.05

>>686
>・一桁増える場合は先頭または末尾に一桁増える。残りが16進数と同じ部分文字列であるかが評価対象となる

二桁増える場合があるのでこれは誤りでした

**684** · 2025/03/19(水) 06:18:11.44

ようやく題意は理解したけど良い解法が思いつかない
ちなみに36桁以下だと答えはいくつありますか？

**デフォルトの名無しさん** · 2025/03/19(水) 08:44:27.79

>>680
ruby 遅いけど
i=0
while i<10**16
if %r|[a-f]|=~i.to_s(16)
i=i.to_s(16).gsub(%r|[a-f].*|){|e| e.gsub(%r|.|,"f")}.hex
else
puts "#{i},0x#{i.to_s(16)}" if %r|#{i.to_s(16)}|=~i.to_s
end
i+=1
end

9 · 2025/03/19(水) 16:33:58.47

>>686
> ・桁数が同じ場合、16進数と10進数が同じということはあり得ない、自明

大間違い。16進数と10進数で桁数が同じ値のうち、一桁のものは、16進も10審も同じだった…orz

結局、高速解放はあるんだろうか？
あるいはコラッツ予想みたいに「無いかもしれない」類の、考えるだけ無駄な問題なのだろうか？

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

>>689
167個で最大値は697786638998562641695629924526065234

>>691
時間をかけて64桁以下で解いたら、405個で最大値は

　2714476666993915057605587441263923823484611431446449961712093492

だった。これはナイーヴな解法ではC++ですら到底求められない値だから、高速解法が
実在する証になっているだろう。

解答例は1週間くらい経ったら載せるので、それまでよく考えてみて下さい。

**デフォルトの名無しさん** · 2025/03/19(水) 22:39:07.36

お題：単位分数のエジプト風分解(2進数風味)
1/aを、1/a=1/b+c/dを満たす1/bとc/dに分解する。
aは1以上の整数とする。
c, dは整数とし、bは2の整べき乗(1, 2, 4,...)とする。
c/dは絶対値が最小である事(負数であってもよい)。

例：
1/3→1/4+1/12 : b=4, c=1, d=12
1/7→1/8+1/56 : b=8, c=1, d=56
1/9→1/8-1/72 : b=8, c=-1, d=72(c=1, d=-72も可)
1/13→1/16+3/208 : b=16, c=3, d=288
1/60→1/64+1/960 : b=64, c=1, d=960

**693** · 2025/03/19(水) 22:42:43.02

aは2以上の整数とする。
に訂正します。

**デフォルトの名無しさん** · 2025/03/19(水) 23:16:25.83

>>693
R
https://ideone.com/TaaAw2

aが2の整べき乗の場合の出力形式に指定がなかったので適当に決めた。

**デフォルトの名無しさん** · 2025/03/20(木) 08:21:38.87

>>693 Rust
fn f(a: i64) -> String {
　let b = (a as u64).next_power_of_two() as i64;
　let b = if 3 * a > 2 * b { b } else { b >> 1 };
　let (c, d) = (b - a, a * b);
　let shift = c.trailing_zeros().min(d.trailing_zeros());
　let (c, d) = (c >> shift, d >> shift);
　if a == b {
　　format!("1/{a}=1/{b}")
　} else {
　　format!("1/{a}=1/{b}{c:+}/{d}")
　}
}

fn main() {
　assert_eq!("1/3=1/4+1/12", f(3));
　assert_eq!("1/7=1/8+1/56", f(7));
　assert_eq!("1/9=1/8-1/72", f(9));
　assert_eq!("1/13=1/16+3/208", f(13));
　assert_eq!("1/60=1/64+1/960", f(60));
　assert_eq!("1/64=1/64", f(64));
　assert_eq!("1/6718464=1/8388608+1631/55037657088", f(6718464));
　assert_eq!("1/123456789=1/134217728+10760939/16570089725755392", f(123456789));
}

**デフォルトの名無しさん** · 2025/03/21(金) 12:56:29.73

>>680 　Rust
fn odai_680() -> Vec<i128> {
　let mut answer = vec![0];
　let n_max = (0..).find(|&n| pow16(n + 1) > pow10(36)).unwrap();
　for s in (0..).take_while(|&s| pow16(n_max) >= pow10(n_max + s + 1)) {
　　let c = (0..=n_max).map(|i| pow16(i) - pow10(i + s)).collect::<Vec<_>>();
　　let rmax = c.iter().scan(0, |s, &c| { *s += if c > 0 { c * 9 } else { 0 }; Some(*s) }).collect::<Vec<_>>();
　　let rmin = c.iter().scan(0, |s, &c| { *s += if c < 0 { c * 9 } else { 0 }; Some(*s) }).collect::<Vec<_>>();
　　let (mut i, mut n, mut d, mut ct) = (0, 1, vec![0; c.len()], vec![0; c.len() + 1]);
　　loop {
　　　d[i] += 1;
　　　if d[i] < 10 {
　　　　let m = pow10(n as u32 + s); ct[i] = c[i] * d[i] + ct[i+1];
　　　　if i == 0 {
　　　　　if ct[0] >= 0 && ct[0] % m < pow10(s) { answer.push(d.iter().take(n).rev().fold(0, |sum, &d| sum * 16 + d)) }
　　　　} else {
　　　　　let (max, min) = (ct[i] + rmax[i-1], ct[i] + rmin[i-1]);
　　　　　if max >= 0 && (max - min > m || pow10(s) > min % m || min % m > max % m) { i -= 1; }
　　　　}
　　　} else { d[i] = -1; i += 1; if i == n { if n == d.len() { break; } n += 1; } }
　　}
　}
　answer.sort(); answer
}

**デフォルトの名無しさん** · 2025/03/21(金) 12:58:11.47

>>697
// 略記
fn pow16(x: u32) -> i128 { 16_i128.pow(x) }
fn pow10(x: u32) -> i128 { 10_i128.pow(x) }

// 結果検証
fn main() {
　let answer = odai_680();
　assert_eq!(167, answer.len());
　for &a in &answer {
　　assert!(a.to_string().contains(&format!("{a:x}")));
　}
　assert_eq!(0, answer[0]);
　assert_eq!(1, answer[1]);
　assert_eq!(357440, answer[10]);
　assert_eq!(2182104649, answer[54]);
　assert_eq!(3927570397557, answer[71]);
　assert_eq!(38135630558262267902210, answer[99]);
　assert_eq!(331052794565713975838768757043267, answer[152]);
　assert_eq!(697786638998562641695629924526065234, answer[answer.len() - 1]);
}

**デフォルトの名無しさん** · 2025/03/21(金) 20:49:29.98

>>697-698
Rustはよく知らないが、mainのforループ内をprintln!("{}", a);に置き換えれば解が表示されるんだよね?
実行結果を>>685で述べたC++プログラムのものと照合したら167個の解すべてが一致した。見事正解!
実行時間はC++プログラムの数倍かかるようだが、ideoneでの実行時間も見たいので載せて下さい。

**デフォルトの名無しさん** · 2025/03/23(日) 23:00:51.13

>>680から1週間経ったので解答例を掲載

>>685を書いたときに作ってあった2つのC++プログラム
https://ideone.com/KID2jR
https://ideone.com/ysdd6b

1番目ではsolve関数の再帰呼び出しの対象とするx[p]の下限と上限を線形探索するが、
2番目では二分探索する。要素数10では二分探索の効果は薄いと思いきや、大分速くなった。

2番目を読み返していたらバグを発見してしまった。i = N - 1のとき63行目のa[i + 1]はa[N]となり
配列の添字範囲外アクセス。0との比較だけだし、if文の評価がどっちでも以降の処理は結局同じだから、
実害も解への影響もないが、厳格さが必要ならif ((i + 1 < N ? a[i + 1] : 0) >= 0) {と書き換えるべきだな。
実行時間への影響は無視できる。

それぞれのPowerShellへの移植版
https://ideone.com/vEGZ3D
https://ideone.com/azzMa4

完全な逐語訳ではなく、PowerShellで書くと遅くなったり煩雑になったりする箇所は適宜改変した。
15桁以下の場合は64ビット整数でも桁溢れしないので、BigIntの代わりにInt64を使えば少し速くなる。

**デフォルトの名無しさん** · 2025/03/24(月) 22:16:36.44

非素数であることが既知の巨大整数を素因数分解するときの
最速のアルゴリズムって何がある？

**デフォルトの名無しさん** · 2025/03/25(火) 15:25:56.57

>>699
> 実行時間はC++プログラムの数倍かかるようだが

rustc -C opt-level=2 でコンパイルしたら
g++ -O2 でコンパイルした ideone_KID2jR.cpp (>>700の一つめ) とほぼ同じ速度出たよ

**デフォルトの名無しさん** · 2025/03/25(火) 15:54:47.24

>>702
データ精度を揃えたアルゴリズム比較のために
>>697-698をi128固定ではなくnum::BigIntにして計測して見ては？

あと出題者>>685は>>700の二つ目で(倍速以上に)短縮出来たと言っているよ

**デフォルトの名無しさん** · 2025/03/25(火) 16:11:02.68

そこまでは興味ないや
「数倍」だったのはもしかして最適化オプション付けてなかったんじゃない?ってだけの話

**デフォルトの名無しさん** · 2025/03/25(火) 17:30:47.40

>>697-698をBigIntに変えるのはどうしたらいいのか分かんなかったので
>>700の方を boost::multiprecision::cpp_int から boost::multiprecision::int128_t に変えてみた

改変版 | オリジナル
https://ideone.com/Ie0HhO 0.12s | https://ideone.com/KID2jR 0.43s
https://ideone.com/np3p5h 0.11s | https://ideone.com/ysdd6b 0.23s

**デフォルトの名無しさん** · 2025/03/25(火) 20:18:24.92

>>705
感心した、出題者回答C++コードはほんの少し変更するだけで簡単にBigInt/i128切り替え出来るのか

>>697-698
Rustはどうなのかな？

**デフォルトの名無しさん** · 2025/03/25(火) 23:43:24.86

>>704
>>699では最適化オプションを付けてrustc -O a.rsでコンパイルした。最適化なしでは
ありの4.6倍くらい掛かった。もしやと思ってコンパイラをアップデートしてみたら、
実行時間は約3分の1に激減し、>>700の1番目と大差ない1.3倍ほどに収まった。

Rustの古いコンパイラ（5年前のもの）がこんなに低性能だったとは…

**デフォルトの名無しさん** · 2025/03/27(木) 11:39:31.21

>>697
crateのnumを使う

**デフォルトの名無しさん** · 2025/03/27(木) 20:29:20.38

c言語で実用的なプログラムを作りたい。
いいテーマはありますか？

**デフォルトの名無しさん** · 2025/03/27(木) 20:35:59.71

お題：＃（シャープ）を入力の段数でウンコ状に並べて出力せよ
出力は全角でも半角でもどちらでもよしとする（5ch は半角スペース表示できない）

in < 3
out >
　　＃
　＃＃＃
＃＃＃＃＃

**デフォルトの名無しさん** · 2025/03/27(木) 21:06:27.50

>>710
PowerShell

function unko($n)
{
　　if ($n -ge 1) {1..$n |% {"　" * ($n - $_) + "＃" * (2 * $_ - 1)}}
}

unko 3

-- 実行結果 --
　　＃
　＃＃＃
＃＃＃＃＃

**デフォルトの名無しさん** · 2025/03/28(金) 21:33:35.13

お題：素因数の総和が2025である2000万以下の自然数をすべて求めて下さい。

例)
32272
　素因数分解すると32272 = 2 × 2 × 2 × 2 × 2017で、
　素因数の総和は2 + 2 + 2 + 2 + 2017 = 2025となります。

※20億以下でもC++で5秒以内に余裕で完了できますが、出力が長すぎるため2000万以下としました。
　その結果、Rでも5秒以内に余裕で完了できる問題になりました。

**デフォルトの名無しさん** · 2025/03/28(金) 21:54:52.53

>>710
山状ではだめだったのか
俺にはわからない

**デフォルトの名無しさん** · 2025/03/28(金) 22:12:15.09

お題
AさんがBさんに惚れてることを
A-B
と表します

両思いのペアを出力してください

入力
D-L,U-X,U-Y,U-R,Z-B,B-E,B-M,B-N,V-H,V-X,W-F,W-R,R-B,R-W,O-W,O-S,F-A,Q-X,P-E,P-L,X-X,Y-M,Y-C,L-U,L-V,I-X,E-B,H-M,A-S

出力
B,E
R,W

**デフォルトの名無しさん** · 2025/03/28(金) 22:28:49.68

>>714
PowerShell

$s = "D-L,U-X,U-Y,U-R,Z-B,B-E,B-M,B-N,V-H,V-X,W-F,W-R,R-B,R-W,O-W,O-S,F-A,Q-X,P-E,P-L,X-X,Y-M,Y-C,L-U,L-V,I-X,E-B,H-M,A-S"
$h = @{}
$s -split "," |% {
　　$a, $b = $_ -split "-"
　　$h[$a] += , $b
}

foreach ($a in $h.keys) {
　　foreach ($b in $h[$a]) {
　　　　if ($a -lt $b -and $h[$b] -contains $a) {"$a,$b"}
　　}
}

-- 実行結果 --
B,E
R,W

**デフォルトの名無しさん** · 2025/03/28(金) 23:19:47.32

>>714
PowerShellでもう少し短く

$s = "D-L,U-X,U-Y,U-R,Z-B,B-E,B-M,B-N,V-H,V-X,W-F,W-R,R-B,R-W,O-W,O-S,F-A,Q-X,P-E,P-L,X-X,Y-M,Y-C,L-U,L-V,I-X,E-B,H-M,A-S"
$h = @{}
$s -split "," |% {
　　$a, $b = $_ -split "-"
　　$i, $t = if ($a -lt $b) {1, "$a,$b"} else {2, "$b,$a"}
　　$h[$t] = $h[$t] -bor $i
}

$h.keys |? {$h[$_] -eq 3} | sort

-- 実行結果 --
B,E
R,W

**デフォルトの名無しさん** · 2025/03/29(土) 11:51:50.06

>>714
Rust

use itertools::Itertools;

fn f(input: &str) -> impl Iterator<Item = &str> {
　input.split(',')
　　.map(|pair| (pair, pair.splitn(2, '-').collect_tuple().unwrap()))
　　.filter(|(_, (a, b))| a < b)
　　.flat_map(|(pair, (a, b))| {
　　　input.split(',')
　　　　.map(|pair| pair.splitn(2, '-').collect_tuple().unwrap())
　　　　.filter_map(move |(x, y)| (a == y && b == x).then_some(pair))
　　})
}

fn main() {
　let input = "D-L,U-X,U-Y,U-R,Z-B,B-E,B-M,B-N,V-H,V-X,W-F,W-R,R-B,R-W,O-W,O-S,F-A,Q-X,P-E,P-L,X-X,Y-M,Y-C,L-U,L-V,I-X,E-B,H-M,A-S";
　itertools::assert_equal(["B-E", "R-W"], f(input).sorted());
}

**デフォルトの名無しさん** · 2025/03/30(日) 01:28:45.68

お題：1～10までの範囲の乱数生成をn回行ったとき出た値の積が20の倍数になる確率Pnを出力せよ

n=2
2, 10 ... 20
4, 5 ... 20
Pn=???

n=3
2, 5, 2 ... 20
4, 5, 2 ... 40
Pn=???

**デフォルトの名無しさん** · 2025/03/30(日) 15:24:52.85

>>718
ん？
何千回も試行してその実際の発生率を出すの？
それとも数学的に確率の理論値を出すの？

**デフォルトの名無しさん** · 2025/03/30(日) 15:35:52.69

後者で学校の課題な予感がするな

**デフォルトの名無しさん** · 2025/03/30(日) 20:11:24.72

>>718
R Version4
https://ideone.com/r03zEZ

ideoneのRは古すぎてエラーが出てしまうので、出力は入力欄に記載した。

巨大整数型を使わなければideoneでも実行できる。
https://ideone.com/K0RefY

**デフォルトの名無しさん** · 2025/03/30(日) 20:58:57.54

>>718
C++への移植版
https://ideone.com/g87ECX

これもideoneのC++が古すぎて10行目をm = size(d)と書けず変更せざるを得なかった。

警備員[Lv.4] · 2025/03/31(月) 03:24:21.45

>>714
Kotlin
//paiza.io/projects/WMZL8ULLNxc0zJQPI2uUsA
URLあると書けなかったので先頭のhttps:を抜いた。

**デフォルトの名無しさん** · 2025/03/31(月) 05:32:04.89

>>718
学校の課題をここに書くなって教わらなかったの？

**デフォルトの名無しさん** · 2025/03/31(月) 22:37:26.59

>>718
>>721-722を整理して行列とヴェクトルの積ですっきり書けるようにした。

R (ideoneでも巨大整数型で実行可能になった)
https://ideone.com/sHNag3
C++
https://ideone.com/7zgflb

式を展開してしまえばPowerShellで結局これだけ。

$a, $b, $c, $d, $e, $f = 0, 1, 1, 2, 2, [BigInt]4

2..100 |% {
　　$a = 10 * $a + 5 * $b + 2 * $c + 2 * $d +　　 $e
　　$b = 　　　　　5 * $b + 3 * $c + 　　　　　　 $e + 　　$f
　　$c = 　　　　　　　　　 5 * $c + 　　　　　　　　　　　$f
　　$d = 　　　　　　　　　　　　　　8 * $d + 4 * $e + 2 * $f
　　$e = 　　　　　　　　　　　　　　　　　　 4 * $e + 2 * $f
　　$f = 　　　　　　　　　　　　　　　　　　　　　　　4 * $f
　　for ($p = $a; $p % 10 -eq 0; $p /= 10) {}
　　"P[$_] = 0.$p"
}

**デフォルトの名無しさん** · 2025/04/01(火) 22:39:42.98

半角スペースの意味がわからない
そういうこだわりは古臭いよ

**デフォルトの名無しさん** · 2025/04/02(水) 13:29:35.55

いまどきのプログラミングなら出力はHTMLだよな

**デフォルトの名無しさん** · 2025/04/02(水) 13:47:27.57

PHPさえその動作禁止だぞ

**デフォルトの名無しさん** · 2025/04/02(水) 14:31:23.27

>>725
変数名がa、b、cの時点でプロじゃねえな

**デフォルトの名無しさん** · 2025/04/02(水) 15:10:39.64

行列演算は数学でもa,b,c,dだから…

**デフォルトの名無しさん** · 2025/04/02(水) 19:51:02.16

俺が言ってるのは5chのプロじゃねえなってことだから
数学は関係ない

**デフォルトの名無しさん** · 2025/04/02(水) 19:56:31.51

5chのプロ笑

**デフォルトの名無しさん** · 2025/04/02(水) 20:14:17.34

5chのプロはどんな変数名使うのか教えて

**デフォルトの名無しさん** · 2025/04/02(水) 21:11:27.43

>>726
>>725の全角空白のこと?　項の書き忘れや書き間違いがないか分かりやすくするため。余分な空白や長い変数名が
ディスク・メモリ空間やコンパイル・インタプリト時間を無駄に増やすと気にする方が古臭くない?

とはいえ、今でもインタプリタ言語のPowerShellでは変数名を長くすると顕著に遅くなる。例えば、

$t1 = measure-command {for ($i = 0; $i -lt 1000000; $i++) {}}
$t2 = measure-command {for ($AnExtraordinarilyLongVariableName = 0; $AnExtraordinarilyLongVariableName -lt 1000000; $AnExtraordinarilyLongVariableName++) {}}
$t2.Ticks / $t1.Ticks

をPowerShell Ver.7で実行すると1.56前後の値が表示される。奇妙なことに、かなり古いVer.2では1前後の値になる。
実時間ではVer.7の$t2とVer.2の$t2が同程度なので、Ver.7では短い変数名での最適化が施されているということか。

それはさておき、>>712を解く人はいませんか?

**デフォルトの名無しさん** · 2025/04/02(水) 23:31:04.18

>>734
縦に揃えるのは無駄に横に長くなる

**デフォルトの名無しさん** · 2025/04/02(水) 23:33:04.35

>>734
ループは毎回、構文を解析しているわけじゃねえぞ？

警備員[Lv.5] · 2025/04/05(土) 14:46:26.08

>>719
このお題の場合は数学的に答えを出そうとするとプログラムを作る必要がなくなってしまわないか？
人が普通に数学的に考えて行くと答えが出てしまいそうな気がするんだが。
またはAIに聞いたらすぐ答えが出そうな感じが。

**デフォルトの名無しさん** · 2025/04/08(火) 23:28:40.30

>>712 　Rust
fn solve(n: usize, limit: usize) -> Vec<usize> {
　let mut answer = Vec::new();
　let mut pnt = generate_primes(n).iter().skip(1).rev().map(|&p| (p, 0, 0)).collect::<Vec<_>>();
　let (mut ci, mut cn, mut ct) = (0, n, 1_usize);
　'advance: loop {
　　pnt[ci..].iter_mut().for_each(|(_p, n, t)| (*n, *t) = (cn, ct));
　　if cn & 1 == 0 && ct.leading_zeros() >= (cn >> 1) as u32 {
　　　ct <<= cn >> 1;
　　　if ct <= limit { answer.push(ct as usize); }
　　}
　　for (i, (p, n, t)) in pnt.iter_mut().enumerate().rev() {
　　　if *n < *p { continue; }
　　　*n -= *p; *t *= *p;
　　　if *t > limit { continue; }
　　　if *n == 1 { continue; }
　　　if *n == 0 { answer.push(*t as usize); continue; }
　　　(ci, cn, ct) = (i, *n, *t);
　　　continue 'advance;
　　};
　　break;
　}
　answer.sort(); answer
}

**デフォルトの名無しさん** · 2025/04/08(火) 23:30:40.48

>>738
素因数の総和が2025になる問題を可能な素数の組合せ総当りで挑戦してみました
20億以下で約0.4秒と規定時間以内に実行できました
実行時間 solve(2025, 20000000): 22.638309ms
実行時間 solve(2025, 2000000000): 418.607978ms

fn main() {
　for (n, limit) in [(2025, 2000_0000), (2025, 20_0000_0000)] {
　　let start_time = std::time::Instant::now();
　　let answer = solve(n, limit);
　　let end_time = std::time::Instant::now();
　　println!("実行時間 solve({n}, {limit}): {:?}", end_time - start_time);

　　// 個数と最初と最後の検証
　　let (valid_len, valid_first, valid_last) = match (n, limit) {
　　　(2025, 2000_0000) => (1265, 30255, 19970000),
　　　(2025, 20_0000_0000) => (49942, 30255, 1999986740),
　　　_ => (0, 0, 0),
　　};
　　assert_eq!(answer.len(), valid_len);
　　assert_eq!(*answer.first().unwrap(), valid_first);
　　assert_eq!(*answer.last().unwrap(), valid_last);
　}
}

**デフォルトの名無しさん** · 2025/04/09(水) 14:40:43.48

>>737
AIも同じこと言ってた

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

>>738-739
出題時に作成した解答例

C++
https://ideone.com/y1YZlj
R
https://ideone.com/zvqAsg

と解の個数と最小値・最大値が一致するので正解だろう。

ローカルでコンパイルしようとしたら、

　error[E0425]: cannot find function `generate_primes` in this scope

と表示されコンパイルできなかったので、実行時間の比較はできなかった。

**デフォルトの名無しさん** · 2025/04/09(水) 22:57:11.84

>>741
すみません
素数の一覧を返すだけなので素数列挙でもライブラリ利用でも何でもいいのですが
例えばエラトステネスの篩ならこんな感じの関数で

// 素数の一覧を返す [2, 3, 5, 7, 11, ... , (最大max)]
fn generate_primes(max: usize) -> Vec<usize> {
　// maxの平方根までの素数の倍数を篩にかければ全ての素数が見つかる
　let limit = max.isqrt() + 1;
　let mut is_prime = vec![true; max + 1];
　is_prime[0] = false;
　is_prime[1] = false;
　// 偽初期値
　let mut prime = 1;
　// 次の素数を探す (前回の素数以降でtrueを探すと次の素数)
　while let Some(pos) = is_prime[(prime + 1)..limit].iter().position(|bool| *bool) {
　　prime += pos + 1;
　　// この素数の倍数をfalseにする【エラトステネスの篩】
　　is_prime[(prime << 1)..].iter_mut().step_by(prime).for_each(|bool| *bool = false);
　}
　// 素数一覧を返す (trueになるindex値が素数)
　is_prime.iter().enumerate().filter_map(|(index, bool)| bool.then_some(index)).collect()
}

**デフォルトの名無しさん** · 2025/04/09(水) 23:40:58.68

>>738-739, 742と>>741のC++を解の標準出力なしに変更したものの実行速度を比較したら、
前者の方が2000万以下では27%、20億以下では11%速かった。

**デフォルトの名無しさん** · 2025/04/09(水) 23:43:56.02

前者はどっち？
アルゴリズムが違うのかちょっと見てみる

**デフォルトの名無しさん** · 2025/04/09(水) 23:50:45.01

>>744
前者は>>738-739, 742のRustプログラム。後者 (C++プログラム) はvectorへの要素追加回数が
多いので時間が掛かっていそう。

**デフォルトの名無しさん** · 2025/04/09(水) 23:59:16.31

たしかにC++の20億だと数秒かかりますね
何がそんなに違うのかな

**デフォルトの名無しさん** · 2025/04/10(木) 00:43:03.90

vectorのメモリは必要分を最初に確保すると速くならない?
vectorの最初のサイズの初期値は要素10個分だったはず。11個目が追加されたら20個確保して全要素コピーんｓんてやってたら遅いよ

**デフォルトの名無しさん** · 2025/04/10(木) 02:19:18.58

ベクタはC++もRustも他でもほぼ同じ仕様で埋まると倍の新たなエリアを確保してコピー
これは2^n個が埋まった時点でそれ以前の累積コピー個数は
最悪の1個スタートでも1+2+4+ ... + 2^(n-2)+2^(n-1) =2^n - 1個しかない
つまりO(1)とみなせるため問題になることは少ない
言語による詳細な差もC++とRustならほぼ無いと思われる

一方で今回の20億以内で素数和が2025になる数を求める問題
C++版がRust版より約10倍遅くなってる原因は
・pushしていくベクタがRust版は1個でC++版は2026個のベクタを利用
・pushしていく回数がRust版は解の個数と同じ49942回でC++版は134621081回
ワーキングメモリ使用量の差が効いてる

**デフォルトの名無しさん** · 2025/04/10(木) 22:03:03.91

>>747
vector p[0]～p[S]のサイズの最大値4499個（20億以下では88876個）分のメモリを

　　for (auto &v : p) v.reserve(4499);

で最初に割り付けておくと、>>743ではRustの方が2000万以下で27%、20億以下で11%速かったのが、
2000万以下では差が縮まりRustの方が14%速く、20億以下では逆転しRustの方が20%遅くなった。
サイズの最大値は実行前には分からないから、上記の改変はあくまでもvectorのサイズ拡張が実行時間に
及ぼす影響を見るためのテストで、解答として使うことはできないが。

vectorのサイズ拡張は、新しいメモリ割り付けとそこへの要素コピーに掛かる時間によってだけではなく、
要素の格納アドレスが変わることによるキャッシュ有効率の低下によっても、速度低下をもたらしそう。

>>746, 748
どっちがどれだけ速いかは実行環境に依存するとはいえ、C++が20億で数秒とかRustより約10倍遅いと
いうのはいくら何でも遅すぎておかしいと思う。解の標準出力をなしにするのを忘れていたり、Windowsで
コンパイル後の実行ファイルの実行時間をPowerShellでmeasure-command {a.exe}のように計測して
ウィルス・チェックに要した時間も含まれていたりしない?

**デフォルトの名無しさん** · 2025/04/11(金) 07:38:20.09

>>738 に手を加えて10倍速くしてみた
fn solve(n: usize, limit: usize) -> Vec<usize> {
　let mut answer = Vec::new();
　let mut pnt = generate_primes(n).windows(2).rev().map(|s| (s[1], s[0], 0, 0)).collect::<Vec<_>>();
　let (mut ci, mut cn, mut ct) = (0, n, 1_usize);
　'advance: loop {
　　pnt[ci..].iter_mut().for_each(|(_p, _q, n, t)| (*n, *t) = (cn, ct));
　　if cn & 1 == 0 && ct.leading_zeros() >= (cn >> 1) as u32 {
　　　ct <<= cn >> 1; if ct <= limit { answer.push(ct); }
　　}
　　'back: for (i, (p, q, n, t)) in pnt.iter_mut().enumerate().rev() {
　　　'again: loop {
　　　　if *n < *p { continue 'back; }
　　　　*n -= *p; *t *= *p;
　　　　if *n ==1 || *t > limit { continue 'back; }
　　　　if *n == 0 { answer.push(*t); continue 'back; }
　　　　if *q > 3 {
　　　　　let mut tt = *t * (*n % *q);
　　　　　for _ in 0..(*n / *q) { tt *= *q; if tt > limit { continue 'again; } }
　　　　}; break 'again;
　　　}; (ci, cn, ct) = (i, *n, *t); continue 'advance;
　　}; break 'advance;
　}; answer.sort(); answer
}

**デフォルトの名無しさん** · 2025/04/11(金) 22:07:48.99

すごいな
アルゴリズムの違いでそんなに速度差変わるものなんだな

**デフォルトの名無しさん** · 2025/04/11(金) 22:44:47.89

>>750
これはとても速いな。ローカルで実行してみたら、>>738のRustプログラムと比較して
2000万以下で16倍、20億以下で55倍の速さだった。

**デフォルトの名無しさん** · 2025/04/12(土) 09:11:24.51

>>712
@Wolfram
https://ideone.com/4xyb1s

**デフォルトの名無しさん** · 2025/04/12(土) 21:18:53.69

>>741のC++プログラムは for (int i = S; i >= 2; i--) のループの最後のi = 2の場合を
ループの外に出して最適化 (p[S]以外のp[_]への要素追加をしないように) するだけで、
20億以下で解の出力なしのときの実行時間が元のプログラムの半分未満になるな。

https://ideone.com/RtTEO2 (1.02秒)
　↓
https://ideone.com/1O04wl (0.44秒)

**デフォルトの名無しさん** · 2025/04/12(土) 21:26:41.27

>>754
それに気づいたけど
まだ>>750と比べて20倍遅いからメモ化の方針が徒となってるのかな

**753** · 2025/04/13(日) 11:09:12.37

>>712
初Rust
https://ideone.com/aaj5D8

**デフォルトの名無しさん** · 2025/04/13(日) 23:46:14.76

>>756
遅い原因は長さ2000万のベクタ利用？

**デフォルトの名無しさん** · 2025/04/13(日) 23:53:41.46

配列にするとどうかね

**デフォルトの名無しさん** · 2025/04/17(木) 00:27:46.72

素因数和2025のお題の3系統のコードを読み解いてみた

>>756
2000万まで各々で素因数の和を求めて2025になるかを確認する方法。
ただし各数の素因数分解を工夫せずにすると大変なので、
各数の最小素因数(SPF)を先に一気にエラトステネスの篩で求めてる。
それを用いれば各数の素因数分解はその分解数回の割算だけで求まる。

ただしそのSPF表のために長さ2000万のベクタを用いている。
もし20億までなら32bit✕20億で8GBが許容できるとしても、
あるいはこのSPF一覧のベクタを用いなくても、
20億回の処理を劇的に減らす枝刈り方法を組み込めないと厳しい。
2000万までの計算でも一番遅い。

**デフォルトの名無しさん** · 2025/04/17(木) 00:29:06.02

>>741
2000万個すべてを素因数分解する方法とは逆に、
2025以下の素数の組み合わせを調べていく方法。
そのうち和が2025になる組み合わせの積が各解となる。

それを効率よく求めるために2025(+1)個のベクタのベクタpを用意している。
つまり和がsumとなる時の積をp[sum]に記録していく。
効率面からの仮の初期値p[0]に1を入れて、各素数iについて降順に、
ベクタp[j]にxがある時、ベクタp[i+j]にx*iをpushしていく。
ここでjの上限は 2025 - i、処理するxの上限は 2000万 / i の枝刈りができる。
最終的にベクタp[2025]の一覧が解となる。
2025個のベクタを用いることが長所および短所になっている。

この改良版>>754では、最後の素数2だけ特別扱いすることで倍速にしている。

**デフォルトの名無しさん** · 2025/04/17(木) 00:32:14.51

>>738
これも2025以下の素数を組み合わせて和が2025になる解を調べる方法。
解一覧を収めるベクタ以外は、固定の長さ305のベクタのみが使われている。
この長さの 305 とは2025以下～3以上の素数[2017, 2011, ... 5, 3]の数になってる。
各素数の冪乗の和 2017^e2017 + 2011^e2011 + ... + 5^e5 + 3^e3 及び積を計算していくが、
各指数のe2017などは解に不要なので使われておらず、
各冪乗の和自体も不要なので2025までの残りの数が使われていて、
固定長ベクタの値は(素数, 残りの数, ここまでの積)の3つ組となっている。
その素数を1つ使うと残りの数が減算されてて積が乗算されるのを繰り返していく。
素数2だけ特別扱いされており、残りの数の半分だけ左シフトすると解の積が出来上がる。

各if～continueが枝刈りとなっていて、残りの下限(=和の上限)や積の上限などがある
この改良版>>750では、次の素数以降の組み合わせで起き得る積の下限で枝刈りしている。
例えば7以下の素数で残り21ならば積の下限は7*7*7=343となるため、
ここまでの積に343を掛けた値が2000万(または20億)を超えていれば枝刈りできるようだ。

このアルゴリズムは作業メモリが固定で小さく常にL1キャッシュに乗り有利と思われる点と、
様々な枝刈りがしやすく処理する組み合わせを大きく減らしている点により、
他のアルゴリズムより桁違いに高速になっていると推測される。

**デフォルトの名無しさん** · 2025/05/03(土) 06:56:07.77

お題：0か1のランダムな要素を持つW*Hの行列と二点の座標x, yとp, qが入力される
直線(x,y)→(p, q) を行列内で要素1に当たらないように任意の位置に合同変換したい
合同変換できる座標があればその二点の座標を出力し、なければ「なし」と出力せよ

**デフォルトの名無しさん** · 2025/05/03(土) 14:00:53.01

？

**デフォルトの名無しさん** · 2025/05/03(土) 14:59:51.97

行列の1は格子点上の印なのかクロスワードの黒マスなのか
(x,y)、(p,q)は任意の点なのか格子点なのか
合同変換される直線(x,y)→(p,q)は実は線分だったりしないのか

無限の可能性を感じさせるお題だな

**デフォルトの名無しさん** · 2025/05/03(土) 15:10:32.79

検証用のデータを書いていないお題は失格
入力例とその時の出力例が必要
もし出力が複数個で長いならその特例の一部や個数など

**デフォルトの名無しさん** · 2025/06/21(土) 16:41:25.25

お題
2次元の配列があったときに
一番左上を起点として右上方向、左下方向、右上方向…
というふうに斜めに配列の要素をたどることを
ジグザグスキャンと名付けます

たとえば、3 * 3の配列の場合は次の順番で配列の要素にアクセスします

(1, 2, 6)
(3, 5, 7)
(4, 8, 9)

二次元の配列を入力としてジグザグスキャンを行ってください
結果を1次元の配列として出力してください

例
入力: (A, B, C), (D, E, F), (G, H, I)
出力: (A, B, D, G, E, C, F, H, I)

入力: (A, B, C), (D, E, F)
出力: (A, B, D, E, C, F)

入力: (A, B), (C, D), (E, F)
出力: (A, B, C, E, D, F)

**デフォルトの名無しさん** · 2025/06/21(土) 19:44:57.30

>>766
R
https://wandbox.org/permlink/JoDE3h6F6k7gKbPs

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

>>766
Rust

fn f<T: Clone, const M: usize, const N: usize>(input: &[[T; N]; M]) -> Vec<T> {
　let mut output = Vec::<T>::new();
　for x in 0..(M + N - 1) {
　　let start = if x < N { 0 } else { x + 1 - N };
　　let end = if x < M { x } else { M - 1 };
　　let iter = (start..=end).map(|m| input[m][x - m].clone());
　　if x & 1 == 1 {
　　　output.extend(iter.clone());
　　} else {
　　　output.extend(iter.rev());
　　}
　}
　output
}

fn main() {
　assert_eq!(f(&[['A', 'B', 'C'], ['D', 'E', 'F'], ['G', 'H', 'I']]), ['A', 'B', 'D', 'G', 'E', 'C', 'F', 'H', 'I']);
　assert_eq!(f(&[['A', 'B', 'C'], ['D', 'E', 'F']]), ['A', 'B', 'D', 'E', 'C', 'F']);
　assert_eq!(f(&[['A', 'B'], ['C', 'D'], ['E', 'F']]), ['A', 'B', 'C', 'E', 'D', 'F']);
}

**デフォルトの名無しさん** · 2025/06/29(日) 20:45:32.73

お題：W*Hの行列に迷路を生成してください（アルゴリズムは任意）

**デフォルトの名無しさん** · 2025/06/29(日) 21:58:43.69

>>769
解がないため不成立
inputとoutputの事例などがないため不成立

**デフォルトの名無しさん** · 2025/07/25(金) 12:30:11.02

【問題】
整数のリストが与えられたとき、そのリストを昇順に安定ソートした時の各要素のインデクス（0開始）を対応させたリストを作成せよ

【例】
入力： 1 100 10 10000 1000
出力： 0 2 1 4 3

入力： 3 1 4 1 5 9 2
出力： 3 0 4 1 5 6 2

入力： 0 1 0 1 0 1 0 1
出力： 0 4 1 5 2 6 3 7

実際に必要になって実装したけどスマートな方法があったら知りたい

**デフォルトの名無しさん** · 2025/07/25(金) 20:46:23.28

>>771
例がおかしい
わかりやすい最後の例で示すと

入力： 0 1 0 1 0 1 0 1
出力： 0 4 1 5 2 6 3 7　間違い
出力： 0 2 4 6 1 3 5 7　正解

安定ソートなので同値は順序を保ってこうなる

**デフォルトの名無しさん** · 2025/07/25(金) 21:30:28.86

>>771 C++ 特にひねりは無い
https://ideone.com/mTHn46

**デフォルトの名無しさん** · 2025/07/26(土) 12:26:55.07

>>772
出題者だけど「各要素の移動先のインデクス」って書いた方がよかったか
文言削りすぎた

**デフォルトの名無しさん** · 2025/07/26(土) 15:08:13.56

>>771
SQL

select
　row_number() over(order by arrayValue, arrayIndex) - 1
from
　arrayTable
order by
　arrayIndex

**デフォルトの名無しさん** · 2025/07/26(土) 19:25:22.74

>>771
Java 24
https://text.is/4Z27R

**デフォルトの名無しさん** · 2025/07/27(日) 10:09:36.80

>>771 ocaml
https://ideone.com/E7eFPC

>>771 octave
https://ideone.com/KkHu9S

>>771 ruby
https://ideone.com/pPIxcE

**デフォルトの名無しさん** · 2025/07/27(日) 17:05:48.29

>>771 c
https://ideone.com/6Wn3eD

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

>>771 ruby 2.6以降？
sorti = ->a {a.map.with_index.sort.map &:last}
f = sorti << sorti
g = method(:p) << f

**デフォルトの名無しさん** · 2025/07/27(日) 20:19:17.79

>>771
R
https://ideone.com/ctaQC5

統計用言語だけあってライブラリ関数rankを呼び出すだけ。ties.method = "min"を指定すれば
同値を同順位（例えば2番目の例では出力が3 0 4 0 5 6 2となる）にもできる。

**デフォルトの名無しさん** · 2025/07/27(日) 21:43:59.43

>>771
Rust
既に色々と出ているため別の観点からのコード
一時作業メモリ最小＆ソートは1回＆ジェネリック

fn f<T: std::cmp::Ord>(input: &[T]) -> Vec<usize> {
　let len = input.len();

　// ポジションのリスト [0, 1, 2, 3, ... , len-1] を作成
　let mut pos_list: Vec<usize> = (0..len).collect();
　// inputを利用してそのポジションだけをソート
　pos_list.sort_by_key(|&pos| &input[pos]);

　// 返すべきランクのリスト
　let mut rank_list: Vec<usize> = vec![0; len];
　// ポジション⇔ランクは逆写像なのでソートは不要
　(0..len).for_each(|rank| rank_list[pos_list[rank]] = rank);
　rank_list
}

fn main() {
　assert_eq!(f(&[1, 100, 10, 10000, 1000]), [0, 2, 1, 4, 3]);
　assert_eq!(f(&[3, 1, 4, 1, 5, 9, 2]), [3, 0, 4, 1, 5, 6, 2]);
　assert_eq!(f(&[0, 1, 0, 1, 0, 1, 0, 1]), [0, 4, 1, 5, 2, 6, 3, 7]);
}

**777** · 2025/07/27(日) 22:54:22.66

>>771 octave ソート一回
https://ideone.com/dTRKBs

>>771 ruby 2.5 ソート一回
https://ideone.com/akDhpS

警備員[Lv.11] · 2025/07/28(月) 23:30:37.16

>>771
>>776をKotlinに変換してKotlinらしくなるように色々省略しただけのもの。
やはり最初からラムダとか考慮されている言語だと色々省略できて分り易くなるね。
https://paiza.io/projects/0Dhknk4mUHrMqtuwzCDAxQ

**デフォルトの名無しさん** · 2025/07/29(火) 00:12:31.56

>>771
Rust
https://ideone.com/jYX2ws

バイナリヒープ使うとソート過程で直接リスト作れるけどコード量増えるしヒープソート遅いから実用性は微妙か
C言語ならありかもしれない

**デフォルトの名無しさん** · 2025/07/30(水) 21:50:10.50

>>771 java
https://ideone.com/Z8Q9Dk

**デフォルトの名無しさん** · 2025/07/31(木) 14:56:29.97

>> 771
java
>> 785氏のデータも加えてみた。
https://ideone.com/vzXoGd

ideoneのjavaはバージョン古いのか...
ま、通りがかりにこのスレみつけたのでちょっと書いただけ。

**デフォルトの名無しさん** · 2025/07/31(木) 18:54:11.86

ち、勘が鈍った。＞＞もつけ間違えるし、sage忘れるし。

**785** · 2025/07/31(木) 21:15:09.63

>>771 java compose乱用
https://ideone.com/TBTZgj

**デフォルトの名無しさん** · 2025/08/03(日) 22:00:37.87

>>771
java >>786を修正。javaが古いねぇ。
https://ideone.com/Z3jS0P

**デフォルトの名無しさん** · 2025/08/04(月) 22:42:57.64

>>771
java >>789を修正。何度もすいませんね。classをメソッド内に移動。
https://ideone.com/BV5FXe

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

>>771
java >>790修正。classだったらメソッドの引数がみえるので修正。recordではできない。
https://ideone.com/r6T4Zf

**デフォルトの名無しさん** · 2025/08/05(火) 01:04:23.30

class ValueWithIndex<U /*extends Comparable<U>*/> implements Comparable<ValueWithIndex<T>> {
ジェネリックは難しい。上のextends Comparable<U>は無くてもよいのだが、無駄でも明記したほうがよさそうなので、
ソースではそうした。
明記しなくとも、Uは正しく推測されているようだ。

**デフォルトの名無しさん** · 2025/08/06(水) 17:17:53.29

>>771
JavaScript
https://paiza.io/projects/xtvAB2LXpLg0XOjzBHfl2w

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

これからはメソッドの時代

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

>>771 scala
https://ideone.com/iycaKk

>>771 swift
https://ideone.com/de2iOi

**デフォルトの名無しさん** · 2025/08/11(月) 20:38:34.09

>>771 dart 2.3
https://ideone.com/XLI2nC
・拡張メソッドはDart2.7から
・ideone現状はDart (dart 2.3.0)

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

>>771
PowerShell 6以降

function rank($a)
{
　　$n = $a.length
　　$r = [int[]]::new($n)
　　if ($n) {0..($n - 1) | sort-object -stable {$a[$_]} |% {$i = 0} {$r[$_] = $i++}}
　　$r
}

function PrintArray($a)
{
　　if ($a.length -le 1) {return $a}
　　"[$(($a |% {PrintArray $_}) -join ", ")]"
}

$q =
　　(1, 100, 10, 10000, 1000),
　　(3, 1, 4, 1, 5, 9, 2),
　　(0, 1, 0, 1, 0, 1, 0, 1),
　　@(),
　　1,
　　((1, 1), (1, 1), (1, 0, 1), (1, 0))

$q |% {
　　"入力: $(PrintArray $_)"
　　"出力: $(PrintArray (rank $_))"
　　""
}

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

-- 実行結果 --
入力: [1, 100, 10, 10000, 1000]
出力: [0, 2, 1, 4, 3]

入力: [3, 1, 4, 1, 5, 9, 2]
出力: [3, 0, 4, 1, 5, 6, 2]

入力: [0, 1, 0, 1, 0, 1, 0, 1]
出力: [0, 4, 1, 5, 2, 6, 3, 7]

入力:
出力:

入力: 1
出力: 0

入力: [[1, 1], [1, 1], [1, 0, 1], [1, 0]]
出力: [2, 3, 1, 0]

**デフォルトの名無しさん** · 2025/08/16(土) 01:44:59.97

【問題Ａ】
１～９を１つずつ使用して表される９桁の数Anは全部で9!（＝362880）個存在する。
整数n（1≦n≦362880）が与えられたとき、n番目に小さいAnを求めよ。

（例）
　1 → 123456789
　2 → 123456798
　3 → 123456879
　123456 → 416589732
　234567 → 684753219
　362880 → 987654321

【問題Ｂ】
１～４を３つずつ使用して表される12桁の数Bnは全部で12!/(3!)^4（＝369600）個存在する。
整数n（1≦n≦369600）が与えられたとき、n番目に小さいBnを求めよ。

（例）
　1 → 111222333444
　2 → 111222334344
　3 → 111222334434
　123456 → 222331434114
　234567 → 324424331112
　369600 → 444333222111

※求める数値は文字列または各桁の数の配列による表現も可能とする（123⇔"123"⇔[1,2,3]）

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

>>799　Rust　愚直にn回まわし

use itertools::Itertools; // for tuple_windows()

fn f(init: &str, n: usize) -> String {
　let mut list = init.chars().rev().collect::<Vec<_>>();
　for _ in 1..n {
　　if let Some((pre_index, (_, old))) = list.iter().tuple_windows().enumerate().find(|(_, (pre, cur))| pre > cur) {
　　　let old_index = pre_index + 1;
　　　let (new_index, _) = list.iter().enumerate().find(|(_, cur)| cur > &old).unwrap();
　　　list.swap(old_index, new_index);
　　　list[..old_index].reverse();
　　}
　}
　list.into_iter().rev().collect()
}

fn main() {
　assert_eq!(f("123456789", 1), "123456789");
　assert_eq!(f("123456789", 2), "123456798");
　assert_eq!(f("123456789", 3), "123456879");
　assert_eq!(f("123456789", 123456), "416589732");
　assert_eq!(f("123456789", 234567), "684753219");
　assert_eq!(f("123456789", 362880), "987654321");
　assert_eq!(f("111222333444", 1), "111222333444");
　assert_eq!(f("111222333444", 2), "111222334344");
　assert_eq!(f("111222333444", 3), "111222334434");
　assert_eq!(f("111222333444", 123456), "222331434114");
　assert_eq!(f("111222333444", 234567), "324424331112");
　assert_eq!(f("111222333444", 369600), "444333222111");
}

**デフォルトの名無しさん** · 2025/08/16(土) 19:14:21.11

>>799 の問題A
1からnまでの自然数を並べてできるi番目の順列を求める関数を前に作って持っていたので、
それを流用したらすぐできた（元の関数はBigIntとiの範囲外エラーにも対応）。

R
https://ideone.com/hMTf2k
C++
https://ideone.com/ZiU5Aa

**デフォルトの名無しさん** · 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;
}