プログラミングのお題スレ Part22 (863ﾚｽ)
上下前次1-新
1(4): デフォルトの名無しさん [] 2023/08/03(木) 13:52:13.20 ID:/xW45k0z(1) AAS
プログラミングのお題スレです。
【出題と回答例】
1 名前：デフォルトの名無しさん
お題：お題本文
2 名前：デフォルトの名無しさん
>>1 使用言語
回答本文
結果がある場合はそれも
【ソースコードが長くなったら】 (オンラインでコードを実行できる)
https://ideone.com/
http://codepad.org/
http://compileonline.com/
http://rextester.com/runcode
https://runnable.com/
https://code.hackerearth.com/
http://melpon.org/wandbox
https://paiza.io/
宿題は宿題スレがあるのでそちらへ。
※前スレ
プログラミングのお題スレ Part21
2chｽﾚ:tech
764: デフォルトの名無しさん [sage] 2025/05/03(土) 14:59:51.97 ID:LoSO6jC9(1) AAS
行列の1は格子点上の印なのかクロスワードの黒マスなのか
(x,y)、(p,q)は任意の点なのか格子点なのか
合同変換される直線(x,y)→(p,q)は実は線分だったりしないのか
無限の可能性を感じさせるお題だな
765: デフォルトの名無しさん [sage] 2025/05/03(土) 15:10:32.79 ID:OINldK7L(1) AAS
検証用のデータを書いていないお題は失格
入力例とその時の出力例が必要
もし出力が複数個で長いならその特例の一部や個数など
766(2): デフォルトの名無しさん [] 2025/06/21(土) 16:41:25.25 ID:muNvYhtO(1) AAS
お題
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)
767: デフォルトの名無しさん [] 2025/06/21(土) 19:44:57.30 ID:jAwJC0YX(1) AAS
>>766
R
https://wandbox.org/permlink/JoDE3h6F6k7gKbPs
768: デフォルトの名無しさん [sage] 2025/06/21(土) 23:05:10.33 ID:awm9eire(1) AAS
>>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']);
}
769(1): デフォルトの名無しさん [sage] 2025/06/29(日) 20:45:32.73 ID:f7vmTtNq(1) AAS
お題：W*Hの行列に迷路を生成してください（アルゴリズムは任意）
770: デフォルトの名無しさん [sage] 2025/06/29(日) 21:58:43.69 ID:HlaloW8+(1) AAS
>>769
解がないため不成立
inputとoutputの事例などがないため不成立
771(22): デフォルトの名無しさん [sage] 2025/07/25(金) 12:30:11.02 ID:CjDQVF2B(1) AAS
【問題】
整数のリストが与えられたとき、そのリストを昇順に安定ソートした時の各要素のインデクス（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
実際に必要になって実装したけどスマートな方法があったら知りたい
772(1): デフォルトの名無しさん [sage] 2025/07/25(金) 20:46:23.28 ID:dyl0C+2U(1) AAS
>>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 正解
安定ソートなので同値は順序を保ってこうなる
773: デフォルトの名無しさん [sage] 2025/07/25(金) 21:30:28.86 ID:Z69qH9vG(1) AAS
>>771 C++ 特にひねりは無い
https://ideone.com/mTHn46
774: デフォルトの名無しさん [sage] 2025/07/26(土) 12:26:55.07 ID:xCVVpUlx(1) AAS
>>772
出題者だけど「各要素の移動先のインデクス」って書いた方がよかったか
文言削りすぎた
775: デフォルトの名無しさん [] 2025/07/26(土) 15:08:13.56 ID:T78ZrTu7(1/2) AAS
>>771
SQL
select
row_number() over(order by arrayValue, arrayIndex) - 1
from
arrayTable
order by
arrayIndex
776(1): デフォルトの名無しさん [] 2025/07/26(土) 19:25:22.74 ID:T78ZrTu7(2/2) AAS
>>771
Java 24
https://text.is/4Z27R
777(1): デフォルトの名無しさん [sage] 2025/07/27(日) 10:09:36.80 ID:vFJ24xnO(1/3) AAS
>>771 ocaml
https://ideone.com/E7eFPC
>>771 octave
https://ideone.com/KkHu9S
>>771 ruby
https://ideone.com/pPIxcE
778: デフォルトの名無しさん [sage] 2025/07/27(日) 17:05:48.29 ID:vFJ24xnO(2/3) AAS
>>771 c
https://ideone.com/6Wn3eD
779: デフォルトの名無しさん [sage] 2025/07/27(日) 17:08:58.25 ID:vFJ24xnO(3/3) AAS
>>771 ruby 2.6以降？
sorti = ->a {a.map.with_index.sort.map &:last}
f = sorti << sorti
g = method(:p) << f
780: デフォルトの名無しさん [] 2025/07/27(日) 20:19:17.79 ID:uFbo+/2v(1) AAS
>>771
R
https://ideone.com/ctaQC5
統計用言語だけあってライブラリ関数rankを呼び出すだけ。ties.method = "min"を指定すれば
同値を同順位（例えば2番目の例では出力が3 0 4 0 5 6 2となる）にもできる。
781: デフォルトの名無しさん [sage] 2025/07/27(日) 21:43:59.43 ID:w39E9j9Q(1) AAS
>>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]);
}
782: 777 [sage] 2025/07/27(日) 22:54:22.66 ID:YfUjoiLt(1) AAS
>>771 octave ソート一回
https://ideone.com/dTRKBs
>>771 ruby 2.5 ソート一回
https://ideone.com/akDhpS
783: 警備員[Lv.11] [] 2025/07/28(月) 23:30:37.16 ID:uO5vEij8(1) AAS
>>771
>>776をKotlinに変換してKotlinらしくなるように色々省略しただけのもの。
やはり最初からラムダとか考慮されている言語だと色々省略できて分り易くなるね。
https://paiza.io/projects/0Dhknk4mUHrMqtuwzCDAxQ
784: デフォルトの名無しさん [sage] 2025/07/29(火) 00:12:31.56 ID:9AXsNEm+(1) AAS
>>771
Rust
https://ideone.com/jYX2ws
バイナリヒープ使うとソート過程で直接リスト作れるけどコード量増えるしヒープソート遅いから実用性は微妙か
C言語ならありかもしれない
785(1): デフォルトの名無しさん [sage] 2025/07/30(水) 21:50:10.50 ID:Ug40aZKP(1) AAS
>>771 java
https://ideone.com/Z8Q9Dk
786(1): デフォルトの名無しさん [] 2025/07/31(木) 14:56:29.97 ID:cLL+G38O(1/2) AAS
>> 771
java
>> 785氏のデータも加えてみた。
https://ideone.com/vzXoGd
ideoneのjavaはバージョン古いのか...
ま、通りがかりにこのスレみつけたのでちょっと書いただけ。
787: デフォルトの名無しさん [] 2025/07/31(木) 18:54:11.86 ID:cLL+G38O(2/2) AAS
ち、勘が鈍った。＞＞もつけ間違えるし、sage忘れるし。
788: 785 [sage] 2025/07/31(木) 21:15:09.63 ID:R3hgrYP8(1) AAS
>>771 java compose乱用
https://ideone.com/TBTZgj
789(1): デフォルトの名無しさん [sage] 2025/08/03(日) 22:00:37.87 ID:1jv9m6G7(1) AAS
>>771
java >>786を修正。javaが古いねぇ。
https://ideone.com/Z3jS0P
790(1): デフォルトの名無しさん [sage] 2025/08/04(月) 22:42:57.64 ID:A9zbJQ8U(1/2) AAS
>>771
java >>789を修正。何度もすいませんね。classをメソッド内に移動。
https://ideone.com/BV5FXe
791: デフォルトの名無しさん [sage] 2025/08/04(月) 23:09:28.79 ID:A9zbJQ8U(2/2) AAS
>>771
java >>790修正。classだったらメソッドの引数がみえるので修正。recordではできない。
https://ideone.com/r6T4Zf
792: デフォルトの名無しさん [sage] 2025/08/05(火) 01:04:23.30 ID:wgx4FmLX(1) AAS
class ValueWithIndex<U /*extends Comparable<U>*/> implements Comparable<ValueWithIndex<T>> {
ジェネリックは難しい。上のextends Comparable<U>は無くてもよいのだが、無駄でも明記したほうがよさそうなので、
ソースではそうした。
明記しなくとも、Uは正しく推測されているようだ。
793: デフォルトの名無しさん [] 2025/08/06(水) 17:17:53.29 ID:qE4NV2ND(1) AAS
>>771
JavaScript
https://paiza.io/projects/xtvAB2LXpLg0XOjzBHfl2w
794: デフォルトの名無しさん [] 2025/08/07(木) 07:21:55.28 ID:W/yAWgo4(1) AAS
これからはメソッドの時代
795: デフォルトの名無しさん [sage] 2025/08/10(日) 23:18:32.78 ID:FODtZCg5(1) AAS
>>771 scala
https://ideone.com/iycaKk
>>771 swift
https://ideone.com/de2iOi
796: デフォルトの名無しさん [sage] 2025/08/11(月) 20:38:34.09 ID:frWpQyFA(1) AAS
>>771 dart 2.3
https://ideone.com/XLI2nC
・拡張メソッドはDart2.7から
・ideone現状はDart (dart 2.3.0)
797: デフォルトの名無しさん [] 2025/08/12(火) 21:05:08.06 ID:uRUBTkGF(1/2) AAS
>>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 $_))"
""
}
798: デフォルトの名無しさん [] 2025/08/12(火) 21:05:40.60 ID:uRUBTkGF(2/2) AAS
-- 実行結果 --
入力: [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]
799(20): デフォルトの名無しさん [sage] 2025/08/16(土) 01:44:59.97 ID:VU+jlz0U(1/2) AAS
【問題Ａ】
１～９を１つずつ使用して表される９桁の数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]）
800(1): デフォルトの名無しさん [sage] 2025/08/16(土) 13:16:59.50 ID:MUbLd8/3(1) AAS
>>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");
}
801: デフォルトの名無しさん [] 2025/08/16(土) 19:14:21.11 ID:kN4EEg8M(1/3) AAS
>>799 の問題A
1からnまでの自然数を並べてできるi番目の順列を求める関数を前に作って持っていたので、
それを流用したらすぐできた（元の関数はBigIntとiの範囲外エラーにも対応）。
R
https://ideone.com/hMTf2k
C++
https://ideone.com/ZiU5Aa
802(3): デフォルトの名無しさん [] 2025/08/16(土) 20:29:06.33 ID:kN4EEg8M(2/3) AAS
>>799 の問題B
R
https://ideone.com/SdWBKf
C++
https://ideone.com/90BpGt
803(1): デフォルトの名無しさん [] 2025/08/16(土) 21:32:58.04 ID:kN4EEg8M(3/3) AAS
>>799
>>802 のC++のithDuplicatedPermutation関数は引数が別の値（例えばn = 5, m = 3）のとき
正しく計算できなかったので修正。Rの方はintではなくdoubleで計算しているので問題ない。
https://ideone.com/uH8dpO
804(1): デフォルトの名無しさん [sage] 2025/08/16(土) 21:46:08.81 ID:VU+jlz0U(2/2) AAS
32bitだと階乗は12!が限界
805(1): デフォルトの名無しさん [sage] 2025/08/17(日) 12:07:33.92 ID:R1ye1QDy(1/2) AAS
>>799 ruby
https://ideone.com/o2Qlkr
>>799 c
https://ideone.com/Q4XNBb
806(2): 805 [sage] 2025/08/17(日) 15:08:29.44 ID:R1ye1QDy(2/2) AAS
>>799 ruby 若干の改善
https://ideone.com/oavxRo
>>799 c 若干の改善
https://ideone.com/34A07H
807: デフォルトの名無しさん [sage] 2025/08/17(日) 15:21:28.95 ID:OrBxx4uG(1) AAS
ソートが消えて>>800と同じアルゴリズムになったね
808(1): デフォルトの名無しさん [] 2025/08/17(日) 20:40:30.84 ID:bUKuWE64(1) AAS
>>804
確かにそうだった。15!も14!もintの範囲内に収まらない。>>803でn = 5に変えた場合に正しい
出力になるのはたまたまだった。
>>802をBigInt化するだけで問題なかった。
R
https://ideone.com/OgBxTJ
C++
https://ideone.com/KLqe3g
809: デフォルトの名無しさん [] 2025/08/19(火) 21:08:19.27 ID:zFi0pntB(1) AAS
>>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
810: デフォルトの名無しさん [sage] 2025/08/19(火) 21:28:38.04 ID:ahVErwF8(1) AAS
>>771 scheme (chicken 4.13)
https://ideone.com/RREeGy
811(1): 806 [sage] 2025/08/21(木) 22:19:54.42 ID:fAlkh9Aq(1) AAS
>>799 ruby
https://ideone.com/3TW9Vr
・問題A時に若干端折る
812(5): デフォルトの名無しさん [] 2025/08/21(木) 23:15:48.39 ID:0KQ1xtxb(1) AAS
>>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回）。
813: デフォルトの名無しさん [] 2025/08/22(金) 01:14:43.39 ID:6LYRfbyj(1) AAS
>>799
Java
https://paiza.io/projects/F5kCIBu6BOVB9QTX7hHWMg
814(1): デフォルトの名無しさん [sage] 2025/08/22(金) 06:55:21.34 ID:qlaiAqZd(1/2) AAS
>>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()
}
815: デフォルトの名無しさん [sage] 2025/08/22(金) 06:56:46.07 ID:qlaiAqZd(2/2) AAS
>>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");
}
816(1): 811 [sage] 2025/08/22(金) 20:26:43.82 ID:m9vhyo0Z(1) AAS
>>799 ruby
https://ideone.com/vvp0kq
・問題A時に全体的な規則性に着目
・部分的に着目しちゃったのが>>811
・何も工夫を入れなかったのが>>806
817(1): 816 [sage] 2025/08/23(土) 20:27:40.18 ID:uyhDG+iz(1/2) AAS
>>799 ruby 問題Bもケア
https://ideone.com/od17Hn
818: デフォルトの名無しさん [sage] 2025/08/23(土) 21:01:55.02 ID:gxRFdG35(1) AAS
>>799
java
https://ideone.com/qRTy1Z
819(1): 817 [sage] 2025/08/23(土) 23:26:24.12 ID:uyhDG+iz(2/2) AAS
>>799 java
https://ideone.com/78psr6
820(1): デフォルトの名無しさん [] 2025/08/24(日) 21:13:57.80 ID:ubCw2JoQ(1) AAS
>>812の逆変換プログラムは>>808の順変換プログラムを流用したから処理に無駄があった。
逆変換用に一から書き直したらすっきりした。
R
https://ideone.com/jYUHe1
C++
https://ideone.com/Lne3AQ
821(1): 819 [sage] 2025/08/25(月) 00:28:39.45 ID:IbSJkZLt(1) AAS
>>799 java Iterable<int[]>
https://ideone.com/NRTZpa
822: デフォルトの名無しさん [sage] 2025/08/27(水) 00:40:48.46 ID:AbNZa8yo(1/2) AAS
>>799 ocaml
https://ideone.com/1Jx1Q8
>>799 scheme (chicken 4.13)
https://ideone.com/n7pIFw
823: デフォルトの名無しさん [sage] 2025/08/27(水) 21:02:12.94 ID:AbNZa8yo(2/2) AAS
>>799 octave
https://ideone.com/RH6xXb
824: デフォルトの名無しさん [] 2025/08/27(水) 21:46:51.59 ID:B7vE54ji(1) AAS
>>820の逆変換プログラムのC#版
https://ideone.com/8HpCN9
LINQのTakeWhileメソッドとSumメソッドを組み合わせたらすっきり書けた。
825: 821 [sage] 2025/08/28(木) 21:01:46.43 ID:mnaa+hsk(1) AAS
>>799 java
https://ideone.com/aKkfqN
・next()ごとに複製しない版。する版は >>821
・hasNext()側で次を準備。next()側なのは >>821
826: デフォルトの名無しさん [] 2025/08/29(金) 13:52:26.21 ID:xrZF+zBK(1) AAS
>>799
https://ideone.com/JLM8r8
C++
827: デフォルトの名無しさん [sage] 2025/08/29(金) 20:09:32.40 ID:VEuLqGzD(1) AAS
>>812 ruby 2.5.5
https://ideone.com/tzzN04
・tallyあるのは2.7以降
>>812 octave
https://ideone.com/ebJd9k
828: デフォルトの名無しさん [] 2025/08/29(金) 22:34:59.67 ID:uVFRnDIW(1/2) AAS
>>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%
829: デフォルトの名無しさん [] 2025/08/29(金) 22:35:22.12 ID:uVFRnDIW(2/2) AAS
-- 実行結果 --
【問題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
830(1): デフォルトの名無しさん [sage] 2025/08/30(土) 17:37:04.21 ID:zI+bKiSo(1) AAS
>>812 ocaml
https://ideone.com/SfsytC
>>812 scheme (chicken 4.13)
https://ideone.com/jwWrRt
831: 830 [sage] 2025/09/02(火) 21:36:10.92 ID:MM5Gazf9(1) AAS
>>812 scheme (chicken 4.13)
https://ideone.com/fZufck
・集計部分をalistに変えてみただけ
832(1): デフォルトの名無しさん [sage] 2025/09/06(土) 23:05:19.87 ID:Z/aFZPi6(1) AAS
>>561 scheme (chicken 4.13)
https://ideone.com/lCgs9s
833(1): 832 [sage] 2025/09/07(日) 12:29:41.48 ID:O1zDlKW9(1/2) AAS
>>561 scheme (chicken 4.13)
https://ideone.com/8VZv71
・m1m2を不必要にリストにしてたのを廃止
834: 833 [sage] 2025/09/07(日) 14:22:59.56 ID:O1zDlKW9(2/2) AAS
>>561 scheme (chicken 4.13)
https://ideone.com/EsJWtG
・letを自然な位置に移動
835(1): デフォルトの名無しさん [sage] 2025/09/08(月) 23:02:49.14 ID:4SI/cFAg(1/2) AAS
>>485 scheme (chicken 4.13)
https://ideone.com/feYtNB
>>500 scheme (chicken 4.13)
https://ideone.com/Svhv1y
836(1): 835 [sage] 2025/09/08(月) 23:33:25.73 ID:4SI/cFAg(2/2) AAS
>>485 scheme (chicken 4.13)
https://ideone.com/ejvKat
・(product . lists)
・(product xs . rest) が >>835
837: デフォルトの名無しさん [sage] 2025/09/09(火) 21:56:29.91 ID:PCxKX9bv(1) AAS
>>438 scheme (chicken 4.13)
https://ideone.com/6weUjU
・まずまとまりに分割して処理
>>438 scheme (chicken 4.13)
https://ideone.com/BCt6fd
・最初のを四つにして、残りはスキップ
838: デフォルトの名無しさん [] 2025/09/10(水) 21:21:57.38 ID:rb/tQvOM(1) AAS
>>438
C#で短く書けた
https://ideone.com/SwAZsS
x.EndsWith(" ") でなく x.LastOrDefault() == ' ' の方が長くはなるが効率的かも知れない。
839(1): 836 [sage] 2025/09/10(水) 22:49:33.81 ID:NV1RL9MH(1) AAS
>>485 scheme (chicken 4.13)
https://ideone.com/g8wtFG
・デカルト積の解釈を（勝手に）変更
840(1): 839 [sage] 2025/09/10(水) 23:35:38.95 ID:6JfM8ZLf(1) AAS
>>485 scheme (chicken 4.13)
https://ideone.com/A6K3XL
・(cons y x)して最後にreverseする
・(list x y)して最後にflattenするのが >>839
841: 840 [sage] 2025/09/11(木) 23:05:23.09 ID:WPUXbxYH(1) AAS
>>485 scheme (chicken 4.13)
https://ideone.com/YqrvdM
・reverse回数減らした版
842(1): デフォルトの名無しさん [sage] 2025/09/12(金) 15:41:31.15 ID:IRXhEt4s(1) AAS
お題
1行1単語のリストが、しりとりとして成立しているか判定するコードを書きなさい
成立していたら◯、不成立なら☓をしゅつりょくすること
【入力】
りんご
ごりら
らっぱ
843: デフォルトの名無しさん [sage] 2025/09/12(金) 16:19:33.85 ID:uazXAFOm(1) AAS
入力例に対する出力例が存在しなくて曖昧
それを補わないと問題が不成立
844: デフォルトの名無しさん [sage] 2025/09/12(金) 20:36:05.46 ID:I2wrB793(1) AAS
>>438 scheme (chicken 4.13)
https://ideone.com/SlkO0l
・空白時にdrop-while
>>842 ruby
https://ideone.com/mY83rW
845(15): デフォルトの名無しさん [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]までのリスト： https://oeis.org/A001591/list
846(1): デフォルトの名無しさん [] 2025/09/13(土) 21:09:19.41 ID:rhMflYHg(1) AAS
>>845
R
https://ideone.com/R7chTY
ヒントはどう使うのかわからなかった。
847: デフォルトの名無しさん [] 2025/09/14(日) 02:07:05.25 ID:K9dbpWus(1) AAS
>>845 c++
https://ideone.com/ezHz45
先越された
848(1): デフォルトの名無しさん [sage] 2025/09/14(日) 02:17:37.66 ID:ymjVQadn(1) AAS
>>845 ruby
https://ideone.com/wrV2zh
・なんとなく動いてる版
・チマチマと次を探して行く
・G[20]まで出すのがやっと(4.05s)
849(2): デフォルトの名無しさん [] 2025/09/14(日) 21:00:58.83 ID:Yva1i9w5(1/2) AAS
>>845
R
https://ideone.com/XhdJw4
>>846より行列計算が速くなった。変数名mとnが逆だったのを直した。
C++に移植
https://ideone.com/9dibE0
850(1): デフォルトの名無しさん [] 2025/09/14(日) 22:50:48.82 ID:Yva1i9w5(2/2) AAS
>>845
Fortranに移植
https://ideone.com/CnJ0S9
行列計算を短く書けて、しかも実行が速い。
851(2): 848 [sage] 2025/09/15(月) 00:34:43.20 ID:aTaxsjKO(1/2) AAS
>>845 ruby
https://ideone.com/3I72I6
・キャッシュ探りながら構築
・c[桁の合計][幅] = とりうるパターン
852(1): 851 [sage] 2025/09/15(月) 00:58:49.72 ID:aTaxsjKO(2/2) AAS
https://ideone.com/GWbQAx
・動きは >>851 といっしょ
・若干の整理
853: デフォルトの名無しさん [] 2025/09/15(月) 22:27:44.05 ID:g8zilsSB(1) AAS
>>850では行末に無駄な半角空白文字が出力される。消すには最後から3行目のnthPartition(m, n)を
trim( )で囲めば良い。
854(1): 852 [sage] 2025/09/16(火) 01:02:30.84 ID:3CKXdG+H(1) AAS
>>845 ruby
https://ideone.com/n5Jqm3
・動きは >>851 といっしょ
・数値の内部表現を配列から整数へ変更
855(1): 854 [sage] 2025/09/17(水) 22:30:29.22 ID:U8XLHdaR(1) AAS
>>845 ruby 2.5.5
https://ideone.com/oAQimi
・とりうるパターン数に着目し迫る
・tallyは2.7以降
856(1): デフォルトの名無しさん [] 2025/09/17(水) 22:43:48.03 ID:RlLGu0ST(1/2) AAS
>>845
C++
https://ideone.com/I6K1tl
行列Aの計算で加減算・代入回数を>>849より減らした。実行時間の違いは分からなかった。
857: デフォルトの名無しさん [] 2025/09/17(水) 23:39:47.32 ID:RlLGu0ST(2/2) AAS
>>856
BigInt化してm = 2000, n = 2¹⁰²⁴で実行したら違いが明確になった。
(1) >>849のBigInt版
https://ideone.com/S92L9G
(2) >>856のBigInt版
https://ideone.com/3x03xT
加減算・代入回数を削減した(2)の方が確かに速く、(1)の約4分の3の実行時間。
858(1): 855 [sage] 2025/09/18(木) 21:13:33.56 ID:mk4sIpUK(1) AAS
>>845 ruby 2.5.5
https://ideone.com/Zm2433
・揃ってからcumsum、のリズムを廃止
859(1): 858 [sage] 2025/09/19(金) 21:59:08.62 ID:e72KvXSi(1) AAS
>>845 ruby 2.5.5
https://ideone.com/iwQNCH
・若干の整理（loop廃止、fill三回へ置き換え）
860(1): 859 [sage] 2025/09/20(土) 21:39:31.29 ID:zrmIrXrK(1) AAS
>>845 ruby 2.5.5
https://ideone.com/jHqv2L
・内部表現の変更
112225→[2,3,0,0,1]
861(1): 860 [sage] 2025/09/22(月) 21:37:36.11 ID:9W7EeSnZ(1) AAS
>>845 ruby 2.5.5
https://ideone.com/MDHX6v
・内部表現のさらなる変更
・パターン数を直接キャッシュするようにした
cc[合計][幅] = とりうるパターン数
>>845 ruby
https://ideone.com/PB8S7w
・m = 2000, n = 1 << 1024
862(1): 861 [sage] 2025/09/23(火) 01:13:48.01 ID:XS9iE/WB(1) AAS
>>845 c++
https://ideone.com/oma0Jf
・ruby版861の移植
・m = 2000, n = 1 << 1024
863: 862 [sage] 2025/09/26(金) 21:58:13.14 ID:rAOVnJgT(1) AAS
>>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では使えずボツ
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.042s