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

[433 デフォルトの名無しさん 2024/10/09(水) 01:22:59.53 ID:YvVjSPhZ]

プログラミングする以前に読むのが面倒くさい

[434 デフォルトの名無しさん 2024/10/09(水) 01:43:57.73 ID:4B3K5XUV]

しまった。初期化してなかったなｗ変数のところ。
あとsouの回復もホイミ、ベホイミ、ベホマラーの３種類だけ。
その３種類がぞろ目の時（１１１，２２２など）
そしたらベホマズンを使える。ほぼ運ゲーですｗ
人修羅みたいに取り巻きがいます。それはバラモスエビルと神龍です。
ある一定時期を過ぎると取り巻きが一斉にHPを連続してあげまくるので
取り巻き先に倒さないと厳しいです。取り巻き＝tori種類１の取り巻き＝tori0
種類２の取り巻き＝tori1　5人だとなかなか倒せないから６人目の魔法剣士＝maken
だれか
これをいれよう。
さてif文を完成させよう！if zoma =1
print("ゾーマが現れた”）
import random
random.random()x = random.uniform(0.1,0.9)
print(x)
if x >200 :
print( 'enemyに' +200のダメージを与えた)
elif x > 0.5 :
print( 'enemyに１００＋のダメージを与えた' )
elif x > 0.2 :
print( '相手が躱した' )
else :
print( "まだゾーマは死んでません")
つかれたーｗ
もっと簡単なやつにしまーすｗ

[435 デフォルトの名無しさん 2024/10/09(水) 01:45:35.37 ID:YvVjSPhZ]

頑張って読んだけどこのままでは多分スレチ、ずっと条件を簡単にして出題し直してみる。

お題
勇者（HP1000）対魔王（HP5000）、先鋒勇者、サイコロ（目は１から６）を振って出た目だけ相手にダメージを与えられ、交互に攻撃しHP0となったら負け。魔王のサイコロは１個だけど勇者のサイコロはN個（N=1～10）の時の勇者の勝率を求めよ。

[436 デフォルトの名無しさん 2024/10/09(水) 02:10:34.29 ID:4B3K5XUV]

# RPGの攻撃状況を再現

# モンスターと戦っている。
# 1から10のサイコロをふって、
# 6未満の場合、サイコロの目だけダメージを与えたと表示。
# 6以上の場合、クリティカルヒットとして、100のダメージを与えたと表示。
# 0の場合、防御されたとして、０ダメージを表示。

import random
hit = random.randint(0,10)
if 1 <= hit < 6:
print("スライムに、" + str(hit) + "のダメージを与えた！")
elif hit >= 6:
print("クリティカルヒットダメージ１００を与えた")
else:
print("ダメージは、" + str(hit) + "防御された")
#楽しすぎだなｗこれはｗ

[437 デフォルトの名無しさん 2024/10/09(水) 18:59:48.61 ID:Vd16zyId]

>>429
asciiで。

[438 デフォルトの名無しさん 2024/10/11(金) 05:53:27.29 ID:EzY86rdr]

お題：文字列の中で1つ以上連続している空白をすべて空白4つに置換せよ。ただし正規表現は使ってはならない。

例：
"abc def ghi" -> "abc def ghi"

[439 438 2024/10/11(金) 05:54:39.00 ID:EzY86rdr]

5chは空白を1つに置換するらしく例は出せない。脳内保管せよ。

[440 デフォルトの名無しさん 2024/10/11(金) 20:53:22.06 ID:BlO5cFoG]

>>438
perl -lpE'$_=join$"x4,split$"'
(文字列を入れる)

[441 デフォルトの名無しさん 2024/10/11(金) 20:58:31.10 ID:BlO5cFoG]

>>440
splitのあとの$"は不要だった。
どちらにしてもタブも置換してまうのでアウトかも。

[442 デフォルトの名無しさん 2024/10/11(金) 22:15:53.82 ID:H5F5jhxE]

>>438
R
https://ideone.com/LO7vyR

[443 デフォルトの名無しさん 2024/10/12(土) 01:34:10.91 ID:OB4ycmPb]

>>435
こういう場合の確率の計算はよく分からなかったので実際にそれぞれ一万回ずつ戦わせてみた。
サイコロ1個で100000戦0勝
サイコロ2個で100000戦0勝
サイコロ3個で100000戦0勝
サイコロ4個で100000戦0勝
サイコロ5個で100000戦47171勝
サイコロ6個で100000戦100000勝
サイコロ7個で100000戦100000勝
サイコロ8個で100000戦100000勝
サイコロ9個で100000戦100000勝
サイコロ10個で100000戦100000勝

[444 デフォルトの名無しさん 2024/10/12(土) 01:39:02.69 ID:OB4ycmPb]

>>443
#!ruby
#encoding: utf-8
$stdout=open("kekka.txt","w")
i=100000 #対戦回数
k=0 #勇者の勝ち
n=1 #勇者のサイコロの数
hpm=5000 #魔王のＨＰ
hpy=1000 #勇者のＨＰ

[445 デフォルトの名無しさん 2024/10/12(土) 01:39:40.49 ID:OB4ycmPb]

>>444
while n<=10
j,t=0,0
while j<i
hpy-=rand(1..6)
if hpy<=0
j+=1
t,hpy,hpm=0,1000,5000
next
end
m=0
while m<n
hpm-=rand(1..6)
m+=1
end
if hpm<=0
k+=1
j+=1
t,hpy,hpm=0,1000,5000
next
end
t+=1
end
puts "サイコロ#{n}個で#{i}戦#{k}勝"
k,hpy,hpm=0,1000,5000
n+=1
end

[446 警備員[Lv.12] 2024/11/05(火) 05:27:21.14 ID:srt1vo+S]

>>427
Kotlin

スペースが何個なのか分り易くするために '*' をスペースの代わりに入れて呼び出している。

https://paiza.io/projects/xSP0nP203HXTwqyxlQD0Gg

[447 デフォルトの名無しさん 2024/11/13(水) 22:01:15.62 ID:nRkxNwtG]

>>435
R

f=\(N){
u=1000
m=5000
while(u>0 & m>0){
m=m-sum(sample(6,N,replace=TRUE))
u=u-sample(6,1)
}
u>m
}
sim=\(N) mean(replicate(1e3,f(N)))
p=sapply(1:10,sim)
plot(p)
data.frame(N=1:10,p=p)

N p
1 1 0.000
2 2 0.000
3 3 0.000
4 4 0.000
5 5 0.498
6 6 1.000
7 7 1.000
8 8 1.000
9 9 1.000
10 10 1.000

[448 デフォルトの名無しさん 2024/11/13(水) 22:22:31.42 ID:nRkxNwtG]

>>435
Wolfram

f[N_] :=(
u=1000;
m=5000;
Until[u<=0 || m<=0, m-=Total@RandomChoice[Range[6],N];u-=Total@RandomChoice[Range[6],1]];
Boole[u >= m]
)
Table[Mean@Table[f[x],10^3],{x,1,10}] // N

{0., 0., 0., 0., 0.511, 1., 1., 1., 1., 1.}

[449 デフォルトの名無しさん 2024/12/31(火) 22:33:49.84 ID:5KitXLte]

ベクターにあるこれを解いてくれ
昔2ch、5chスレでやってたができず
いまだと4x4はパワーで行けるとおもうが

4x4盤タイルゲーム for Windows
対戦するたびに学習して次第に強くなる「最善手探索+対戦学習型知能ゲーム」

[450 デフォルトの名無しさん 2025/01/01(水) 12:58:01.50 ID:emEmRiID]

他力本願か？

[451 デフォルトの名無しさん 2025/01/01(水) 13:30:44.19 ID:WMbw73Fu]

出題の仕方でプログラミング能力の無さがわかる

[452 デフォルトの名無しさん 2025/01/01(水) 13:32:50.17 ID:ZpviU2f/]

>>438
Java
https://paiza.io/projects/c5TaBFHebIAdHNIU_QToUg

[453 デフォルトの名無しさん 2025/01/01(水) 13:54:47.38 ID:ZpviU2f/]

>>427
Java
https://paiza.io/projects/9XrtZ_9CpiIeg-xcQkcc1Q?language=java

[454 デフォルトの名無しさん 2025/01/01(水) 15:04:31.04 ID:ZpviU2f/]

>>416
Java
https://paiza.io/projects/xs9ggwnP0Am-Y9dDK0794A?language=java

[455 デフォルトの名無しさん 2025/01/01(水) 18:14:11.44 ID:X9RQ0R0S]

>>449
勝手に名付けて水道管連結ゲーム
先後で縦か横で管を繋げた方の勝ち
ただしこの場合、黒が角においたら連結するだけだが今白が角におくと黒2つは除去される
▓
□▓

[456 デフォルトの名無しさん 2025/01/01(水) 19:18:52.94 ID:ZpviU2f/]

>>382
Java
https://paiza.io/projects/Nvq9hUoU-aTzCInIQLugGg

[457 デフォルトの名無しさん 2025/01/01(水) 19:35:45.17 ID:ZpviU2f/]

>>381
Java
https://paiza.io/projects/DzTt5UiETM3n60v4Pj5-hg?language=java

[458 デフォルトの名無しさん 2025/01/01(水) 20:12:46.32 ID:ZpviU2f/]

>>356
Java
https://paiza.io/projects/9oGyF38BDGg3_l8X-MS5-Q?language=java

[459 デフォルトの名無しさん 2025/01/01(水) 20:32:30.47 ID:ZpviU2f/]

>>349
Java
https://paiza.io/projects/VuNCoPaBlgTLpp9G-pMWxg?language=java

[460 警備員[Lv.16] 2025/01/02(木) 03:06:13.48 ID:PSAM74+n]

>>438
Kotlin

https://paiza.io/projects/8ePwRoyLPZQ0cMWtO7MSHg

[461 警備員[Lv.16] 2025/01/02(木) 03:15:13.97 ID:PSAM74+n]

>>449
解いてくれって？何をしたらいいの？
全パターンやらせて勝つパターンを出せってこと？

[462 デフォルトの名無しさん 2025/01/02(木) 10:05:16.72 ID:gED46q9T]

>>461
最善手だったら先手の勝ちかどうか

[463 デフォルトの名無しさん 2025/01/02(木) 16:25:40.35 ID:H7SLSd6p]

https://mevius.5ch.net/test/read.cgi/tech/1624028577/251

Java
https://paiza.io/projects/hQp_tZ73CDJ-oBAxcJuHbA?language=java

[464 デフォルトの名無しさん 2025/01/03(金) 13:22:57.82 ID:dEYOS8Dq]

お題
AのあとｂﾉAと同じ数だけBが続く言語エビがあるとします
文字列が入力されたときそれがエビ言語であるか判定するプログラムを作成してください

→ true
A → false
B → false
AB → true
ABB → false
AAB → false
AABB → true
ABAABBAAABBB→ true

[465 デフォルトの名無しさん 2025/01/03(金) 13:25:00.11 ID:dEYOS8Dq]

>>464
文字化け訂正
誤：AのあとｂﾉAと同じ数だけBが続く言語エビがあるとします
正：AのあとにAと同じ数だけBが続く言語エビがあるとします

[466 デフォルトの名無しさん 2025/01/03(金) 15:30:14.42 ID:aGLRGnDr]

>>464 lisp
https://ideone.com/hHjwKz

[467 デフォルトの名無しさん 2025/01/03(金) 15:34:16.34 ID:aGLRGnDr]

>>464 python
https://ideone.com/2Xa1tx

[468 デフォルトの名無しさん 2025/01/03(金) 17:52:02.97 ID:aGLRGnDr]

>>464 lisp (chatgptに教えてもらった)
https://ideone.com/UYK3Qu
https://chatgpt.com/share/67778c2d-647c-8011-96dd-954a8f0fba92

[469 デフォルトの名無しさん 2025/01/03(金) 20:07:57.67 ID:yesC/P5F]

>>464
fn is_ab_lang(input: &str) -> bool {
match input
.chars()
.fold(Some(0), |state, char| match (state, char) {
(Some(count), 'A') => Some(count + 1),
(Some(count), 'B') if count > 0 => Some(count - 1),
_ => None,
}) {
Some(0) => true,
_ => false,
}
}

fn main() {
for s in ["", "AB", "AABB", "ABAABBAAABBB"] {
assert!(is_ab_lang(s)); // true
}
for s in ["A", "B", "BA", "ABB", "AAB", "ABBA"] {
assert!(!is_ab_lang(s)); // false
}
}

[470 デフォルトの名無しさん 2025/01/03(金) 23:45:21.31 ID:AD9nWeeV]

>>464 c
https://ideone.com/KDcKNc
#include <stdio.h>
#include <string.h>
int isablang(const char *s) {
size_t a = strspn(s, "A"), b = strspn(s + a, "B");
return !*s || 0 < a && 0 < b && a == b && isablang(s + a + b);
}
void g(const char *s) {
printf("%s\t%s\n", isablang(s) ? "true" : "false", s);
}
int main() {
g("A"), g("B"), g("C"), g("BA"), g("CA"), g("ABB"), g("AAB"), g("AABABB"), g("ABC"), g("CAB"), g("ABCAB");
g(""), g("AB"), g("ABAB"), g("AABB");
return 0;
}

[471 デフォルトの名無しさん 2025/01/04(土) 14:03:19.07 ID:uiECOsgP]

>>468
ChatGPTロジックだとAABABBが受理されちゃう

[472 468 2025/01/04(土) 15:43:19.87 ID:RKGS1C18]

あら
ちょっとだけ修正すれば…って、無理か

[473 デフォルトの名無しさん 2025/01/04(土) 16:26:18.49 ID:kbkaPDs8]

>>464 c
https://ideone.com/x7a81M
・strspn使わない
・再帰しない
#include <stdio.h>
int isablang(const char *s) {
const char *t, *u;
for (; *s; s = u) {
if (*s != 'A') return 0; else for (t = s; *t == 'A'; t++);
if (*t != 'B') return 0; else for (u = t; *u == 'B'; u++);
if (t - s != u - t) return 0;
}
return 1;
}

[474 デフォルトの名無しさん 2025/01/04(土) 21:19:41.74 ID:uiECOsgP]

お題
貨幣・銀行券を次の文字列で表すとします
(1)
(5)
(10)
(50)
(100)
(500)
[1000]
[5000]
[10000]

貨幣・銀行券がランダムに次のような文字列で与えられます
(100)(10)(1)[10000](5)(500)[1000][5000][1000][1000](10)(100)(50)(100)[1000]

与えられた貨幣・銀行券を分類して貨幣・銀行券の価値が高い順に次のように出力するプログラムを作成してください
[10000]
[5000]
[1000][1000][1000][1000]
(500)
(100)(100)(100)
(50)
(10)(10)
(5)
(1)

[475 デフォルトの名無しさん 2025/01/04(土) 22:52:21.99 ID:frbzLXtQ]

>>474 c
https://ideone.com/TBzq6C

[476 デフォルトの名無しさん 2025/01/05(日) 03:39:43.83 ID:/228f09V]

>>449
誰もいないので自分でAIに司令してやってみた
が何かおかしい
https://ideone.com/ZlulrF

[477 デフォルトの名無しさん 2025/01/05(日) 21:35:39.46 ID:6Z+55hA8]

>>474 ruby
https://ideone.com/6bso7P

[478 警備員[Lv.18] 2025/01/12(日) 04:14:11.28 ID:zWON4EbF]

>>464
Kotlin
https://paiza.io/projects/SkS05OZPJQJlBJ0iWlkkeA

[479 警備員[Lv.18] 2025/01/12(日) 04:47:49.98 ID:zWON4EbF]

>>474
Kotlin
https://paiza.io/projects/rM9KpHluaNW1E3bsLY2k6A

[480 デフォルトの名無しさん 2025/01/12(日) 17:40:12.54 ID:Mt0OVaIB]

4*4タイルゲームをAIに命令させてやらせているが
それっぽいのを出力はするが正しい勝利判定ができていない

[481 デフォルトの名無しさん 2025/01/13(月) 13:03:01.90 ID:mFwJihvQ]

>>438 c
https://ideone.com/UKze06

[482 デフォルトの名無しさん 2025/01/13(月) 20:43:35.02 ID:zlmvetys]

>>438 java
https://ideone.com/mGUDU4

[483 9 2025/01/20(月) 01:11:38.35 ID:zWVP8H/r]

>>474 Perl5

$s = '(100)(10)(1)[10000](5)(500)[1000][5000][1000][1000](10)(100)(50)(100)[1000]';
$h{$_} .= $_ for $s =~ /\(\d+\)|\[\d+\]/g;
use List::Util 'sum';
$v{$h{$_}} = sum($h{$_} =~ /\d+/g) for keys %h;
print "$_\n" for sort{$v{$b} <=> $v{$a}} keys %v;

実行結果
~ $ perl 22_474_value.pl
[10000]
[5000]
[1000][1000][1000][1000]
(500)
(100)(100)(100)
(50)
(10)(10)
(5)
(1)

[484 9 2025/01/21(火) 02:09:25.80 ID:Kvjf8jsk]

>>483 Perl5

$_ = 'abc def ghi';
print join(' ' x 4, split) . "\n";

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

お題

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

入力：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]

