プログラミングのお題スレ Part22 (863ﾚｽ)

プログラミングのお題スレ Part22 http://mevius.5ch.net/test/read.cgi/tech/1691038333/

上下前次1-新
通常表示 512ﾊﾞｲﾄ分割 ﾚｽ栞
抽出解除 ﾚｽ栞

---

ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡

---

799: デフォルトの名無しさん [sage] 2025/08/16(土) 01:44:59.97 ID:VU+jlz0U 【問題Ａ】 １～９を１つずつ使用して表される９桁の数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]） http://mevius.5ch.net/test/read.cgi/tech/1691038333/799

800: デフォルトの名無しさん [sage] 2025/08/16(土) 13:16:59.50 ID:MUbLd8/3 >>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"); } http://mevius.5ch.net/test/read.cgi/tech/1691038333/800

801: デフォルトの名無しさん [] 2025/08/16(土) 19:14:21.11 ID:kN4EEg8M >>799 の問題A 1からnまでの自然数を並べてできるi番目の順列を求める関数を前に作って持っていたので、 それを流用したらすぐできた（元の関数はBigIntとiの範囲外エラーにも対応）。 R https://ideone.com/hMTf2k C++ https://ideone.com/ZiU5Aa http://mevius.5ch.net/test/read.cgi/tech/1691038333/801

802: デフォルトの名無しさん [] 2025/08/16(土) 20:29:06.33 ID:kN4EEg8M >>799 の問題B R https://ideone.com/SdWBKf C++ https://ideone.com/90BpGt http://mevius.5ch.net/test/read.cgi/tech/1691038333/802

803: デフォルトの名無しさん [] 2025/08/16(土) 21:32:58.04 ID:kN4EEg8M >>799 >>802 のC++のithDuplicatedPermutation関数は引数が別の値（例えばn = 5, m = 3）のとき 正しく計算できなかったので修正。Rの方はintではなくdoubleで計算しているので問題ない。 https://ideone.com/uH8dpO http://mevius.5ch.net/test/read.cgi/tech/1691038333/803

805: デフォルトの名無しさん [sage] 2025/08/17(日) 12:07:33.92 ID:R1ye1QDy >>799 ruby https://ideone.com/o2Qlkr >>799 c https://ideone.com/Q4XNBb http://mevius.5ch.net/test/read.cgi/tech/1691038333/805

806: 805 [sage] 2025/08/17(日) 15:08:29.44 ID:R1ye1QDy >>799 ruby 若干の改善 https://ideone.com/oavxRo >>799 c 若干の改善 https://ideone.com/34A07H http://mevius.5ch.net/test/read.cgi/tech/1691038333/806

809: デフォルトの名無しさん [] 2025/08/19(火) 21:08:19.27 ID:zFi0pntB >>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 http://mevius.5ch.net/test/read.cgi/tech/1691038333/809

811: 806 [sage] 2025/08/21(木) 22:19:54.42 ID:fAlkh9Aq >>799 ruby https://ideone.com/3TW9Vr ・問題A時に若干端折る http://mevius.5ch.net/test/read.cgi/tech/1691038333/811

812: デフォルトの名無しさん [] 2025/08/21(木) 23:15:48.39 ID:0KQ1xtxb >>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回）。 http://mevius.5ch.net/test/read.cgi/tech/1691038333/812

813: デフォルトの名無しさん [] 2025/08/22(金) 01:14:43.39 ID:6LYRfbyj >>799 Java https://paiza.io/projects/F5kCIBu6BOVB9QTX7hHWMg http://mevius.5ch.net/test/read.cgi/tech/1691038333/813

814: デフォルトの名無しさん [sage] 2025/08/22(金) 06:55:21.34 ID:qlaiAqZd >>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() } http://mevius.5ch.net/test/read.cgi/tech/1691038333/814

816: 811 [sage] 2025/08/22(金) 20:26:43.82 ID:m9vhyo0Z >>799 ruby https://ideone.com/vvp0kq ・問題A時に全体的な規則性に着目 ・部分的に着目しちゃったのが>>811 ・何も工夫を入れなかったのが>>806 http://mevius.5ch.net/test/read.cgi/tech/1691038333/816

817: 816 [sage] 2025/08/23(土) 20:27:40.18 ID:uyhDG+iz >>799 ruby 問題Bもケア https://ideone.com/od17Hn http://mevius.5ch.net/test/read.cgi/tech/1691038333/817

818: デフォルトの名無しさん [sage] 2025/08/23(土) 21:01:55.02 ID:gxRFdG35 >>799 java https://ideone.com/qRTy1Z http://mevius.5ch.net/test/read.cgi/tech/1691038333/818

819: 817 [sage] 2025/08/23(土) 23:26:24.12 ID:uyhDG+iz >>799 java https://ideone.com/78psr6 http://mevius.5ch.net/test/read.cgi/tech/1691038333/819

821: 819 [sage] 2025/08/25(月) 00:28:39.45 ID:IbSJkZLt >>799 java Iterable<int[]> https://ideone.com/NRTZpa http://mevius.5ch.net/test/read.cgi/tech/1691038333/821

822: デフォルトの名無しさん [sage] 2025/08/27(水) 00:40:48.46 ID:AbNZa8yo >>799 ocaml https://ideone.com/1Jx1Q8 >>799 scheme (chicken 4.13) https://ideone.com/n7pIFw http://mevius.5ch.net/test/read.cgi/tech/1691038333/822

823: デフォルトの名無しさん [sage] 2025/08/27(水) 21:02:12.94 ID:AbNZa8yo >>799 octave https://ideone.com/RH6xXb http://mevius.5ch.net/test/read.cgi/tech/1691038333/823

825: 821 [sage] 2025/08/28(木) 21:01:46.43 ID:mnaa+hsk >>799 java https://ideone.com/aKkfqN ・next()ごとに複製しない版。する版は >>821 ・hasNext()側で次を準備。next()側なのは >>821 http://mevius.5ch.net/test/read.cgi/tech/1691038333/825

---

ﾒﾓ帳

(0/65535文字)

---

上下前次1-新書関写板覧索設栞歴

---

ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

Google検索

Wikipedia

---

ぬこの手 ぬこTOP 0.043s