[486 デフォルトの名無しさん 2025/01/22(水) 22:43:43.59 ID:EHGf/TPZ]

>>485
Rust

fn odai(文字列: &str, 長さ: usize) -> Vec<String> {
use itertools::Itertools;
(0..長さ)
.map(|_| 文字列.chars())
.multi_cartesian_product()
.map(String::from_iter)
.collect()
}

fn main() {
assert_eq!(odai("ABC", 1), ["A", "B", "C"]);
assert_eq!(odai("ABC", 2), ["AA", "AB", "AC", "BA", "BB", "BC", "CA", "CB", "CC"]);
assert_eq!(odai("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"]);
}

[487 デフォルトの名無しさん 2025/01/22(水) 23:18:53.24 ID:dYX3B7ea]

>>485 ruby
https://ideone.com/EA8orq
f = ->(s, n) {:product.to_proc.(*[s.chars]*n).map(&:join)}

[488 デフォルトの名無しさん 2025/01/22(水) 23:57:13.34 ID:EHGf/TPZ]

>>485
Rust 今回は積ライブラリを使わない自力版

fn odai(文字列: &str, 長さ: usize) -> Vec<String> {
let chars = 文字列.chars().collect::<Vec<_>>();
let mut state = vec![0; 長さ];
let mut output = Vec::new();
'Loop: loop {
let s = state.iter().map(|i| chars[*i]).collect();
output.push(s);
for index in state.iter_mut().rev() {
*index += 1;
if *index == chars.len() {
*index = 0;
continue;
}
continue 'Loop;
}
return output;
}
}

検証用main()は>>486と同じ

[489 デフォルトの名無しさん 2025/01/23(木) 18:33:06.01 ID:hcg9tgUx]

>>485
JavaScript

const prod = function* (str, len, buf = [])
{
　if (len > 0)
　{
　　for (let i = 0; i < str.length; i++)
　　{
　　　buf.push(str[i]);
　　　yield* prod(str, len - 1, buf);
　　　buf.pop();
　　}
　}
　else
　{
　　yield buf.join("");
　}
};

for (let n = 1; n < 4; n++)
{
　console.log([...prod("ABC", n)]);
}

[490 デフォルトの名無しさん 2025/01/23(木) 20:05:23.84 ID:naue5Hlh]

>>485 ocaml
https://ideone.com/hEQ0UI

>>485 octave
https://ideone.com/Hga7TO

[491 9 2025/01/24(金) 01:44:22.46 ID:p08ruAfw]

>>485　Perl5

for $n (1..3) {
　@cp = @s = qw(A B C);
　while(--$n) { @cp = map{ $p = $_; map{ "$p$_" } @s } @cp }
　print "@cp\n";
}

※見易くするためインデントは全角スペースに置換してあります


実行結果
~ $ perl 22_485_CartesianProd.pl
A B C
AA AB AC BA BB BC CA CB CC
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

[492 9 2025/01/24(金) 17:38:14.24 ID:cg1ZmS3G]

>>464 Perl5

for (<DATA>) {
　chomp;
　print "$_ → ", (/^(A((AB)?|(?1))B)+$/g ? 'true' : 'false'), "\n";
}
__DATA__

A
B
AB
ABB
AAB
AABB
ABAABBAAABBB
ABC
AABABB

※見易くするためにインデントを全角スペースに置換してあります

実行結果
~ $ perl 22_464_AB_rec_rex.pl
→ false
A → false
B → false
AB → true
ABB → false
AAB → false
AABB → true
ABAABBAAABBB → true
ABC → false
AABABB → false

[493 デフォルトの名無しさん 2025/01/24(金) 20:04:46.59 ID:kDOvSp0D]

>>485 dart
https://ideone.com/nZXS5G

>>485 rust
https://ideone.com/07rym1

[494 9 2025/01/25(土) 02:52:09.44 ID:wVQIyzpy]

>>492
/g の ｇは不要で / でおｋだった…orz

[495 デフォルトの名無しさん 2025/01/25(土) 03:04:24.02 ID:Z97MpHAu]

どんまい

[496 デフォルトの名無しさん 2025/01/25(土) 21:23:47.57 ID:KM9w0vp0]

>>485 c
https://ideone.com/7DAmou
・バッファに取る版

>>485 c
https://ideone.com/irBE3p
・バッファに取らない版
・表示するだけ

[497 デフォルトの名無しさん 2025/01/26(日) 14:07:38.91 ID:nBBaggrk]

>>485
Java
https://paiza.io/projects/W5rymKHMXkZgp2ID0-tfMg

[498 493 2025/01/26(日) 15:22:46.05 ID:dl7YvN1C]

>>485 dart
https://ideone.com/WtkLVE
・若干の簡略化

>>485 rust
https://ideone.com/VXyvY2
・若干の簡略化？

[499 デフォルトの名無しさん 2025/01/27(月) 00:00:51.14 ID:/Jqezixy]

>>485 java
https://ideone.com/H7Pti7

[500 デフォルトの名無しさん 2025/01/27(月) 09:16:22.69 ID:rqFJtGlJ]

お題
入力された文字列から重複する文字を抽出してください

T →
CG →
ATA → A
CGGA → G
ATGAT → AT
GTTGCA → GT
CCCCGGG → CG
ACTGCGAG → ACG
ATCAGAATA → AT
TGCCATGACA → TGCA

[501 9 2025/01/27(月) 17:15:59.64 ID:cwZgX9Gy]

Perl5

for (qw{T CG ATA CGGA ATGAT GTTGCA CCCCGGG ACTGCGAG ATCAGAATA TGCCATGACA}) {
　%h = (); $h{$_}++ for split '';
　print "$_ → ", (grep{1 < $h{$_}} keys %h), "\n";
}

※見易くするためインデントを全角スペースに置換してあります


実行結果
~ $ perl 22_500_dupe_char.pl
T →
CG →
ATA → A
CGGA → G
ATGAT → TA
GTTGCA → GT
CCCCGGG → CG
ACTGCGAG → GAC
ATCAGAATA → TA
TGCCATGACA → TGAC

[502 9 2025/01/27(月) 21:20:12.94 ID:cwZgX9Gy]

>>501 Coilotに入力して処理内容を問うてみたらちゃんと返してきてワラタ
https://copilot.microsoft.com/chats/rbPk2t5sxTRgAPM8BeSxZ

[503 9 2025/01/27(月) 21:22:36.75 ID:cwZgX9Gy]

CopilotのURLをコピペしても他の人に内容を見せることはできなかったワ…orz

[504 デフォルトの名無しさん 2025/01/27(月) 21:24:28.42 ID:LHxZVLOG]

>>500 octave
https://ideone.com/eLcVPC
function s = f(s)
[~, ia] = unique(s);
s(ia) = [];
if 1 < length(s)
[~, ia] = unique(s, 'first');
s = s(sort(ia));
end
end

>>500 ruby
https://try.ruby-lang.org/playground/#code=f+%3D+-%3Es+%7Bs.chars.tally.select+%7B1+%3C+_2%7D.keys.join%7D%0Ass+%3D+%3C%3CEOS.lines(chomp%3A+true)%0AT%0ACG%0AATA%0ACGGA%0AATGAT%0AGTTGCA%0ACCCCGGG%0AACTGCGAG%0AATCAGAATA%0ATGCCATGACA%0AEOS%0Aputs+ss.map+%7B%7Cs%7C+%22%23%7Bs%7D+-%3E+%23%7Bf.(s)%7D%22%7D&engine=cruby-3.3.0
https://ideone.com/9E5Z9a
f = ->s {s.chars.tally.select {1 < _2}.keys.join}

[505 デフォルトの名無しさん 2025/01/27(月) 21:30:57.80 ID:l9HsQRRu]

>>485 lisp
https://ideone.com/Hiqt3o

>>500 lisp
https://ideone.com/eRqGSp

[506 デフォルトの名無しさん 2025/01/28(火) 21:18:03.62 ID:oNqYbqge]

>>500 dart
https://ideone.com/WZzsxb

>>500 c
https://ideone.com/1c41ME

[507 デフォルトの名無しさん 2025/01/29(水) 01:00:49.19 ID:4mvV5Tkg]

>>500 c++
https://ideone.com/5VRuHk

[508 デフォルトの名無しさん 2025/01/29(水) 01:49:29.44 ID:PQfpjql4]

>>500
REM 重複チェック.bat
ruby -x "%~f0"
exit

#~
#!ruby
while 1
print "> "
a=$stdin.gets.chomp.split("")
exit if a==[]
puts a.select{|e| a.count(e)>1}.uniq.join
end

[509 デフォルトの名無しさん 2025/01/29(水) 21:56:05.24 ID:GDFS0NvX]

>>500 java
https://ideone.com/zIZZ1G

[510 デフォルトの名無しさん 2025/01/30(木) 21:27:24.39 ID:te1+SH0T]

お題
ソース文字列と検索文字列が入力されます
検索文字列の文字をすべて含むソース文字列の部分文字列のうち
一番短い部分文字列を出力してください

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

[511 506 2025/01/30(木) 21:43:26.41 ID:ID2xuR+0]

>>500 c
https://ideone.com/LLFaOP
・unsigned int m[128] = {0};を使って集計

[512 デフォルトの名無しさん 2025/01/30(木) 22:47:12.58 ID:3iB+73MI]

高速文字列解析の世界に似た問題のアルゴリズム(ウェーブレット木)が沢山ありました

[513 デフォルトの名無しさん 2025/01/31(金) 00:36:51.89 ID:MBodgIXJ]

>>510 ruby
https://ideone.com/K7lxJe

[514 デフォルトの名無しさん 2025/01/31(金) 13:46:22.55 ID:+tPQNmsr]

このスレでいいのかわからんのだけど
Rust勉強中なんだがメモリ安全性の恩恵を受けやすいなんかしらかのプログラムを書こうと思ってるんだがなにかいいお題はあるか？
言語処理系は大体作ってるのでそれ以外で頼む

[515 デフォルトの名無しさん 2025/01/31(金) 15:33:43.41 ID:b4vq2KMj]

う～んこの嫌われムーブはあのおじさんか
このスレでは自重して欲しいな

[516 デフォルトの名無しさん 2025/01/31(金) 16:14:43.64 ID:fZW/Grtl]

>>514 へのお題

次の操作ができる循環リンクリストを作成してください

・空のリストへの挿入
・冒頭の挿入
・最後に挿入
・指定された位置への挿入
・最初のノードを削除する
・最後のノードを削除する
・任意の位置からノードを削除する

[517 デフォルトの名無しさん 2025/01/31(金) 21:55:55.86 ID:mLWOFznj]

>>514
Rustはメモリのデータ競合もデータ参照競合も全てコンパイルエラーにしてくれるから間違えようがないね
他の普通の言語だと実行して問題発生に気付いて調査して頑張ってようやく競合が原因だと判明して間違えていたことがわかるから開発効率の悪さとして差が現れるけど
Rustは実行前にその種のミスのデバッグまで全て終えてしまう感じ

[518 デフォルトの名無しさん 2025/01/31(金) 22:10:00.47 ID:4ClqIqkw]

普通は問題発生前に気がつく

[519 デフォルトの名無しさん 2025/01/31(金) 22:17:10.46 ID:bHXxdIdo]

>>510 c
https://ideone.com/MZt32o

[520 デフォルトの名無しさん 2025/01/31(金) 22:38:00.61 ID:3jAIz2ps]

>>518
グローバル変数を排他制御せずに使ってしまっていたりするミスなどよく見かけるような
一般的にも巨大なコードになったり複数人で共通認識なかったりで見逃しミスは必ず出てくる
そしてタイミング次第によって稀にバグが起こるパターンとか負荷が高くなって起きてバグ発覚とか

[521 デフォルトの名無しさん 2025/01/31(金) 23:44:08.10 ID:mLWOFznj]

全て自分で出来る気付くミスらない
って自己過信な人がセキュリティホールを招いてるからね
自動的にサポートしてくれる言語を使うのが安全で開発効率もいいよ

[522 デフォルトの名無しさん 2025/02/01(土) 00:00:30.73 ID:pgp85i6o]

ちゃんとルールを守って運転すれば
事故も起きないし､違反で捕まらない
それと同じ

[523 デフォルトの名無しさん 2025/02/01(土) 00:26:30.15 ID:cvjWKAds]

>>517
せっかくだからRustで>>516やってきなよ

[524 519 2025/02/01(土) 17:22:30.12 ID:/Ur4AoNp]

>>510 c
https://ideone.com/tdT1q2
・若干の高速化
　部分文字列を一文字ずつズラして検証していたのを
n = strcspnで探してn文字スキップへ

[525 デフォルトの名無しさん 2025/02/01(土) 22:42:58.39 ID:1BfoGXYb]

>>516
横からだがその仕様ならベクタをリングバッファとして使った両端キューで十分だな
多くの実用例でもこの方が速いことが知られている

use std::collections::VecDeque;
// 空のキュー
let mut deque: VecDeque<T> = VecDeque::new();
// 先頭に挿入
deque.push_front(t);
// 最後に挿入
deque.push_back(t);
// 指定位置に挿入
deque.insert(index, t);
// 先頭を削除して得る
let first: Option<T> = deque.pop_front();
// 最後を削除して得る
let last: Option<T> = deque.pop_back();
// 指定位置を削除して得る
let element: Option<T> = deque.pop_back();

[526 デフォルトの名無しさん 2025/02/01(土) 22:57:16.48 ID:FwGLv5NU]

ズルしてどうするんよ…

[527 デフォルトの名無しさん 2025/02/01(土) 23:00:12.86 ID:FwGLv5NU]

Rustのメモリ安全性を確認するためにプログラム書きたいんでしょ、だったら循環リストをフルスクラッチするしかないよね

[528 デフォルトの名無しさん 2025/02/02(日) 19:41:14.89 ID:NpAQnhYs]

リンクリストならindex番目の操作(挿入or切除)は
index番目で分解して操作して合体するだけなのでこれで動くよ

use std::collections::LinkedList;

trait LinkedListExt<T> {
fn insert_at(&mut self, index: usize, value: T);
fn remove_at(&mut self, index: usize) -> Option<T>;
}

impl<T> LinkedListExt<T> for LinkedList<T> {
fn insert_at(&mut self, index: usize, value: T) {
let mut tail = self.split_off(index);
self.push_back(value);
self.append(&mut tail);
}
fn remove_at(&mut self, index: usize) -> Option<T> {
let mut tail = self.split_off(index);
let value = tail.pop_front();
self.append(&mut tail);
value
}
}

[529 デフォルトの名無しさん 2025/02/03(月) 21:15:02.53 ID:swo++26S]

>>510
R
https://ideone.com/0Hr1lU

C++ (>>524と同じ巨大文字列での繰り返しあり)
https://ideone.com/7fJXjB

[530 デフォルトの名無しさん 2025/02/03(月) 22:57:52.37 ID:VF4m0iMh]

>>510 c
https://ideone.com/L4xIAy
・f_529 は529さんのパクり
・f_strcspn_chr は strchr してから strcspn すると単純ながら若干の速度向上

[531 530 2025/02/04(火) 21:13:55.63 ID:k8XtEdoq]

>>510 c
https://ideone.com/Mar3S7
・f_529direct は出現位置集めるのやめた
　*min = strchr(*min + 1, **min)) でそのまま次へ

[532 531 2025/02/05(水) 20:39:11.49 ID:mFRiRIqM]

>>510 c
https://ideone.com/jeAf1a
・デバッグと若干の整理

[533 532 2025/02/05(水) 23:28:39.35 ID:mFRiRIqM]

>>510 java
https://ideone.com/EdHfzN

[534 デフォルトの名無しさん 2025/02/06(木) 22:16:32.16 ID:u6r6iDwj]

>>510
C++
https://ideone.com/ywT3qw

>>529からの変更点
・sへのtの文字の出現位置を高速取得（1バイト文字のみに対応）
・sにtの同一文字が3回以上連続して出現する場合に最初と最後以外の位置を省略

[535 デフォルトの名無しさん 2025/02/07(金) 19:14:17.64 ID:UF6GKvr5]

>>500
Wolfram Language

str = "ATGAT"
>> Out[1]= ATGAT

duplicates = str // Characters \
(* { A, T, G, A, T } *) \
// Counts \
(* <| A -> 2, T -> 2, G -> 1 |> *) \
// Select[Function[ 1 < # ]] \
(* <| A -> 2, T -> 2 |> *) \
// Keys \
(* { A, T } *) \
// StringJoin (* "AT" *)
>> Out[2]= AT

[536 デフォルトの名無しさん 2025/02/07(金) 21:12:13.92 ID:n3kvQb3T]

テス

[537 9 2025/02/07(金) 21:20:22.98 ID:dMuAEB5V]

>510 Perl5

https://ideone.com/lceN9R

[538 デフォルトの名無しさん 2025/02/07(金) 22:53:14.41 ID:ovhX7KXo]

>>510 c
https://ideone.com/uYlPLX
・f_537 は537さんのパクリ

[539 9 2025/02/07(金) 23:00:25.46 ID:dMuAEB5V]

>>537
しくった、これ一番短い範囲ではなく間違って一番長い範囲を検出してる。
サンプルデータではたまたま同じ解になるようで、間違いを見落としてしまった。

それから、一番長い（短いにすべきだったが）範囲の検索にわざわざ候補listをsortして[0]番目を
取得しているが無駄だし規模が大きくなると効率よくない

時間あったら直しますわ〜

[540 9 2025/02/07(金) 23:02:20.43 ID:dMuAEB5V]

>>538
あーでも527の方式がいまんとこ一番早いんだな、検証ｔｈｘ

[541 9 2025/02/07(金) 23:04:01.40 ID:dMuAEB5V]

>>540 527 じゃなくて 537ね。ｽﾏｿ

[542 538 2025/02/07(金) 23:08:45.80 ID:ovhX7KXo]

>>540
>>537さん方式は動的にメモリとらなくていいのがいいよね、清々しくていいよね
あと実行時間の値はまぁアテにはならんので参考程度にｗ

[543 デフォルトの名無しさん 2025/02/07(金) 23:41:05.56 ID:qBbgMoXu]

>>500
PowerShell

"T", "CG", "ATA", "CGGA", "ATGAT", "GTTGCA", "CCCCGGG", "ACTGCGAG ", "ATCAGAATA", "TGCCATGACA" |% {
　　"$_ → $(-join ([char[]]$_ | group -case |% {$_.name[$_.count -le 1]}))"
}

[実行結果]
T →
CG →
ATA → A
CGGA → G
ATGAT → AT
GTTGCA → GT
CCCCGGG → CG
ACTGCGAG → ACG
ATCAGAATA → AT
TGCCATGACA → TGCA

[544 9 2025/02/08(土) 00:22:55.52 ID:vma3KbbM]

>>510 Perl5、>>537 の修正版

https://ideone.com/klqLux

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

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

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

[545 9 2025/02/08(土) 00:26:07.95 ID:vma3KbbM]

>>544 List::Utils → List::Util ね。ｽﾏｿ

[546 デフォルトの名無しさん 2025/02/08(土) 08:27:20.39 ID:7bAG/IVE]

>>510
Wolfram Language

s = "DHBICEJAFG"
>> Out[1]= DHBICEJAFG
pattern = "EIC"
>> Out[2]= EIC

shortestMatch = \
(* 全通りの部分文字列を生成する *) \
ReplaceList[ Characters[ s ], {___, x__, ___} -> {x} ] \
(* 短い順、先頭に近い順に並べる *) \
// Sort \
(* 検索文字列の文字を全て含むものを選ぶ *) \
// Select[ ContainAll[ Characters[ pattern ] ] ] \
(* 1つ目を文字列として返す *) \
// Extract[ 1 ] // StringJoin
>> Out[3]= ICE

[547 9 2025/02/08(土) 17:50:15.20 ID:HpUe4TZQ]

>>510 Perl5、>>544 をもう一回だけ改良

https://ideone.com/YkuK1w

改良点：
・検出された範囲の候補を一通りリストに蓄えて、あとでその中から最短のものを探す方式を止めて、
　範囲を検索するループ内のifでその時点までの最短な範囲の判定と記録を行うようにした。
・CPANモジュールList::MoreUtilsのminmaxを使わない。
・コアモジュールList::Utilはminだけ使う。reduceは使わない。

なんだかPerlのコードらしい感じが減って、ベタな感じのコードになってしまいました

[548 デフォルトの名無しさん 2025/02/08(土) 19:59:09.70 ID:EDI8nVtP]

>>510
C++
https://ideone.com/7EHx0H

>>534からの変更点
・minmax_elementを呼び出さずに済むようにして高速化

[549 デフォルトの名無しさん 2025/02/08(土) 20:02:06.41 ID:EDI8nVtP]

>>510
C++
https://ideone.com/TluWQi

>>548では検索文字列が短くて高速化されたか分かりにくかったので、長くして529, 534, 548の
実行時間を比較してみると、効果が顕著に現れた。

[550 警備員[Lv.19] 2025/02/09(日) 03:18:28.07 ID:Y8d2noVo]

>>485
Kotlin
https://paiza.io/projects/RtyGxT2PXZScHW6eucI5ng

[551 警備員[Lv.19] 2025/02/09(日) 03:56:54.57 ID:Y8d2noVo]

>>500
Kotlin
https://paiza.io/projects/eipNjg4meAtA7__e3JTRdg

[552 デフォルトの名無しさん 2025/02/09(日) 12:47:59.38 ID:uN83pfj6]

>>510 c
https://ideone.com/D2AZMK
・両端に着目し、両端のみを更新しつつ調べていく（が、これといってパっとせず）
・f_both_ends はあくまで元の文字列s上を調べていく
・f_both_ends_v2 は「次」「隣」にアクセスしやすくした構造の上を調べていく
・あと実行時間の値ははげしくブレブレなので参考程度にとどめておいてね

[553 デフォルトの名無しさん 2025/02/09(日) 21:29:55.65 ID:do9MXosP]

>>485
R
https://ideone.com/wuW5oV

[554 デフォルトの名無しさん 2025/02/09(日) 21:31:24.58 ID:do9MXosP]

>>510
C++
https://ideone.com/bwvs06

>>548からの変更点
・データ構造を単純化したら速くなった

[555 デフォルトの名無しさん 2025/02/09(日) 21:35:08.87 ID:do9MXosP]

>>510
https://ideone.com/46Tb28
>>549の実行速度比較に554を追加。548は不要な2行を削除した。検索文字列が短いのと長いのの両方をテスト。

[556 警備員[Lv.19] 2025/02/10(月) 13:21:24.86 ID:g+w4FSG9]

>>510
Kotlin

出来たことは出来たが、もっと簡単に出来そうな気がしてきた。

https://paiza.io/projects/RwNXYMH6q3P6v0vx9zbZng

[557 デフォルトの名無しさん 2025/02/10(月) 21:24:31.20 ID:KgR1Tipz]

>>485
C# (IEnumerableとして列挙)
https://ideone.com/UBY8bl

[558 デフォルトの名無しさん 2025/02/11(火) 03:27:04.16 ID:FlAqv/ML]

動画再生回数、登録者数、評価数、コメント数

上2桁、下2桁に04、13、40、44、71、74など
（＋生年月日、IDの数字など）の組み合わせ

業者による忌み数字、不吉数字の嫌がらせ&精神攻撃がキモすぎ

[559 警備員[Lv.20] 2025/02/11(火) 05:48:25.27 ID:Y4Uu1QjJ]

それはお題なのか？それともただの誤爆か？

[560 デフォルトの名無しさん 2025/02/11(火) 06:03:36.08 ID:h8gYOd9x]

糖質でしょ
忌み数字不吉数字とか意味不明なこと言ってるし，それを業者が特定個人を狙って表示する意味も分からんし

[561 デフォルトの名無しさん 2025/02/11(火) 10:54:21.93 ID:E5oVpL7o]

お題
数列が入力されます
ニ番目に小さい数を出力してください

入力：4, 5, 1, 7, 1, 2, 8, 9, 2, 7
出力：2

[562 デフォルトの名無しさん 2025/02/11(火) 11:46:37.94 ID:A5/Zs5AB]

こんちゃ
質問いいでしょうけ
プルダウン（ポップアップ）をUIとしてだすとして
見えている項目名と、実際にパラミータとして出す値を変えたい時はどうしたらよか

[563 9 2025/02/11(火) 14:53:15.78 ID:mMj2PIa8]

>>561 Perl5

$h{$_} = $_ for 4, 5, 1, 7, 1, 2, 8, 9, 2, 7;
@s = sort keys %h;
print "$s[1]\n";


実行結果
~ $ perl 22_561_second.pl
2


Perl5.26以降に付属のList::Utilにはuniq関数があるのでそれを使えば:

use List::Util qw(uniq);
@s = uniq sort 4, 5, 1, 7, 1, 2, 8, 9, 2, 7;
print "$s[1]\n";

[564 警備員[Lv.20] 2025/02/11(火) 16:33:48.19 ID:Y4Uu1QjJ]

>>562
環境や言語やフレームワークを書いて限定しないと色々な環境や言語やフレームワークでの答えが適当に沢山湧いて出て来る可能性あるぞ。
しかも分からない所は適当に解釈してだ。なぜならここはお題スレだから。

[565 デフォルトの名無しさん 2025/02/11(火) 16:37:12.05 ID:WPoAkGuN]

>>561 ruby
https://ideone.com/OI7hWs

>>561 octave
https://ideone.com/36aKUO

>>561 c
https://ideone.com/eDmlMM

[566 デフォルトの名無しさん 2025/02/11(火) 16:40:21.13 ID:gFwXvlnz]

>>561
#!ruby
puts $stdin.gets.chomp.split(",").map{|e| e.to_i}.uniq.sort[1]

[567 デフォルトの名無しさん 2025/02/11(火) 17:43:14.68 ID:7RexIvi8]

>>510 lisp
https://ideone.com/qm4PsV

[568 デフォルトの名無しさん 2025/02/11(火) 17:48:30.95 ID:7RexIvi8]

>>561 lisp
https://ideone.com/g6m1EK

[569 デフォルトの名無しさん 2025/02/11(火) 18:19:05.70 ID:7RexIvi8]

>>568
全然だめでした
取りあえずテスト追加済

[570 デフォルトの名無しさん 2025/02/11(火) 20:45:09.89 ID:hMHygfcC]

>>561
R
https://ideone.com/3beF1j

C++
https://ideone.com/A8hp2f

それぞれ3通りの方法で、大きなデータでの実行時間を比較

[571 デフォルトの名無しさん 2025/02/11(火) 23:21:03.54 ID:Vzh5cLYk]

数列が入力されるので
整数の数列だけでなく浮動小数点数の数列にも対応してくださいね

ニ番目に小さい数がない時
例えば同じ数しか存在しない時や数列の長さが1の時には
解がないことを返してくださいね
例えばその時にMAX値が返ってきたら失格ですよ

[572 565 2025/02/11(火) 23:28:05.14 ID:qmej6t15]

>>561 ocaml
https://ideone.com/aV59Yd

>>561 java
https://ideone.com/PdgusX

[573 9 2025/02/11(火) 23:36:31.53 ID:yxel6cu3]

先に言えよって、感じｗ

[574 デフォルトの名無しさん 2025/02/11(火) 23:48:25.56 ID:E5oVpL7o]

>>571は出題者ではないよ
出題者として申し上げるなら>>571は観点がダサい

[575 デフォルトの名無しさん 2025/02/11(火) 23:50:12.69 ID:HwVbkmdb]

小数対応はともかく
max値を返してしまう人はプログラマ失格かな
あとsortを使ってしまう人は計算量を知らない初心者

[576 デフォルトの名無しさん 2025/02/11(火) 23:53:59.73 ID:E5oVpL7o]

そういうこだわりはアスペルガーにしか思えないな、どうでも良いじゃないですかそんなこと

[577 デフォルトの名無しさん 2025/02/11(火) 23:56:29.96 ID:E5oVpL7o]

こだわりは自分の胸のうちに留めていただきたい、他人に求めたら回答の幅を狭めるだけ、多様性のある回答こそ美しい

[578 デフォルトの名無しさん 2025/02/11(火) 23:57:23.71 ID:HwVbkmdb]

>>576
多くの人はちゃんとnilとかemptyとかNoneなどを返しているよね
プログラマならそこだけは守らなければならない必須事項

[579 デフォルトの名無しさん 2025/02/11(火) 23:59:56.87 ID:E5oVpL7o]

だからそういう、こうじゃないとダメだという態度がアスペルガー仕草なんだってばよ、君が思うのは勝手だが他人に求めるものじゃない

[580 デフォルトの名無しさん 2025/02/12(水) 00:01:10.34 ID:hk2aQo3G]

プログラミングはもっと自由なものなんだよ、思ったとおりにかけば良い

[581 9 2025/02/12(水) 00:03:23.15 ID:yw0CaA/O]

そういう条件は回答を見て思いついた後から言わず先に書くべきでは？
そうでなければ、与えられた短い文とテストデータから、
処理対象データの範囲や要求仕様を読み手が色々解釈しても仕方ないだろ。
後からいろいろ言って批判なんてでもってのほかだと思うが。

[582 9 2025/02/12(水) 00:05:30.21 ID:yw0CaA/O]

出来たもの見て実はこういう条件がありましたってケチつけるのはクソクライアントと一緒だな

[583 デフォルトの名無しさん 2025/02/12(水) 00:13:52.34 ID:SJ0T1N6w]

ざっと見たけどmax()を返してるのはC++の人だけで他は皆まともだ
普段からまともなコード書いてるかどうかバレてしまうから自由が面白い

[584 デフォルトの名無しさん 2025/02/12(水) 00:18:10.68 ID:hk2aQo3G]

好きにしたら良いんやで吉田松陰もそんなこと言ってた気がする

[585 デフォルトの名無しさん 2025/02/12(水) 00:20:24.72 ID:hk2aQo3G]

まともとかバレるとかそういう当て擦りの嫌味ったらしい言い方どこで身につけてきたのあんた、母ちゃんは悲しいよ

[586 デフォルトの名無しさん 2025/02/12(水) 00:22:24.96 ID:Qtl/TEf6]

>>583
関数がINT_MAXを返すのはまともなコードだろ。2番目に小さい数はINT_MAXではありえないから、
返り値がINT_MAXの場合は「なし」と表示すれば良いだけ。

[587 9 2025/02/12(水) 00:28:30.94 ID:yw0CaA/O]

「データが二個未満の場合にはnilを返す。」とか書いとくべき。
でもそういう細かい条件をちまちま指定した窮屈な課題は、つまんなくて回答を造る意欲が減るんだよな。

シンプルで純な課題に対してどういうエレガントでエッセンシャルな回答があるか考えるのが楽しいのであって、
細かいいろんな条件を守る周辺コードで固めるような作業はつまんないから趣味の世界ではやりたくないな

[588 デフォルトの名無しさん 2025/02/12(水) 00:31:16.47 ID:1WuTe288]

普段はプログラム載せるだけだけど、みんな意外と饒舌なんだなw

[589 9 2025/02/12(水) 00:33:57.88 ID:yw0CaA/O]

ここはある意味、回答のｺｰﾄﾞでもって語るスレだからな

[590 デフォルトの名無しさん 2025/02/12(水) 00:35:35.77 ID:kQv2EDFI]

お題にそんな指定ないのに
みんなnilなどを返してるからこのスレの住人たちはセンスいいな

[591 デフォルトの名無しさん 2025/02/12(水) 19:12:16.26 ID:FZJ50oR3]

>>561 lisp (sbcl)
https://ideone.com/Bct7bC

>>561 lisp (clisp)
https://ideone.com/yqfmzh

clispだと何故かsort版の方が速い

[592 デフォルトの名無しさん 2025/02/12(水) 20:45:54.96 ID:JML0DDov]

>>561 ruby
https://ideone.com/svMSSw

>>561 sqlite
https://ideone.com/W02Q5r

[593 デフォルトの名無しさん 2025/02/12(水) 22:44:39.40 ID:Qtl/TEf6]

>>561, 571
>>570のC++のf3をint型の最大値を含むデータにも対応させた。

C#にはint?型があるのですっきり書けるが、
https://ideone.com/oRhDL1

C++ではまあまあすっきり書くにはintへのポインタを返すしかないか。
https://ideone.com/xYnTSD
(該当値が複数の位置に存在する場合にそれらのうちのどれへのポインタを返すかについては
こだわらないものとする)

[594 デフォルトの名無しさん 2025/02/13(木) 12:04:43.08 ID:KGk2Z9bM]

お題：ランダムな数列から任意の並んでいる二つの数同士を足して、その二つの数の間に挿入せよ。
その新しい数が一桁ならそのまま挿入し二桁なら桁同士を足してその二桁の間に挿入せよ。

< 123456789 3 4
> 1237456789

(3+4=7)

< 123456789 6 7
> 123456143789

(6+7=13 1+3=4)

[595 デフォルトの名無しさん 2025/02/13(木) 12:31:31.25 ID:QhFtS6hw]

問題文の記述が下手かよ

[596 デフォルトの名無しさん 2025/02/13(木) 13:27:16.37 ID:J5YSE8js]

>>594 ruby
a=$stdin.gets.chomp.split(" ")
b=a[1].to_i+a[2].to_i
c=(b<9 ? a[1]+b.to_s+a[2] : a[1]+"#{b/10}#{b/10+b%10}#{b%10}"+a[2])
puts a[0].gsub(a[1]+a[2],c)

[597 9 2025/02/13(木) 17:35:13.67 ID:UAfabByi]

>>594　Perl5、見易くするためインデントは全角スペースに置換してあります

for (<DATA>) {
　($s, $a, $b) = split;
　$c = $a + $b;
　$c = $1 . ($1 + $2) . $2 if $c =~ /(\d)(\d)/;
　$s =~ s/$a$b/$a$c$b/g;
　print "$s\n";
}
__DATA__
123456789 3 4
123456789 6 7
123456789 8 9
3141592653589793238462643383279502884197169399375105820974944 9 7


実行結果
~ $ perl 22_594.pl
1237456789
123456143789
123456781879
3141592653589176793238462643383279502884191767169399375105820917674944

[598 デフォルトの名無しさん 2025/02/13(木) 20:12:01.16 ID:3SfOseF2]

>>594
題意が以下の通りだとして、PowerShell (エラーチェックは省略)

　自然数x, i, j (i + 1 = jを満たす) が与えられる。xの上i桁目の数字をx[i]で表す。
　x[i]とx[j]の和をyとして、

　・yが1桁のとき、yをx[i]とx[j]の間に挿入せよ
　・yが2桁のとき、y[1]とy[2]の和をy[1]とy[2]の間に挿入してから、yをx[i]とx[j]の間に挿入せよ

function f($x, $i, $j)
{
　　$s = [string]$x
　　$y = [int][string]$s[$i - 1] + [int][string]$s[$j - 1]
　　if ($y -lt 10) {
　　　　$s.insert($i, $y)
　　} else {
　　　　$s.insert($i, 11 * $y)
　　}
}

(123456789, 3, 4), (123456789, 6, 7) |% {
　　"< $($_[0]) $($_[1]) $($_[2])"
　　"> $(f $_[0] $_[1] $_[2])", ""
}

[実行結果]
< 123456789 3 4
> 1237456789

< 123456789 6 7
> 123456143789

[599 9 2025/02/13(木) 20:24:48.49 ID:UAfabByi]

数学屋さんかいなｗ
i,jの「3 4」とか「６ 7」は桁の位置をしていしているのではなく数値列の中にある数字を指定するんジャマイカ
とオレは解釈したが

[600 デフォルトの名無しさん 2025/02/13(木) 20:34:25.67 ID:3SfOseF2]

>>599
そうか。だとすれば、

function f($x, $i, $j)
{
　　$s = [string]$x
　　$y = $i + $j
　　if ($y -ge 10) {$y *= 11}
　　$s -replace "$i$j", "$i$y$j"
}

(123456789, 3, 4), (123456789, 6, 7), (123456789, 8, 9), ("3141592653589793238462643383279502884197169399375105820974944", 9, 7) |% {
　　"< $($_[0]) $($_[1]) $($_[2])"
　　"> $(f $_[0] $_[1] $_[2])", ""
}

[実行結果]
< 123456789 3 4
> 1237456789

< 123456789 6 7
> 123456143789

< 123456789 8 9
> 123456781879

< 3141592653589793238462643383279502884197169399375105820974944 9 7
> 3141592653589176793238462643383279502884191767169399375105820917674944

[601 デフォルトの名無しさん 2025/02/13(木) 20:45:01.39 ID:KiG3F5Wd]

>>561 c
https://ideone.com/ZyWoVM

>>594 ruby
https://ideone.com/gp9Fvp

[602 9 2025/02/13(木) 20:52:32.26 ID:UAfabByi]

なんでこの人はコーデイングするのがこんなに早いんだろう…

[603 デフォルトの名無しさん 2025/02/13(木) 22:58:07.29 ID:bC7pFAVH]

>>594　Rust

fn f(input: &str, a: u32, b:u32) -> String {
let src = format!("{a}{b}");
let dst = if a + b < 10 {
format!("{a}{x}{b}", x = a + b)
} else {
format!("{a}{x}{y}{z}{b}", x = 1, y = 1 + a + b - 10, z = a + b - 10)
};
use itertools::Itertools;
input.split(&src).join(&dst)
}

fn main() {
assert_eq!(f("123456789", 3, 4), "1237456789");
assert_eq!(f("123456789", 6, 7), "123456143789");
assert_eq!(f("3141592653589793238462643383279502884197169399375105820974944", 9, 7),
"3141592653589176793238462643383279502884191767169399375105820917674944");
}

[604 デフォルトの名無しさん 2025/02/13(木) 23:47:12.83 ID:bC7pFAVH]

>>561　Rust

fn second_smallest<T: Copy + Ord>(input: &[T]) -> Option<T> {
use std::cmp::Ordering::{Equal, Greater, Less};
input
.iter()
.copied()
.fold(None, |state, t| match state {
Some((_t0, Some(t1))) if t >= t1 => state,
Some((t0, _)) => match Ord::cmp(&t, &t0) {
Less => Some((t, Some(t0))),
Equal => state,
Greater => Some((t0, Some(t))),
},
None => Some((t, None)),
})
.and_then(|(_t0, t1option)| t1option)
}

fn main() {
assert_eq!(second_smallest(&[4, 5, 1, 7, 1, 2, 8, 9, 2, 7, 1]), Some(2));
assert_eq!(second_smallest(&[1, 1, 1]), None);
assert_eq!(second_smallest(&[] as &[i32]), None);
}

[605 デフォルトの名無しさん 2025/02/14(金) 17:55:06.91 ID:L6dJMbYJ]

わけがわからん
アセンブラじゃあるまいし

[606 デフォルトの名無しさん 2025/02/14(金) 18:42:18.21 ID:RXjqXFcF]

わからないのはどのへんなんだろう？
・型がジェネリックになっている点
・代入文がないなど関数型プログラミングになっている点
・パターンマッチングが使われている点
いずれも最近は対応している言語が増えてるような

[607 デフォルトの名無しさん 2025/02/14(金) 23:21:45.00 ID:bNo2F1oE]

可読性の良さから高階関数を使ったメソッドチェーンが一般的になってきたね
マイクロソフトがC#などでLINQ広めたのがきっかけで各言語もその有用性から導入するようになった

[608 デフォルトの名無しさん 2025/02/14(金) 23:42:29.57 ID:PVqLPxMJ]

お題：ランダムな英文字列が与えられる。隣り合う英文字が同じ大文字だった場合、その間にその大文字の小文字を挿入せよ

In < abcDDefGG
Out > abcDdDefGgG

[609 デフォルトの名無しさん 2025/02/15(土) 00:16:29.67 ID:aVKCg5xf]

>>608 ruby
while 1
s=DATA.gets.chomp
exit if s==""
t=s.gsub(%r|([A-Z])\1|){$1+$1.downcase+$1}
puts "IN < #{s}\nOUT > #{t}"
end
__END__
abcDDefGG

[610 デフォルトの名無しさん 2025/02/15(土) 00:16:34.18 ID:f9ERvXXy]

>>594 dart
https://ideone.com/uQxzo1

>>608 ruby
https://ideone.com/pwoRRH

[611 デフォルトの名無しさん 2025/02/15(土) 00:28:45.42 ID:/PgyVRU9]

>>606
正規表現みたい非人間的な書式はやめようぜっての

[612 デフォルトの名無しさん 2025/02/15(土) 00:39:27.81 ID:rssRTGdz]

>>608
PowerShell

function f($s)
{
　　-join $(
　　　　foreach ($i in 0..($s.length - 2)) {
　　　　　　$s[$i]
　　　　　　if ($s[$i] -ne $s[$i + 1]) {continue}
　　　　　　if ($s[$i] -lt [char]"A" -or $s[$i] -gt [char]"Z") {continue}
　　　　　　([string]$s[$i]).ToLower()
　　　　}
　　　　$s[$i + 1]
　　)
}

"abcDDefGG", "abcDDDfGG" |% {"$_ → $(f $_)"}

[実行結果]
abcDDefGG → abcDdDefGgG
abcDDDfGG → abcDdDdDfGgG

[613 デフォルトの名無しさん 2025/02/15(土) 01:01:01.24 ID:qzrI3kKZ]

>>608　Rust

fn f(input: &str) -> String {
　let mut output = String::new();
　let mut pre_uppercase = None;
　for char in input.chars() {
　　if Some(char) == pre_uppercase {
　　　output.push(char.to_ascii_lowercase());
　　}
　　output.push(char);
　　pre_uppercase = char.is_ascii_uppercase().then_some(char);
　}
　output
}

fn main() {
　assert_eq!(f("abcDDefGG"), "abcDdDefGgG");
　assert_eq!(f("abcDDDfGG"), "abcDdDdDfGgG");
}

[614 デフォルトの名無しさん 2025/02/15(土) 09:21:24.60 ID:XILc/8JX]

>>608 ruby
https://ideone.com/nHcphN

>>608 dart
https://ideone.com/NxwW8Y

[615 614 2025/02/15(土) 10:02:25.10 ID:UI50KRFJ]

>>608 dart
https://ideone.com/2E5Rxy

[616 9 2025/02/15(土) 10:36:35.12 ID:1WENuqRv]

>>608 Perl5、肯定先読みと置換の小文字変換

s/([A-Z])(?=\1)/\1\l\1/g, print for <DATA>;
__DATA__
abcDDefGG
abcDDDefGGG


実行結果
C:\Home>perl 22_608_ins_l.pl
abcDdDefGgG
abcDdDdDefGgGgG

[617 9 2025/02/15(土) 10:39:20.52 ID:1WENuqRv]

>>611
お断り〜します〜♪
　　　 ハハ
　　　(ﾟωﾟ)
　((⊂ﾉ 　ﾉつ))
　　 (＿⌒ヽ
εﾆ≡　)ﾉ`Ｊ

[618 デフォルトの名無しさん 2025/02/15(土) 10:40:34.16 ID:+yYMeR0h]

>>594 >>608 lisp
https://ideone.com/W5gGfD

[619 615 2025/02/15(土) 13:20:38.24 ID:eC3jFbuY]

>>608 java
https://ideone.com/YfufZz

>>616
＿人人人人人人人人人人人人＿
＞　置換の小文字変換！？　＜
￣Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^￣

勉強になりました

[620 デフォルトの名無しさん 2025/02/15(土) 21:05:44.70 ID:rssRTGdz]

>>612は文字列長が1文字の場合にバクがあった。PowerShellの0..-1は空(から)ではなく0, -1になるのが
原因 (Rの0:-1も同様)。修正するには、fの最初に if ($s.length -lt 2) {return $s} を挿入する。

[621 デフォルトの名無しさん 2025/02/15(土) 21:06:37.89 ID:rssRTGdz]

>>561
C++
https://ideone.com/bQBKIM
C#のヌル許容型と同じ挙動のnullable型を自作し、>>593のC#のmin2関数をジェネリック化、
ポインタ参照化して移植した。

https://ideone.com/p2LNC9
593のC++のmin2関数と実行速度を比較する¹と30%ほど遅い。文字列型や可変長数値型と
違って最大値が存在する固定長数値型では、それを利用するf593の方が良い。

──
¹ Microsoft C++では100回繰り返しテストが最適化され1回しか実行されない

[622 デフォルトの名無しさん 2025/02/15(土) 21:52:48.39 ID:qa0m30Tb]

>>621
最大値をundefined代わりに使ってはいけないと指摘があったのにまだ使っているのかいな
そのコードで入力数列がこうだった場合
vector<int> a = {IntMax - 1, IntMax};
2番目に小さい数として正解のintMaxを返さなければならない

[623 デフォルトの名無しさん 2025/02/15(土) 22:00:12.34 ID:rssRTGdz]

>>622
>>593のC++プログラムの実行結果を参照。入力数列にINT_MAXが含まれる場合でも問題ない。

[624 デフォルトの名無しさん 2025/02/15(土) 22:09:09.66 ID:qa0m30Tb]

>>623
それはm1とm2を間接にポインタで持つために遅くなっているf593()
m1とm2を直接に整数で持つため速いf3()はIntMaxに対応できていない

[625 デフォルトの名無しさん 2025/02/15(土) 22:24:28.09 ID:rssRTGdz]

>>624
>>621の速度比較テストに>>570のf3も追加
https://ideone.com/scnfdu

ポインタで持つf593との比で、整数で持つf570は6%速いだけ。一方、null許容型のf621は29%も遅い。
最大値が存在する型ではそれを利用する方が良いという結論に変わりはない。

[626 デフォルトの名無しさん 2025/02/15(土) 22:29:41.23 ID:rssRTGdz]

まあ、同じ値の要素が大量に存在する入力データではf570は遅くなるが、平均的な速度はf570の方が速い。

[627 デフォルトの名無しさん 2025/02/15(土) 22:31:16.05 ID:rssRTGdz]

>>626はf570じゃなくてf593だった。

[628 デフォルトの名無しさん 2025/02/15(土) 22:42:01.35 ID:v2QOLp/q]

f593でローカル変数へのポインタを返し得るのは如何かと

[629 デフォルトの名無しさん 2025/02/15(土) 23:34:59.77 ID:rssRTGdz]

>>628
返しえないでしょ。

[630 デフォルトの名無しさん 2025/02/15(土) 23:46:12.83 ID:qa0m30Tb]

>>625
まずnullableのコードがおかしい
例えばoverload(op)のこれ

if (y.isNull) return false; \
return x op y.value; \

Nullだとfals eとなり
opの計算結果次第でもfal seとなり
両者を区別できない

[631 デフォルトの名無しさん 2025/02/15(土) 23:47:32.80 ID:qa0m30Tb]

>>625
あとvector扱うコードは倫理的に際どいかな
長さ0でないことを調べずに
いきなりint *m1 = &a[0], m2 = &y;
今回は長さ0の時に*m1をアクセスしないから論理的にギリセーフだけど際どい

そのへんのトリッキーさも含めて
(もしあれば)最小値も返す場合
(もしあれば)3番目の最小値も返す場合など
このIntMax方式は破綻すると思う

[632 デフォルトの名無しさん 2025/02/15(土) 23:52:31.08 ID:rssRTGdz]

>>630
>>621に書いた通り、C#のヌル許容型T? (Nullable<T>のエイリアス) の挙動に従っただけだから。
文句があるならMicrosoftに言ってくれ。

[633 9 2025/02/16(日) 06:28:07.79 ID:GnMUCCm7]

qa0m30Tb の回答はどれよ？

[634 デフォルトの名無しさん 2025/02/16(日) 08:09:49.66 ID:v+IcfGmt]

いるよねえ他人の回答に文句だけつけて自分では回答しないやつ

[635 デフォルトの名無しさん 2025/02/16(日) 08:16:54.29 ID:v+IcfGmt]

他人の回答が間違いとなるようにお題を解釈するのは知的なことではないよバカの所業だよ

[636 デフォルトの名無しさん 2025/02/16(日) 08:20:29.71 ID:eNZyrnPC]

そんなことより>>616のワンライナーがカッコよくてほれぼれする

[637 デフォルトの名無しさん 2025/02/16(日) 10:58:48.51 ID:EXJYkLn8]

帰ったと思ったらまたやってんのｗ

[638 デフォルトの名無しさん 2025/02/16(日) 15:14:38.18 ID:8bpH8MuA]

コンパイラ警告無視するのが知的な事だと思ってそうだな

[639 9 2025/02/16(日) 15:45:59.98 ID:GnMUCCm7]

回答のｺｰﾄﾞでもって語ってほしいなぁ

[640 デフォルトの名無しさん 2025/02/17(月) 13:08:08.60 ID:lz3iaMcC]

お題：ランダムな数列が与えられる。隣り合う数字が偶数同士の時、あいだに0を。奇数同士の時は1を挿入し、それ以外は何も挿入しない

In < 123346
Out > 12313406

[641 デフォルトの名無しさん 2025/02/17(月) 13:47:54.59 ID:1CKZ5rpi]

>>640 ruby
DATA.readlines(chomp:1).map{|e|
a=e.split("").map{|f| f.to_i}
(0..a.size-2).each{|n|
a[n]=a[n]*10 if (a[n]%2==0 && a[n+1]%2==0)
a[n+1]=a[n+1]+10 if (a[n]%2==1 && a[n+1]%2==1)}
puts "IN < #{e}\nOUT > #{a.map{|f| f.to_s}.join}"}
__END__
123346

[642 デフォルトの名無しさん 2025/02/17(月) 20:02:39.61 ID:SzDlV4TD]

>>640 lisp
https://ideone.com/DV9DeR

[643 デフォルトの名無しさん 2025/02/17(月) 20:47:46.22 ID:2enU2rA/]

>>640
PowerShell (一般的な文字コードを想定)

function f([string]$s)
{
　　$rprev = 2
　　-join ([char[]]$s |% {
　　　　$r = $_ % 2
　　　　if ($r -eq $rprev) {$r}
　　　　$rprev = $r
　　　　$_
　　})
}

123346, 12333468, 1, "" |% {"$_ → $(f $_)"}

[実行結果]
123346 → 12313406
12333468 → 123131340608
1 → 1
→

[644 デフォルトの名無しさん 2025/02/17(月) 20:48:16.10 ID:2enU2rA/]

正規表現置換なら、

function f($s)
{
　　$s -replace "[02468](?=[02468])", "$&0" -replace "[13579](?=[13579])", "$&1"
}

1回で済ますなら、

function f($s)
{
　　[RegEx]::Replace($s, "[02468](?=[02468])|[13579](?=[13579])", {$_ = $args[0].value[0]; "$_$($_ % 2)"})
}

[645 デフォルトの名無しさん 2025/02/17(月) 20:58:11.16 ID:UxhkW11K]

>>640　Rust

fn f(input: &[u8]) -> Vec<u8> {
　input.windows(2).fold(Vec::new(), |mut vec, w| {
　　if vec.is_empty() {
　　　vec.push(w[0]);
　　}
　　if (w[0] ^ w[1]) & 1 == 0 {
　　　vec.push(w[0] & 1 + b'0');
　　}
　　vec.push(w[1]);
　　vec
　})
}

fn main() {
　assert_eq!(f(b"123346"), b"12313406");
　assert_eq!(f(b"12333468"), b"123131340608");
}

[646 デフォルトの名無しさん 2025/02/18(火) 10:32:01.38 ID:Spp0fdd/]

>>645
そうやればいいのか、なるほどね

[647 デフォルトの名無しさん 2025/02/18(火) 17:51:16.96 ID:ZRfTlf8i]

Vecのnewやpushなど普通にcollectに任せる手もあるね
条件付き挿入は汎用にOptionで取捨を示してflat_mapとflattenでも可能
前値など状態を保ちつつ1つにまとめるならfoldでイテレータに流すならscan
一例としてこんな感じ

fn f(input: &[u8]) -> Vec<u8> {
　input
　　.iter()
　　.scan(None, |pre, &x| {
　　　Some([
　　　　pre.replace(x & 1)
　　　　　.and_then(|p| (p == x & 1).then_some(p + b'0')),
　　　　Some(x),
　　　])
　　})
　　.flat_map(|list| list.into_iter().flatten())
　　.collect()
}

>>640
Rust

[648 デフォルトの名無しさん 2025/02/19(水) 21:30:14.30 ID:LKzHskwz]

>>640
>>643-644の3つのfを上から順にf1, f2, f3とし、長い文字列を引数として呼び出したときの
実行時間を比較すると、

$s = -join (1..10000)
$t = 1..3 |% {(iex "measure-command {f$_ $s}").ticks}
$tmin = ($t | measure -min).minimum
1..3 |% {"f$_`: {0:0.00}倍" -f ($t[$_ - 1] / $tmin)}

[実行結果の一例]
f1: 34.78倍
f2: 1.00倍
f3: 14.93倍

大差でf2 < f3 < f1となった。インタプリタ言語のコード実行は遅いので、処理を自分で
書くほど遅くなり、ライブラリ関数等に丸投げすれば速くなることによる。

https://ideone.com/GVewWL
コンパイラ言語のC#で同様の比較をすると (PowerShellより速いので文字列を長くし、
f1の改良版としてStringBuilder使用のf4を追加した)、当然f4< f1 < f2 < f3になった。

[649 デフォルトの名無しさん 2025/02/19(水) 21:58:22.55 ID:Hs/awmG/]

>>647
関数型でタブーの可変な変数宣言してもよいなら、もっと簡単になるね。

fn f(input: &[u8]) -> Vec<u8> {
　let mut pre = None;
　input
　　.iter()
　　.flat_map(|&x| {
　　　[
　　　　pre.replace(x & 1)
　　　　　.and_then(|p| (p == x & 1).then_some(p + b'0')),
　　　　Some(x),
　　　]
　　　.into_iter()
　　　.flatten()
　　})
　　.collect()
}

[650 デフォルトの名無しさん 2025/02/20(木) 23:25:43.81 ID:Zfo8kSSQ]

mutableの使用は必要最小限が望ましいが
mutableを使えない言語は実用的ではない

[651 警備員[Lv.21] 2025/02/22(土) 15:11:12.54 ID:nEyoRU5r]

>>640
Perl5
https://paiza.io/projects/gW_sI1_VqokddmYSJ6Lj2A

[652 警備員[Lv.21] 2025/02/22(土) 15:42:54.65 ID:nEyoRU5r]

>>640
Kotlin
https://paiza.io/projects/mAEXhhFdJiHVQWYtHvIP-g

[653 警備員[Lv.21] 2025/02/22(土) 15:53:04.03 ID:nEyoRU5r]

>>640
C
https://paiza.io/projects/7L9vpqOvFcbZfv9vO5GPvA

[654 デフォルトの名無しさん 2025/02/22(土) 23:33:07.08 ID:k7PDvk0j]

>>640
Haskell
https://ideone.com/U3SvTZ

[655 警備員[Lv.21] 2025/02/24(月) 18:11:14.44 ID:Ikw9MrIX]

>>608

>>651とかとアルゴリズムはほぼ同じ。これといった捻りはない。
よく分からないが5chに書き込みがブロックされたのでURLのコロンまでは削った。

Perl
//paiza.io/projects/zAqms-VVEWIMhcgr8AV6Pw
Kotlin
//paiza.io/projects/iu8mTSyKsxqWx_T51Wpj4Q
C
//paiza.io/projects/bDkj3tRF_KmiBL67miRxyA

[656 デフォルトの名無しさん 2025/02/26(水) 21:33:47.93 ID:rkiIsmEI]

お題: Python の int.bit_count()

65535 → 16
15 → 4
6 → 2
1 → 1
0 → 0
-1 → 1
-6 → 2
-15 → 4
-65535 → 16

[657 デフォルトの名無しさん 2025/02/26(水) 23:29:03.38 ID:Gl9HHMVG]

>>656
C++20
https://paiza.io/projects/R-sSq9oCAOmG17wk6c5naw

[658 デフォルトの名無しさん 2025/02/27(木) 00:23:41.10 ID:TOGelnHV]

>>656
Rust

fn bit_count(x: i64) -> usize {
const MAGIC_1: u64 = 0x5555555555555555; // 0101..0101
const MAGIC_2: u64 = 0x3333333333333333; // 0011..0011
const MAGIC_3: u64 = 0x0f0f0f0f0f0f0f0f;
const MAGIC_4: u64 = 0x00ff00ff00ff00ff;
const MAGIC_5: u64 = 0x0000ffff0000ffff;
const MAGIC_6: u64 = 0x00000000ffffffff;

let x = x.unsigned_abs();
let x = (x & MAGIC_1) + ((x >> 1) & MAGIC_1);
let x = (x & MAGIC_2) + ((x >> 2) & MAGIC_2);
let x = (x & MAGIC_3) + ((x >> 4) & MAGIC_3);
let x = (x & MAGIC_4) + ((x >> 8) & MAGIC_4);
let x = (x & MAGIC_5) + ((x >> 16) & MAGIC_5);
let x = (x & MAGIC_6) + ((x >> 32) & MAGIC_6);
x as usize
}

fn main() {
assert_eq!(bit_count(65535), 16);
assert_eq!(bit_count(15), 4);
assert_eq!(bit_count(6), 2);
assert_eq!(bit_count(1), 1);
assert_eq!(bit_count(0), 0);
assert_eq!(bit_count(-1), 1);
assert_eq!(bit_count(-6), 2);
assert_eq!(bit_count(-15), 4);
assert_eq!(bit_count(-65535), 16);
}

[659 デフォルトの名無しさん 2025/02/27(木) 08:26:19.30 ID:LSRTW28H]

>>656 Rust

trait BitCount {
　fn bit_count(&self) -> usize;
}
impl BitCount for i32 {
　fn bit_count(&self) -> usize {
　　self.unsigned_abs().count_ones() as usize
　}
}
use num::{BigInt, One};
impl BitCount for BigInt {
　fn bit_count(&self) -> usize {
　　self.iter_u64_digits().map(|x| x.count_ones() as usize).sum()
　}
}

fn main() {
　for (input, output) in [(65535, 16), (15, 4), (6, 2), (1, 1), (0, 0), (-1, 1), (-6, 2), (-15, 4), (-65535, 16)] {
　　assert_eq!(input.bit_count(), output);
　}
　assert_eq!(BigInt::from(-1).bit_count(), 1);
　assert_eq!((BigInt::from(2).pow(1_000_000_000) - BigInt::one()).bit_count(), 1_000_000_000);
}

[660 デフォルトの名無しさん 2025/02/28(金) 01:30:55.49 ID:1HSOHgVq]

intは処理単位のことなんだけどな
何ビットで表現できるかという意味ではない

[661 9 2025/02/28(金) 03:12:43.15 ID:MEvV9q87]

負の場合に表現可能なビット数を配慮しないとPython の int.bit_count()と同じ結果にならないんジャマイカじゃまいか
たぶんPythonの整数がbigintのせいだとおもう
絶対値とってpopcountとかやらないと意外とあれこれ書いてﾌﾟﾁ長めのコードになりそうなおかん

[662 デフォルトの名無しさん 2025/02/28(金) 23:07:16.17 ID:SRu+xdWw]

よく見たらみんな絶対値をとったりbigintを使ったりしてるな

[663 デフォルトの名無しさん 2025/03/01(土) 20:18:20.34 ID:H8RpZRUP]

>>656
PowerShellのBigIntなら、

$b = @(0)
1..8 |% {$b += $b |% {$_ + 1}}

function bit_count([BigInt]$n)
{
　　($b[[BigInt]::Abs($n).ToByteArray()] | measure -sum).Sum
}

65535, 15, 6, 1, 0, -1, -6, -15, -65535, [BigInt]::Pow(123, 45) |% {
　　"$_ → $(bit_count $_)"
}

[実行結果]
65535 → 16
15 → 4
6 → 2
1 → 1
0 → 0
-1 → 1
-6 → 2
-15 → 4
-65535 → 16
11110408185131956285910790587176451918559153212268021823629073199866111001242743283966127048043 → 159

[664 デフォルトの名無しさん 2025/03/01(土) 20:19:24.06 ID:H8RpZRUP]

お題：1からnまでの自然数のビット単位での総排他的論理和1 ⊕ 2 ⊕ 3 ⊕ … ⊕ nを求める
関数を作り、n = 123456789, 12345678901234567890のときの値を表示せよ。

[665 デフォルトの名無しさん 2025/03/01(土) 21:19:28.22 ID:5VrbV50/]

A003815かな

[666 デフォルトの名無しさん 2025/03/01(土) 21:32:49.43 ID:UfbLQAky]

数学の試験で中間式を省いて解答だけ書くタイプw

[667 デフォルトの名無しさん 2025/03/01(土) 23:41:19.76 ID:+HRoh0yF]

まあ数列の問題ならOEISを見てみるよな

[668 デフォルトの名無しさん 2025/03/02(日) 01:21:29.93 ID:xdmIFouH]

>> 664 　Rust
fn f(n: u64) -> u64 {
　// f(n) = 1⊕2⊕3⊕...⊕n とすると (2k)⊕(2k+1)=1 であるから 1⊕1=0 より
　// f(4k+1) = (4k+1)⊕(4k)⊕(4k-1)⊕(4k-2)⊕f(4k-3) = f(4(k-1)+1) = ... = f(1) = 1
　// f(4k+3) = (4k+3)⊕(4k+2)⊕f(4k+1) = 0
　// f(4k) = (4k)⊕f(4k-1) = 4k
　// f(4k+2) = (4k+2)⊕f(4k+1) = (4k+2)⊕1 = 4k+3
　match n % 4 {
　　0 => n,
　　1 => 1,
　　2 => n + 1,
　　3 => 0,
　　_ => unreachable!(),
　}
}

fn main() {
　for n in [123456789, 12345678901234567890] {
　　println!("f({n}) = {fn}", fn = f(n));
　}
}
出力
f(123456789) = 1
f(12345678901234567890) = 12345678901234567891

[669 デフォルトの名無しさん 2025/03/11(火) 21:18:30.26 ID:Qmk3F8/1]

>>656
PowerShellでもPopCountがいつの間にか使えるようになっていた。Version 7.5.0で動作確認。

function bit_count($n)
{
　　[BigInt]::PopCount([BigInt]::Abs($n))
}

65535, 15, 6, 1, 0, -1, -6, -15, -65535, [BigInt]::Pow(123, 45) |% {
　　"$_ → $(bit_count $_)"
}

実行結果は>>663と同じ。

[670 デフォルトの名無しさん 2025/03/13(木) 20:35:03.45 ID:QP/8WHEA]

お題：数列が入力される。元の数列に逆順にした数列を減算したときの値を出力せよ

In < 12345
OUt > -41976 (12345 - 54321)

[671 デフォルトの名無しさん 2025/03/13(木) 21:13:53.77 ID:SRpNsp20]

>>670
PowerShell

function f([BigInt]$n)
{
　　$c = [char[]][string]$n
　　$n - [BigInt]-join $c[-1..-$c.length]
}

12345, [BigInt]::Pow(12, 34) |% {"$_ → $(f $_)"}

[実行結果]
12345 → -41976
4922235242952026704037113243122008064 → 314233029528909439273950854852378624

[672 デフォルトの名無しさん 2025/03/14(金) 02:10:51.25 ID:wjeVVi0w]

>>671
12の34乗は合っているけどその後の差がおかしくない？
4922235242952026704037113243122008064 から
4608002213423117304076202592425322294 を引いて
314233029528909399960910650696685770 が正解のところ
314233029528909439273950854852378624 となっているよ
正解は1の位が「4 - 4 = 0」になるはずだよね

>>670 Rust 逆文字列を生成する版

use num::BigInt;

fn odai(input: &str) -> Option<String> {
　let rev_input: String = input.chars().rev().collect();
　let x: BigInt = input.parse().ok()?;
　let y: BigInt = rev_input.parse().ok()?;
　Some((x - y).to_string())
}

fn main() {
　assert_eq!(odai("12345"), Some("-41976".to_string()));
　assert_eq!(odai("4922235242952026704037113243122008064"), Some("314233029528909399960910650696685770".to_string()));
}

[673 デフォルトの名無しさん 2025/03/14(金) 02:30:00.58 ID:wjeVVi0w]

>>670 Rust 逆文字列を生成しない＆整数ジェネリック版
use num::{BigInt, CheckedAdd, CheckedMul, CheckedSub, FromPrimitive};

fn chars_to_integer<X>(input: impl Iterator<Item = char>) -> Option<X>
　where X: FromPrimitive + CheckedMul + CheckedAdd,
{
　let (zero, ten) = (X::from_u32(0).unwrap(), X::from_u32(10).unwrap());
　input
　　.map(|c| X::from_u32(c.to_digit(10)?))
　　.try_fold(zero, |acc, x| acc.checked_mul(&ten)?.checked_add(&x?))
}

fn odai<X>(input: &str) -> Option<X>
　where X: FromPrimitive + CheckedMul + CheckedAdd + CheckedSub,
{
　let x = chars_to_integer::<X>(input.chars())?;
　let y = chars_to_integer::<X>(input.chars().rev())?;
　x.checked_sub(&y)
}

fn main() {
　assert_eq!(odai::<i64>("12345"), Some(-41976));
　assert_eq!(odai::<BigInt>("4922235242952026704037113243122008064"), Some("314233029528909399960910650696685770".parse::<BigInt>().unwrap()));
}

[674 デフォルトの名無しさん 2025/03/14(金) 20:19:17.17 ID:Imul3vYR]

>>672
確かに間違っていた。PowerShellの旧ヴァージョンでは [BigInt]文字列 と書くだけで
文字列をBigInt型に正確に変換できるから>>671のプログラムでも正しい結果が得られるが、
新ヴァージョンではdouble経由での変換に仕様変更されたようで誤差が生じてしまうから
[BigInt]::Parse(文字列) と書かなければならなくなった。

[675 デフォルトの名無しさん 2025/03/14(金) 21:36:16.55 ID:pC/XkvI4]

数列の長さは指定されていない。

10 INPUT "0-9";I
20 PRINT "0"
30 END

[676 デフォルトの名無しさん 2025/03/15(土) 19:04:58.28 ID:GCbQqql0]

>>673
これらのwhere~は何という名称ですか？

>　where X: FromPrimitive + CheckedMul + CheckedAdd,
>　where X: FromPrimitive + CheckedMul + CheckedAdd + CheckedSub,

[677 9 2025/03/16(日) 00:12:31.12 ID:8GU62dKf]

>>670 Perl5

use bigint;
print $_ - reverse($_), "\n" for 12345, 4922235242952026704037113243122008064;


実行結果

$ perl 22_670_reverse_minus_biginit.pl
-41976
314233029528909399960910650696685770

[678 警備員[Lv.23] 2025/03/16(日) 17:25:01.96 ID:wlGuyFJ7]

>>670
Kotlin

文字列にしてひっくり返しているだけの何の捻りもないプログラム

https://paiza.io/projects/VBq2l9lhzmUxVo6xAMuAHg

[679 デフォルトの名無しさん 2025/03/16(日) 22:59:41.54 ID:wtk+s/+W]

>>670
PowerShellでジェネリック化(もどき?)
途中式や結果が入力値の型で表せない場合は$nullを返す。

function f($n)
{
　　$T = $n.GetType()
　　$s = [string]$n
　　try {
　　　　$n - $T::Parse(-join $s[-1..-$s.Length]) -as $T
　　} catch {
　　　　$null
　　}
}

12345, [BigInt]::Pow(12, 34), [byte]12, [sbyte]12, [sbyte]123, -123 |% {
　　"[$($_.GetType())]$_ → $(f $_)"
}

-- 実行結果 --
[int]12345 → -41976
[bigint]4922235242952026704037113243122008064 → 314233029528909399960910650696685770
[byte]12 →
[sbyte]12 → -9
[sbyte]123 →
[int]-123 →

[680 デフォルトの名無しさん 2025/03/16(日) 23:01:39.52 ID:6JX6mCC/]

お題：36桁以下の負でない整数で16進表記が10進表記の部分文字列であるものをすべて求めて下さい。

(例)
・1の16進表記1は10進表記1の部分文字列です
・123の16進表記7Bは10進表記123の部分文字列ではありません
・357440の16進表記57440は10進表記357440の部分文字列です

※遅い言語では15桁以下で解いても構いません

[681 デフォルトの名無しさん 2025/03/16(日) 23:59:39.36 ID:qWmLE6LP]

>>676
where句だよ
型Xのトレイト境界を宣言してる

[682 9 2025/03/18(火) 16:05:22.66 ID:GYPHuJM6]

>>680 Perl5、ナイーブな処理方式だと時間がかかり過ぎで最後まで解けないおそれがあるが、なかなかほかに回答者が現れないし、
出現傾向を見るだけでも…と思って、16進数の桁にa-fの現れる値をskipするナイーブな処理方法で。

$m = sprintf '%x', 9 x 15; # 10進で15桁まで
print $m . ' '. hex($m)."\n";
$m =~ s/[a-f]/9/g;
print "1 .. 0x$m\n";
print "".localtime."\n";
for (1 .. $m) {
　$d = hex($_);
　if (0 <= index($d, $_)) {
　　$n++;
　　print "$d, 0x$_\n";
　}
}
print "".localtime."\n";
print "$n count found";

[683 9 2025/03/18(火) 16:07:07.28 ID:GYPHuJM6]

>>682
実行結果 (改行数を減らすため適度につなげてます)
$ perl 22_680_hex_substr_1.pl
38d7ea4c67fff 999999999999999
1 .. 0x3897994967999
Tue Mar 18 09:15:31 2025
1, 0x1　　 2, 0x2　　 3, 0x3　　 4, 0x4　　 5, 0x5　　 6, 0x6　　 7, 0x7　　 8, 0x8　　 9, 0x9
357440, 0x57440　　 357441, 0x57441　　 357442, 0x57442　　 357443, 0x57443　　 357444, 0x57444
357445, 0x57445　　 357446, 0x57446　　 357447, 0x57447　　 357448, 0x57448　　 357449, 0x57449
1079653, 0x107965　　 1081713, 0x108171　　 1122966, 0x112296　　 1123079, 0x112307　　 1123080, 0x112308
2246166, 0x224616　　 3369253, 0x336925　　 3371313, 0x337131　　 3412566, 0x341256
4494393, 0x449439　　 4494400, 0x449440　　 4535653, 0x453565
5658739, 0x565873　　 5658740, 0x565874　　 5660793, 0x566079　　 5660800, 0x566080　　 5702166, 0x570216
6783879, 0x678387　　 6783880, 0x678388　　 6784000, 0x678400
6825253, 0x682525　　 7948339, 0x794833　　 7948340, 0x794834　　 7950393, 0x795039　　 7950400, 0x795040
2182104640, 0x82104640　　 2182104641, 0x82104641　　 2182104642, 0x82104642　　 2182104643, 0x82104643　　 2182104644, 0x82104644
2182104645, 0x82104645　　 2182104646, 0x82104646　　 2182104647, 0x82104647　　 2182104648, 0x82104648　　 2182104649, 0x82104649
1263629042727, 0x12636290427　　 1307655353654, 0x13076553536　　 2573583194436, 0x25735831944　　 2617616245848, 0x26176162458
3330782168640, 0x30782168640　　 3330782168641, 0x30782168641　　 3330782168642, 0x30782168642　　 3330782168643, 0x30782168643
3330782168644, 0x30782168644　　 3330782168645, 0x30782168645　　 3330782168646, 0x30782168646　　 3330782168647, 0x30782168647
3330782168648, 0x30782168648　　 3330782168649, 0x30782168649　　 3883544086630, 0x38835440866　　 3927569962533, 0x39275699625
3927570397557, 0x39275703975

Core i7-8559U で6時間ほど実行してここまで高々13桁。
やはり想定通り気の利いた高速解放が要りますﾃﾍﾍﾟﾛ。

[684 デフォルトの名無しさん 2025/03/18(火) 16:35:06.57 ID:lVLkTjWA]

>>680
ruby
(0..10**16-1).each{|e| puts "#{e},0x#{e.to_s(16)}" if %r|[a-f]|!~e.to_s(16)}

[685 デフォルトの名無しさん 2025/03/18(火) 21:39:06.90 ID:9hwr8+MV]

>>683
14桁と15桁には該当値がないので、そこに列挙された数に0を追加した72個が15桁以下の答で
結果的には合っているよ。

出題時に作ったC++プログラムはideoneで36桁以下を0.43秒で完了した。これをPowerShellに
移植したプログラムは15桁以下を0.5秒未満、36桁以下を数分で完了した。

その後、改良したC++プログラムではideoneで36桁以下を0.23秒に短縮できた。

[686 9 2025/03/18(火) 21:41:48.53 ID:GYPHuJM6]

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

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

[687 9 2025/03/18(火) 21:42:49.00 ID:GYPHuJM6]

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

[688 9 2025/03/18(火) 21:52:10.05 ID:GYPHuJM6]

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

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

[689 684 2025/03/19(水) 06:18:11.44 ID:khMnA4jS]

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

[690 デフォルトの名無しさん 2025/03/19(水) 08:44:27.79 ID:khMnA4jS]

>>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

[691 9 2025/03/19(水) 16:33:58.47 ID:kDrq13vm]

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

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

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

[692 デフォルトの名無しさん 2025/03/19(水) 21:08:24.40 ID:VtmjGkS9]

>>689
167個で最大値は697786638998562641695629924526065234

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

　2714476666993915057605587441263923823484611431446449961712093492

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

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

[693 デフォルトの名無しさん 2025/03/19(水) 22:39:07.36 ID:P0JLFopv]

お題：単位分数のエジプト風分解(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

[694 693 2025/03/19(水) 22:42:43.02 ID:P0JLFopv]

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

[695 デフォルトの名無しさん 2025/03/19(水) 23:16:25.83 ID:G4dDQ6P7]

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

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

[696 デフォルトの名無しさん 2025/03/20(木) 08:21:38.87 ID:6IEA4H0O]

>>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));
}

[697 デフォルトの名無しさん 2025/03/21(金) 12:56:29.73 ID:CgJbZEAu]

>>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
}

[698 デフォルトの名無しさん 2025/03/21(金) 12:58:11.47 ID:CgJbZEAu]

>>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]);
}

[699 デフォルトの名無しさん 2025/03/21(金) 20:49:29.98 ID:uwhksDTb]

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

[700 デフォルトの名無しさん 2025/03/23(日) 23:00:51.13 ID:pi1bImlR]

>>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を使えば少し速くなる。

[701 デフォルトの名無しさん 2025/03/24(月) 22:16:36.44 ID:/lNBwDBZ]

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

[702 デフォルトの名無しさん 2025/03/25(火) 15:25:56.57 ID:Yc/egiP0]

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

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

[703 デフォルトの名無しさん 2025/03/25(火) 15:54:47.24 ID:GZ5kfx5g]

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

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

[704 デフォルトの名無しさん 2025/03/25(火) 16:11:02.68 ID:Yc/egiP0]

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

[705 デフォルトの名無しさん 2025/03/25(火) 17:30:47.40 ID:Yc/egiP0]

>>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

[706 デフォルトの名無しさん 2025/03/25(火) 20:18:24.92 ID:oTGl9wWX]

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

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

[707 デフォルトの名無しさん 2025/03/25(火) 23:43:24.86 ID:V/NXIH+S]

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

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

[708 デフォルトの名無しさん 2025/03/27(木) 11:39:31.21 ID:vU3T1Sq/]

>>697
crateのnumを使う

[709 デフォルトの名無しさん 2025/03/27(木) 20:29:20.38 ID:DyGv4jyd]

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

[710 デフォルトの名無しさん 2025/03/27(木) 20:35:59.71 ID:cvPlHeM5]

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

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

[711 デフォルトの名無しさん 2025/03/27(木) 21:06:27.50 ID:AGn6MWSp]

>>710
PowerShell

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

unko 3

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

[712 デフォルトの名無しさん 2025/03/28(金) 21:33:35.13 ID:VDfNaTNz]

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

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

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

[713 デフォルトの名無しさん 2025/03/28(金) 21:54:52.53 ID:e6/uDocq]

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

[714 デフォルトの名無しさん 2025/03/28(金) 22:12:15.09 ID:g08AymBh]

お題
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

[715 デフォルトの名無しさん 2025/03/28(金) 22:28:49.68 ID:VDfNaTNz]

>>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

[716 デフォルトの名無しさん 2025/03/28(金) 23:19:47.32 ID:VDfNaTNz]

>>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

[717 デフォルトの名無しさん 2025/03/29(土) 11:51:50.06 ID:UeqVkFR5]

>>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());
}

[718 デフォルトの名無しさん 2025/03/30(日) 01:28:45.68 ID:KrBJAiIU]

お題：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=???

[719 デフォルトの名無しさん 2025/03/30(日) 15:24:52.85 ID:6QsLEZYT]

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

[720 デフォルトの名無しさん 2025/03/30(日) 15:35:52.69 ID:bQF7/1H+]

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

[721 デフォルトの名無しさん 2025/03/30(日) 20:11:24.72 ID:qyCZpZxd]

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

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

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

[722 デフォルトの名無しさん 2025/03/30(日) 20:58:57.54 ID:qyCZpZxd]

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

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

[723 警備員[Lv.4] 2025/03/31(月) 03:24:21.45 ID:V+SeThnI]

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

[724 デフォルトの名無しさん 2025/03/31(月) 05:32:04.89 ID:lZyiUZP+]

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

[725 デフォルトの名無しさん 2025/03/31(月) 22:37:26.59 ID:eEIz6yDp]

>>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"
}

[726 デフォルトの名無しさん 2025/04/01(火) 22:39:42.98 ID:9GVSWQu0]

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

[727 デフォルトの名無しさん 2025/04/02(水) 13:29:35.55 ID:k9Y5euIy]

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

[728 デフォルトの名無しさん 2025/04/02(水) 13:47:27.57 ID:hi8l+lAW]

PHPさえその動作禁止だぞ

[729 デフォルトの名無しさん 2025/04/02(水) 14:31:23.27 ID:vIYRPSqy]

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

[730 デフォルトの名無しさん 2025/04/02(水) 15:10:39.64 ID:hi8l+lAW]

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

[731 デフォルトの名無しさん 2025/04/02(水) 19:51:02.16 ID:7MGV8+qg]

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

[732 デフォルトの名無しさん 2025/04/02(水) 19:56:31.51 ID:/hTkauy0]

5chのプロ 笑

[733 デフォルトの名無しさん 2025/04/02(水) 20:14:17.34 ID:ZWpp3MuE]

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

[734 デフォルトの名無しさん 2025/04/02(水) 21:11:27.43 ID:HCJVcqu8]

>>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を解く人はいませんか?

[735 デフォルトの名無しさん 2025/04/02(水) 23:31:04.18 ID:vIYRPSqy]

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

[736 デフォルトの名無しさん 2025/04/02(水) 23:33:04.35 ID:vIYRPSqy]

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

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

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

[738 デフォルトの名無しさん 2025/04/08(火) 23:28:40.30 ID:OzdBhfzQ]

>>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
}

[739 デフォルトの名無しさん 2025/04/08(火) 23:30:40.48 ID:OzdBhfzQ]

>>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);
　}
}

[740 デフォルトの名無しさん 2025/04/09(水) 14:40:43.48 ID:jYixYFG8]

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

[741 デフォルトの名無しさん 2025/04/09(水) 22:22:33.83 ID:Ip5PiQSs]

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

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

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

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

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

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

[742 デフォルトの名無しさん 2025/04/09(水) 22:57:11.84 ID:R3DmBa+t]

>>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()
}

[743 デフォルトの名無しさん 2025/04/09(水) 23:40:58.68 ID:Ip5PiQSs]

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

[744 デフォルトの名無しさん 2025/04/09(水) 23:43:56.02 ID:R3DmBa+t]

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

[745 デフォルトの名無しさん 2025/04/09(水) 23:50:45.01 ID:Ip5PiQSs]

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

[746 デフォルトの名無しさん 2025/04/09(水) 23:59:16.31 ID:R3DmBa+t]

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

[747 デフォルトの名無しさん 2025/04/10(木) 00:43:03.90 ID:1pFQYAQA]

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

[748 デフォルトの名無しさん 2025/04/10(木) 02:19:18.58 ID:Zvxe3V8x]

ベクタは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回
ワーキングメモリ使用量の差が効いてる

[749 デフォルトの名無しさん 2025/04/10(木) 22:03:03.91 ID:Y2N8/SQw]

>>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}のように計測して
ウィルス・チェックに要した時間も含まれていたりしない?

[750 デフォルトの名無しさん 2025/04/11(金) 07:38:20.09 ID:oaeJuxMT]

>>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
}

[751 デフォルトの名無しさん 2025/04/11(金) 22:07:48.99 ID:CMM29JI3]

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

[752 デフォルトの名無しさん 2025/04/11(金) 22:44:47.89 ID:4wK2/GRg]

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

[753 デフォルトの名無しさん 2025/04/12(土) 09:11:24.51 ID:xiQsTIG2]

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

[754 デフォルトの名無しさん 2025/04/12(土) 21:18:53.69 ID:RVQAocGC]

>>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秒)

[755 デフォルトの名無しさん 2025/04/12(土) 21:26:41.27 ID:csJOBVaF]

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

[756 753 2025/04/13(日) 11:09:12.37 ID:vq5HB/06]

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

[757 デフォルトの名無しさん 2025/04/13(日) 23:46:14.76 ID:bmEZDV0H]

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

[758 デフォルトの名無しさん 2025/04/13(日) 23:53:41.46 ID:fz+Jdq57]

配列にするとどうかね

[759 デフォルトの名無しさん 2025/04/17(木) 00:27:46.72 ID:dz0qzhSq]

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

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

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

[760 デフォルトの名無しさん 2025/04/17(木) 00:29:06.02 ID:dz0qzhSq]

>>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だけ特別扱いすることで倍速にしている。

[761 デフォルトの名無しさん 2025/04/17(木) 00:32:14.51 ID:dz0qzhSq]

>>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キャッシュに乗り有利と思われる点と、
様々な枝刈りがしやすく処理する組み合わせを大きく減らしている点により、
他のアルゴリズムより桁違いに高速になっていると推測される。

[762 デフォルトの名無しさん 2025/05/03(土) 06:56:07.77 ID:Hs+w1scb]

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

[763 デフォルトの名無しさん 2025/05/03(土) 14:00:53.01 ID:2KurydQy]

？

[764 デフォルトの名無しさん 2025/05/03(土) 14:59:51.97 ID:LoSO6jC9]

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

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

[765 デフォルトの名無しさん 2025/05/03(土) 15:10:32.79 ID:OINldK7L]

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

[766 デフォルトの名無しさん 2025/06/21(土) 16:41:25.25 ID:muNvYhtO]

お題
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]

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

[768 デフォルトの名無しさん 2025/06/21(土) 23:05:10.33 ID:awm9eire]

>>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 デフォルトの名無しさん 2025/06/29(日) 20:45:32.73 ID:f7vmTtNq]

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

[770 デフォルトの名無しさん 2025/06/29(日) 21:58:43.69 ID:HlaloW8+]

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

[771 デフォルトの名無しさん 2025/07/25(金) 12:30:11.02 ID:CjDQVF2B]

【問題】
整数のリストが与えられたとき、そのリストを昇順に安定ソートした時の各要素のインデクス（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 デフォルトの名無しさん 2025/07/25(金) 20:46:23.28 ID:dyl0C+2U]

>>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 デフォルトの名無しさん 2025/07/25(金) 21:30:28.86 ID:Z69qH9vG]

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

[774 デフォルトの名無しさん 2025/07/26(土) 12:26:55.07 ID:xCVVpUlx]

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

[775 デフォルトの名無しさん 2025/07/26(土) 15:08:13.56 ID:T78ZrTu7]

>>771
SQL

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

[776 デフォルトの名無しさん 2025/07/26(土) 19:25:22.74 ID:T78ZrTu7]

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

[777 デフォルトの名無しさん 2025/07/27(日) 10:09:36.80 ID:vFJ24xnO]

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

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

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

[778 デフォルトの名無しさん 2025/07/27(日) 17:05:48.29 ID:vFJ24xnO]

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

[779 デフォルトの名無しさん 2025/07/27(日) 17:08:58.25 ID:vFJ24xnO]

>>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]

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

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

[781 デフォルトの名無しさん 2025/07/27(日) 21:43:59.43 ID:w39E9j9Q]

>>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 2025/07/27(日) 22:54:22.66 ID:YfUjoiLt]

>>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]

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

[784 デフォルトの名無しさん 2025/07/29(火) 00:12:31.56 ID:9AXsNEm+]

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

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

[785 デフォルトの名無しさん 2025/07/30(水) 21:50:10.50 ID:Ug40aZKP]

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

[786 デフォルトの名無しさん 2025/07/31(木) 14:56:29.97 ID:cLL+G38O]

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

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

[787 デフォルトの名無しさん 2025/07/31(木) 18:54:11.86 ID:cLL+G38O]

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

[788 785 2025/07/31(木) 21:15:09.63 ID:R3hgrYP8]

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

[789 デフォルトの名無しさん 2025/08/03(日) 22:00:37.87 ID:1jv9m6G7]

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

[790 デフォルトの名無しさん 2025/08/04(月) 22:42:57.64 ID:A9zbJQ8U]

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

[791 デフォルトの名無しさん 2025/08/04(月) 23:09:28.79 ID:A9zbJQ8U]

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

[792 デフォルトの名無しさん 2025/08/05(火) 01:04:23.30 ID:wgx4FmLX]

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

[793 デフォルトの名無しさん 2025/08/06(水) 17:17:53.29 ID:qE4NV2ND]

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

[794 デフォルトの名無しさん 2025/08/07(木) 07:21:55.28 ID:W/yAWgo4]

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

[795 デフォルトの名無しさん 2025/08/10(日) 23:18:32.78 ID:FODtZCg5]

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

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

[796 デフォルトの名無しさん 2025/08/11(月) 20:38:34.09 ID:frWpQyFA]

>>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]

>>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]

-- 実行結果 --
入力: [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 デフォルトの名無しさん 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]）

[800 デフォルトの名無しさん 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");
}

[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

[802 デフォルトの名無しさん 2025/08/16(土) 20:29:06.33 ID:kN4EEg8M]

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

[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

[804 デフォルトの名無しさん 2025/08/16(土) 21:46:08.81 ID:VU+jlz0U]

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

[805 デフォルトの名無しさん 2025/08/17(日) 12:07:33.92 ID:R1ye1QDy]

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

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

[806 805 2025/08/17(日) 15:08:29.44 ID:R1ye1QDy]

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

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

[807 デフォルトの名無しさん 2025/08/17(日) 15:21:28.95 ID:OrBxx4uG]

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

[808 デフォルトの名無しさん 2025/08/17(日) 20:40:30.84 ID:bUKuWE64]

>>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]

>>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 デフォルトの名無しさん 2025/08/19(火) 21:28:38.04 ID:ahVErwF8]

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

[811 806 2025/08/21(木) 22:19:54.42 ID:fAlkh9Aq]

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

[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回）。

[813 デフォルトの名無しさん 2025/08/22(金) 01:14:43.39 ID:6LYRfbyj]

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

[814 デフォルトの名無しさん 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()
}

[815 デフォルトの名無しさん 2025/08/22(金) 06:56:46.07 ID:qlaiAqZd]

>>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 811 2025/08/22(金) 20:26:43.82 ID:m9vhyo0Z]

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

[817 816 2025/08/23(土) 20:27:40.18 ID:uyhDG+iz]

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

[818 デフォルトの名無しさん 2025/08/23(土) 21:01:55.02 ID:gxRFdG35]

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

[819 817 2025/08/23(土) 23:26:24.12 ID:uyhDG+iz]

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

[820 デフォルトの名無しさん 2025/08/24(日) 21:13:57.80 ID:ubCw2JoQ]

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

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

[821 819 2025/08/25(月) 00:28:39.45 ID:IbSJkZLt]

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

[822 デフォルトの名無しさん 2025/08/27(水) 00:40:48.46 ID:AbNZa8yo]

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

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

[823 デフォルトの名無しさん 2025/08/27(水) 21:02:12.94 ID:AbNZa8yo]

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

[824 デフォルトの名無しさん 2025/08/27(水) 21:46:51.59 ID:B7vE54ji]

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

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

[825 821 2025/08/28(木) 21:01:46.43 ID:mnaa+hsk]

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

[826 デフォルトの名無しさん 2025/08/29(金) 13:52:26.21 ID:xrZF+zBK]

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

[827 デフォルトの名無しさん 2025/08/29(金) 20:09:32.40 ID:VEuLqGzD]

>>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]

>>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]

-- 実行結果 --

【問題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 デフォルトの名無しさん 2025/08/30(土) 17:37:04.21 ID:zI+bKiSo]

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

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

[831 830 2025/09/02(火) 21:36:10.92 ID:MM5Gazf9]

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

[832 デフォルトの名無しさん 2025/09/06(土) 23:05:19.87 ID:Z/aFZPi6]

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

[833 832 2025/09/07(日) 12:29:41.48 ID:O1zDlKW9]

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

[834 833 2025/09/07(日) 14:22:59.56 ID:O1zDlKW9]

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

[835 デフォルトの名無しさん 2025/09/08(月) 23:02:49.14 ID:4SI/cFAg]

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

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

[836 835 2025/09/08(月) 23:33:25.73 ID:4SI/cFAg]

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

[837 デフォルトの名無しさん 2025/09/09(火) 21:56:29.91 ID:PCxKX9bv]

>>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]

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

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

[839 836 2025/09/10(水) 22:49:33.81 ID:NV1RL9MH]

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

[840 839 2025/09/10(水) 23:35:38.95 ID:6JfM8ZLf]

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

[841 840 2025/09/11(木) 23:05:23.09 ID:WPUXbxYH]

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

[842 デフォルトの名無しさん 2025/09/12(金) 15:41:31.15 ID:IRXhEt4s]

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

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

[843 デフォルトの名無しさん 2025/09/12(金) 16:19:33.85 ID:uazXAFOm]

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

[844 デフォルトの名無しさん 2025/09/12(金) 20:36:05.46 ID:I2wrB793]

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

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

[845 デフォルトの名無しさん 2025/09/13(土) 12:21:51.23 ID:nVmVuqdT]

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

【問題】
各桁の数が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 デフォルトの名無しさん 2025/09/13(土) 21:09:19.41 ID:rhMflYHg]

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

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

[847 デフォルトの名無しさん 2025/09/14(日) 02:07:05.25 ID:K9dbpWus]

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

[848 デフォルトの名無しさん 2025/09/14(日) 02:17:37.66 ID:ymjVQadn]

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

[849 デフォルトの名無しさん 2025/09/14(日) 21:00:58.83 ID:Yva1i9w5]

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

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

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

[850 デフォルトの名無しさん 2025/09/14(日) 22:50:48.82 ID:Yva1i9w5]

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

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

[851 848 2025/09/15(月) 00:34:43.20 ID:aTaxsjKO]

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

[852 851 2025/09/15(月) 00:58:49.72 ID:aTaxsjKO]

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

[853 デフォルトの名無しさん 2025/09/15(月) 22:27:44.05 ID:g8zilsSB]

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

[854 852 2025/09/16(火) 01:02:30.84 ID:3CKXdG+H]

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

[855 854 2025/09/17(水) 22:30:29.22 ID:U8XLHdaR]

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

[856 デフォルトの名無しさん 2025/09/17(水) 22:43:48.03 ID:RlLGu0ST]

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

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

[857 デフォルトの名無しさん 2025/09/17(水) 23:39:47.32 ID:RlLGu0ST]

>>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 855 2025/09/18(木) 21:13:33.56 ID:mk4sIpUK]

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

[859 858 2025/09/19(金) 21:59:08.62 ID:e72KvXSi]

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

[860 859 2025/09/20(土) 21:39:31.29 ID:zrmIrXrK]

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

[861 860 2025/09/22(月) 21:37:36.11 ID:9W7EeSnZ]

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

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

[862 861 2025/09/23(火) 01:13:48.01 ID:XS9iE/WB]

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

[863 862 2025/09/26(金) 21:58:13.14 ID:rAOVnJgT]

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

[864 デフォルトの名無しさん 2025/10/19(日) 18:23:02.12 ID:UPYRyJKx]

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

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

出力
使用枚数：2

[865 デフォルトの名無しさん 2025/10/19(日) 21:36:07.90 ID:1trCfbwI]

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

[866 デフォルトの名無しさん 2025/10/22(水) 21:34:32.83 ID:vm0Iby1T]

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

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

[867 デフォルトの名無しさん 2025/10/26(日) 09:31:44.23 ID:Y3+SSpql]

お題というか、協力してほしい感じなんですが、素因数分解関数を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

[868 デフォルトの名無しさん 2025/10/26(日) 09:50:23.90 ID:Y3+SSpql]

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

[869 デフォルトの名無しさん 2025/10/26(日) 10:13:01.91 ID:XLS0tlS8]

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

[870 デフォルトの名無しさん 2025/10/26(日) 10:19:15.38 ID:0X7G2IAI]

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

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

[871 869 2025/10/26(日) 10:21:11.68 ID:XLS0tlS8]

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

[872 デフォルトの名無しさん 2025/10/26(日) 17:08:32.87 ID:Y3+SSpql]

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

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

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

[873 デフォルトの名無しさん 2025/10/26(日) 17:55:12.41 ID:N6SeZsiy]

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

[874 デフォルトの名無しさん 2025/10/26(日) 23:06:07.50 ID:Y3+SSpql]

>>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 なので、素数比較回数が多いのかと。

[875 デフォルトの名無しさん 2025/10/26(日) 23:07:37.04 ID:Y3+SSpql]

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

[876 デフォルトの名無しさん 2025/11/07(金) 05:48:17.42 ID:ckPLmv2U]

>>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;
}