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

**デフォルトの名無しさん** · 2022/11/13(日) 19:00:36.84

プログラミングのお題スレです。

【出題と回答例】
1 名前：デフォルトの名無しさん
　　お題：お題本文

2 名前：デフォルトの名無しさん
　　>>1 使用言語
　　回答本文
　　結果がある場合はそれも

【ソースコードが長くなったら】 (オンラインでコードを実行できる)
https://ideone.com/
http://codepad.org/
http://compileonline.com/
http://rextester.com/runcode
https://runnable.com/
https://code.hackerearth.com/
http://melpon.org/wandbox
https://paiza.io/

宿題は宿題スレがあるのでそちらへ。

※前スレ
プログラミングのお題スレ Part20
https://mevius.5ch.net/test/read.cgi/tech/1624028577/

**638** · 2023/06/11(日) 22:49:44.46

>>763
Perlの（多分Pythoも,Rubyはｼﾗﾈ）配列はリストなのでインデックスで回すとリンク辿りをloopで繰り返し
こういったコードでは遅さに拍車をかけていると思う。あとhashを多用するのもペナルティーがあると思う。
配列の代わりにBit Vectorが使える場面ではそれにより改善できる可能性がある
たとえば序盤のエラトステネスの篩で素数求めるloopについては>>761のコードだと5.2秒くらいなんだけれど
長い文字列をVectorとし、個々の文字をflag要素とみなし、

use feature qw{say};
$m = 1234567;
$o = '1' x $m;
for $i (2..int(sqrt $m)) {
　if (substr $o, $i, 1) {
　　for ($i..(int($m / $i)+1)) {
　　　$j = $i * $_; last if $m <= $j; substr $o, $j, 1, '0';
　　}
　}
}
for (2.. $m) {
　$n++ if substr($o, $_, 1);
}
print "$n\n";

と書くと0.3秒くらいに短縮される。ただし5分のうち5秒なので焼け石に…
しかしこの方法は151060650通りを求める後半のループにはうまく効かない。
つかそれ以前に解が合ってない。多分俺が勘違いしてバグ仕込んだと思う。

しかしRのコード短いな…も一回勉強してみようかな

**デフォルトの名無しさん** · 2023/06/12(月) 00:06:55.69

やめとけ
短ければいいという時代はとっくに終わってる
いつまでワンライナーとかアホな事やってんねんと思う

**デフォルトの名無しさん** · 2023/06/12(月) 23:18:04.33

>>763のプログラムの8～11行目は以下のように書いた方がすっきりして良い。

for (i in 1:q[n %/% 3L]) {
　　m <- n - p[i]
　　k <- k + sum(isprime[m - p[i:q[m %/% 2L]]])
}

>>761のプログラムはa ≤ b ≤ cではなくa < b < cの場合の組み合わせ数を計算している。
14行目の$i+1を$iに、13行目と16行目の<=を<に変更すれば正解が得られる。

**デフォルトの名無しさん** · 2023/06/12(月) 23:18:28.27

PowerShell 7は前のバージョンよりは速くなっていて、以下のプログラムは>>761の
3分の1ほどの時間で実行できた。

$n = 1234567
$isprime = @($false) * 2 + @($true) * ($n - 1)
foreach ($i in 2..[Math]::sqrt($n)) {
　　if ($isprime[$i]) {for ($j = $i + $i; $j -le $n; $j += $i) {$isprime[$j] = $false}}
}

$j = 0
$p = $q = @(0) * ($n + 1)
foreach ($i in 2..$n) {
　　if ($isprime[$i]) {$p[$j++] = $i}
　　$q[$i] = $j - 1
}

$k = 0
foreach ($i in 0..$q[$n / 3]) {
　　$m = $n - $p[$i]
　　foreach ($j in $i..$q[$m / 2]) {
　　　　if ($isprime[$m - $p[$j]]) {$k++}
　　}
}
"${k}通り"

**デフォルトの名無しさん** · 2023/06/12(月) 23:42:55.82

>>738 rust
https://ideone.com/THk6s8
fn sieve_of_eratosthenes(n: u32) -> (Vec<bool>, Vec<u32>) {
if n < 2 {return (Vec::new(), Vec::new())};
let mut isprime = vec![true; 1 + n as usize];
isprime[0..2].fill(false);
(2..=(n as f64).sqrt() as usize).for_each(|i| if isprime[i] {
(i*i..=n as usize).step_by(i).for_each(|j| isprime[j] = false);
});
let primes = (2..=n).filter(|&i| isprime[i as usize]).collect();
(isprime, primes)
}
fn main() {
let n = 1234567;
let (isprime, primes) = sieve_of_eratosthenes(n);
let count = primes.iter().enumerate().take_while(|(i, &a)| a <= n / 3).map(|(i, &a)|
primes[i..].iter().take_while(|&&b| b <= (n - a) / 2).map(|&b|
isprime[(n - a - b) as usize] as u32
).sum::<u32>()
).sum::<u32>();
println!("count = {}", count);
}

**638** · 2023/06/12(月) 23:47:34.40

>>766
おお、指摘ありがとう。
俺てっきりa < b < cを検索する問題だと思い込んでた。何故合わないか頭ひねっていた。
思い込みにより作りこんだバグというものはなかなか自力で問題だと気づけないんだよな…。

>>767
俺も時間あったら高速化してみるよ。そのうち…、時間があったら…
第二loopの高速化は他にも試作したけどちょっとムｽﾞカしい

**638** · 2023/06/13(火) 00:40:44.65

>>738 Perl5 高速化版、>>766のおかげで不具合解決したし、>>761 の1/3に時間短縮できたので俺としてはこのお題これで一区切りつけたい。

$m = 1234567;
$o = '1' x $m; #substr $o, 0, 2, '00';
for $i (2..int(sqrt $m)) {
　if (substr $o, $i, 1) {
　　for ($i..(int($m / $i)+1)) {
　　　$j = $i * $_; last if $m <= $j; substr $o, $j, 1, '0';
　　}
　}
}
for (2.. $m) { push @p, $_ if substr($o, $_, 1) }
for $i (0..$#p) {
　$p1 = $p[0];
　last if $m < 3 * $p1;
　for $p2 (@p) {
　　$s = $p1 + $p2;
　　$r = $m - $s;
　　last if $r < $p2;
　　$n++ if substr $o, $r, 1;
　}
　shift @p;
}
print "n = $n\n";

実行結果：（CPU Core-i7 8995u）
$ time perl 21_738_prime+1234567_charVec.pl
n = 151060650

real 1m57.390s
user 1m56.375s
sys 0m0.093s

**デフォルトの名無しさん** · 2023/06/13(火) 22:09:38.41

>>738 octave
・n = 1234567 でideone完走できず
https://ideone.com/QzfFfY

>>738 ruby
・n = 1234567 でideone完走できず
https://ideone.com/OPplEt

>>738 java
https://ideone.com/pCHK8L

ちなみに現時点ではそれぞれ
C (gcc 8.3)
Rust (rust 1.56)
Octave (octave 4.4.1)
Ruby (ruby 2.5.5)
Java (HotSpot 12)

**デフォルトの名無しさん** · 2023/06/13(火) 23:10:18.55

>>771
nが偶数の場合はaは2しかあり得ないから、ループでaを変化させるのは時間の無駄でしかない。

**デフォルトの名無しさん** · 2023/06/14(水) 01:24:51.27

数値の設定がデカすぎるんだよ
こんなもん個人のパソコンでやって結果だけコピペしても面白くもなんともない
ネットのプログラムサービスとかで完走できるサイズに設定しとけや

**デフォルトの名無しさん** · 2023/06/14(水) 03:58:19.40

>>738
https://paiza.io/projects/fGIqMa8Tq4Q0FBxgaGrN7Q

**デフォルトの名無しさん** · 2023/06/14(水) 10:10:07.75

お題：文字列を入力すると文字列が右に移動を始め画面の端に当たったら当たった側の文字が一つ削れて今度は左に移動しそれを繰り返し最終的に文字がなくなるまでアニメーションするプログラムを作成せよ。

**デフォルトの名無しさん** · 2023/06/14(水) 12:04:02.31

ブラウザでコード描いて実行する環境はいくつかあるけど
ANSIエスケープシーケンスとか解釈してくれるコンソール出力付きの環境ってある？

**デフォルトの名無しさん** · 2023/06/14(水) 12:48:17.85

この辺でチョチョっと扱えると便利なんだが
https://wandbox.org/
https://cpp.sh/

**デフォルトの名無しさん** · 2023/06/14(水) 21:28:54.64

>>738 octave
・for無しでa,b,cを算出（ただしfor版>>771より遅い）
・n = 1234567 でメモリ不足でオチる（bがクソデカサイズ）
・データの型をint32にしてみたりもしたが焼け石に水だし少し遅くもなるのでdoubleに戻した
https://ideone.com/aosEo2
function [isprime, primes] = sieve_of_eratosthenes(n)
if n < 2; isprime = [], primes = [], return; end
isprime = [false true(1, n-1)];
for i = 2:sqrt(n)
if isprime(i); isprime(i*i:i:n) = false; end
end
primes = find(isprime);
end
n = 123456
[isprime, primes] = sieve_of_eratosthenes(n);
a = primes(primes <= n / 3)';
b = primes.*(a <= primes & primes <= (n - a) / 2);
c = (n - a - b)(b ~= 0);
count = sum(isprime(c))

**デフォルトの名無しさん** · 2023/06/14(水) 22:07:29.08

>>775
PowerShellで全角文字、等幅フォント限定

$s = "プログラミングのお題スレです。"
$w = $Host.UI.RawUI.WindowSize.Width - 1
$c = $Host.UI.RawUI.CursorSize
$Host.UI.RawUI.CursorSize = 0;`
foreach ($n in $s.length..0) {
　　$d = $w - 2 * $n
　　$m = $s.length - $n
　　foreach ($x in ((1..$d), ($d..1))[$m % 2]) {
　　　　$l = "`r" + " " * $x + $s.SubString([Math]::Floor($m / 2), $n) + " " * ($d - $x)
　　　　Write-Host $l -NoNewline
　　　　if (!$n) {Write-Host; break}
　　　　Sleep -m 20
　　}
}
$Host.UI.RawUI.CursorSize = $c

**デフォルトの名無しさん** · 2023/06/15(木) 00:31:42.16

>>774
フーリエ変換でなぜ計算できるのか知らないが、とりあえずRに移植してみたら
5秒で完了できなかった。www.ideone.com/nhGFqi

tio.runで実行したら5.975秒かかった。fft関数がRのよりnumpyのの方が速いのか?
RのはUses C translation of Fortran code in Singleton (1979)だそうだが。

**デフォルトの名無しさん** · 2023/06/15(木) 01:02:15.13

>>780
数え上げの問題を形式的冪級数の議論に対応づけることができる
形式的冪級数同士の積は長さ n が2の冪なら高速フーリエ変換による畳み込みで O(n log n) で計算できる
Rのfftはおそらく高速になる2の冪の長さのfftをしていないんだと思う

**638** · 2023/06/15(木) 01:38:57.15

へー、そりゃ面白い

**デフォルトの名無しさん** · 2023/06/15(木) 20:35:51.05

この程度の桁数ならfft使う意味などない
ハードのfpuで計算に勝てるはずがない
fft使うメリットなんぞ数万桁とかいかないとでないやろ

**デフォルトの名無しさん** · 2023/06/15(木) 21:44:36.42

>>781
Rの標準のfft関数は遅いようなので、fftwパッケージのFFT, IFFT関数に替えたら
実行時間は半分くらいに短縮されたが、ideoneではfftwパッケージがインスール
されていなくて実行できなくて残念。

library(fftw)

conv <- function(f, g) round(Re(IFFT(FFT(f) * FFT(g))))

n <- 1234567L
isprime <- c(FALSE, rep(TRUE, n - 1))
for (i in 2:sqrt(n)) if (isprime[i]) isprime[seq(i + i, n, i)] <- FALSE

N <- nextn(2 * n + 1, 2)
x <- c(0, as.double(isprime), rep(0, N - n - 1))
count <- conv(conv(x, x), x)[n + 1]

i <- 2:(n %/% 2 - 1)
k <- sum(isprime[i] & isprime[n - 2 * i])

cat((count - 3 * k) %/% 6 + k, "通り\n", sep = "")

**デフォルトの名無しさん** · 2023/06/15(木) 22:01:30.16

fftなんぞ使って早くなんかならんというに
原理わかってんの？
例えばHaskellの標準のinteger型は何万桁でも計算できる、その際fftで掛け算するので数万桁まで行ってもそこそこ早い
しかし逆に32bitで収まるような計算だと遅くなる
だから“この計算はfftなんか使わなくていいよ、int32の範囲で収まるからそれで計算してね”と専用の型がいっぱいある
Rがそれで早くなるなら素の標準計算がしょぼいとかインタプリタ特有の話
そもそも計算速度気にする場合にRを選択してる時点で筋違い

**デフォルトの名無しさん** · 2023/06/15(木) 22:26:38.53

>>785
遅い言語でも工夫次第で制限時間を突破できないかというのがスレの流れなので、
そういう当たり前な突っ込みは野暮というもの。速い言語での正攻法の回答例は
>>746にちゃんと書いた。

**デフォルトの名無しさん** · 2023/06/15(木) 23:01:51.41

だからそこでfft使うなんてのがわかってないって言ってるの
わからんかね？

**デフォルトの名無しさん** · 2023/06/15(木) 23:56:30.25

>>787
忖度して読み取ると多倍長整数の乗算の話をしているのだと思うけれど >>738 の問題を解く上ではそもそもあまり関係がない
素数になる次数の係数が 1 でそれ以外が 0 の形式的冪級数を考えてそれを3回乗算して N = 1234567 の次数の係数を求める問題に帰着させているだけ

**デフォルトの名無しさん** · 2023/06/16(金) 00:03:42.43

まぁ上の方のレス見ればわかる通りそもそも本人fftの理論何にも勉強した事なさそうでちゃんと勉強した人間(というかちゃんと勉強してなくてもわかる事だけど)>>378の話になんも関係ないってわからんのかな？
しかもそのレベルで噛みついてくるからタチ悪い

**デフォルトの名無しさん** · 2023/06/16(金) 00:04:47.90

なんか日本語変になったな
なんで勉強もした事ない話しで他人に噛みついてこれるんだろう？

**デフォルトの名無しさん** · 2023/06/16(金) 01:54:12.19

炎上学習法というのがある
相手に噛みついて解説させて勉強する手法

**デフォルトの名無しさん** · 2023/06/16(金) 09:00:10.71

>>738
>>746 にもあるが
>>785 が正論

**デフォルトの名無しさん** · 2023/06/16(金) 09:01:22.25

問題
Σ[n: 1→4000](1/√n)
の整数部を答えよ

**デフォルトの名無しさん** · 2023/06/16(金) 10:04:38.20

やだ

**デフォルトの名無しさん** · 2023/06/16(金) 10:33:26.86

フィボナッチ数列のn番目の整数zだけ表示するプログラムを書きなさい。
ただし、zが3、5、15のいずれかで割り切れる場合はzの後に改行を挿入して、
"割り切れる"と表示しなさい。

1, 1, 2, 3, ... n

【条件】
1 <= n <= 100000000000

**デフォルトの名無しさん** · 2023/06/16(金) 10:52:39.37

まぁ最後の条件は最後の1桁まで計算させるつもりなんかもしれないけど
5 | Fₙ ⇔ 5 | n
だから意味はないわな

**デフォルトの名無しさん** · 2023/06/16(金) 20:29:55.57

>>738
https://paiza.io/projects/0QCNbnKzWMHspiarmHa0Tw
細かいテクニックで高速化して出題者の方の解答例と同じくらいの実行時間にできた
総当たりの解法の計算量が N = 1234567 に対して O(pi(N)^2) なのに対してこの解法は O(N log N) なのできちんと書けば十分に速く動いてくれる

**デフォルトの名無しさん** · 2023/06/16(金) 21:29:35.35

>>797
解説プリーズ
コード読んでもさっぱりわからん
どうやってO(N)にできたんですか？

**デフォルトの名無しさん** · 2023/06/16(金) 21:34:18.18

アレ？
やっぱりこれ三乗してるんじゃないの？
O(N)ちゃうやん
O(N)の意味わかってる？

**デフォルトの名無しさん** · 2023/06/16(金) 21:36:03.94

>>797
確かに無駄は大分省けたな。Rでも同じようにしたらばっちり完走できた。
www.ideone.com/7lob9A

**デフォルトの名無しさん** · 2023/06/16(金) 21:36:46.05

イヤ、整数計数の多項式環の三乗もfftで早くできるのかな？

**デフォルトの名無しさん** · 2023/06/16(金) 21:41:30.83

もしかしたらできるか
fftのアルゴリズムってこっちのコンボリューション積をあっちの各点積に持っていく方法だから多項式環でもできるんかな？

**デフォルトの名無しさん** · 2023/06/16(金) 22:11:45.10

>>798
大体わかっているみたいだけど少し丁寧に書いてみる
素数次数の係数が 1 でそれ以外の係数が 0 の形式的冪級数 f を考える
f^3 の k 次の項の係数は素数 3 個を選んで足した和が k になる場合の数になるので今回は k = 1234567 の係数を求めたい
長さ N の多項式の積は高速フーリエ変換による畳み込みで O(N log N) で計算できるので形式的冪級数を前から必要なだけとって多項式にして適用する
また取りうる値が大きくて誤差が問題になるときは数論変換と中国剰余定理で復元する方法もあるけど今回は不要
3乗している対象は配列の各項なのでそこはボトルネックにはならない

**デフォルトの名無しさん** · 2023/06/16(金) 22:23:18.66

うん、やっとわかった
fftの計算への応用つて真っ先に整数そのものの掛け算が思いついてしまうけど、別に整数そのものの掛け算でなくてもいいわけだ
完全に目からウロコ

**デフォルトの名無しさん** · 2023/06/16(金) 23:47:11.07

>>795

とりあえずHaskell
10000項くらいまではちゃんと動くよう
Haskellの整数型は一応規格上の制限はないみたいだけど多分GHCには流石に制限あるだらうから何項まで動くか不明

**デフォルトの名無しさん** · 2023/06/17(土) 06:25:35.36

>>775
Rust + termion
https://gist.github.com/rust-play/aaa7a8eb1831e14b947f486986211461

**デフォルトの名無しさん** · 2023/06/17(土) 15:32:59.09

お題

15時間20分を15.2と表記するとして
15.2+2.4=18.0時間って計算させるにはどうやればいいの？

**デフォルトの名無しさん** · 2023/06/17(土) 22:31:22.41

整数部分と小数部分に分ける
小数部分は2桁とみなす
60進数の小数点数として扱う

**デフォルトの名無しさん** · 2023/06/17(土) 23:26:07.50

>>807
Rだと自作のクラスでなくても演算子を再定義できてしまうから、そういう奇妙な表記の
数式での計算も可能。
www.ideone.com/xzSCyt

**デフォルトの名無しさん** · 2023/06/18(日) 22:57:19.74

>>807 octave
https://ideone.com/S0EqvY
function c = f(a, b)
m = (fix(a) + fix(b)) * 60 + round((a - fix(a) + b - fix(b)) * 100);
c = fix(m / 60) + rem(m, 60) / 100;
end

**デフォルトの名無しさん** · 2023/06/20(火) 15:17:12.61

お題　Fourier 変換

長さが2べきの複素数の列が与えられます
(複素数はDouble型２つのタプルで表現するとする)
そのFourier変換である同じ長さの列を計算する関数を実現して下さい
またそれを利用して同じ長さの畳み込み積を計算する関数を実現して下さい

(但し書き)
長さNの数列(aₙ)のFourier変換F(aₙ)とは第k項が
Σ[n=0,N-1] (cos(2πkn/N) + isin(2πkn/N))aₙ
である列を与える変換とする
その逆変換F⁻¹(aₙ)は第k項が
1/NΣ[n=0,N-1] (cos(-2πkn/N) + isin(-2πkn/N))aₙ
で与えられる変換である
数列(aₙ)と(bₙ)の畳み込み積とは
F⁻¹( F(aₙ) × F(bₙ) )
で与えられる積である、ただしこの×は各項毎の積で与えられる列である

**デフォルトの名無しさん** · 2023/06/20(火) 15:17:18.47

(例)
・F (a,b,c,d) = (a+b+c+d, a+bi-c-di,a-b+c-d,a-bi-c+di)
・F(1,2,3,0,0,0,0,0) =
6.0 :+ 0.0
2.4142135623730954 :+ 4.414213562373095
(-1.9999999999999996) :+ 2.0
(-0.4142135623730949) :+ (-1.5857864376269046)
2.0 :+ 0.0
(-0.4142135623730949) :+ 1.585786437626905
(-2.0000000000000004) :+ (-2.0)
2.4142135623730945 :+ (-4.414213562373096)
・1,2,3,0,0,0,0,0と4,5,6,0,0,0,0,0の畳み込み積
=
3.999999999999999 :+ 2.6645352591003757e-15
12.999999999999998 :+ (-1.6730659520119792e-15)
28.0 :+ (-5.773159728050814e-15)
27.0 :+ (-5.432361405589022e-15)
18.0 :+ (-8.881784197001252e-16)
1.7763568394002505e-15 :+ 3.656004566188772e-15
1.7763568394002505e-15 :+ 3.9968028886505635e-15
0.0 :+ 3.4494227914122297e-15

**デフォルトの名無しさん** · 2023/06/20(火) 15:59:11.28

お題（難易度★）

a=1のとき、b=1000000
a=2のとき、b=999999
a=3のとき、b=999998

上記の法則を元に、aがnのときのbの値を求めなさい

**デフォルトの名無しさん** · 2023/06/20(火) 23:32:28.84

>>813 py

import numpy as np
from scipy.optimize import least_squares

data = np.array([
1000000,
999999,
999998,
999997,
])

def poly_2d(x, a, b, c, d, e, f):
return a * x**5 + b * x**4 + c * x ** 3 + d * x ** 2 + e * x + f

def residuals(params, data):
a, b, c, d, e, f = params
res = []
for x in range(1, len(data) + 1):
res.append(data[x - 1] - poly_2d(x, a, b, c, d, e, f))
return res

initial_guess = [1, 1, 1, 1, 1, 1]
result = least_squares(residuals, initial_guess, args=(data,))
a, b, c, d, e, f = result.x

print(f"fn = lambda x: {a:.6f}*x**5 + {b:.6f}*x**4 + {c:.6f}*x**3 + {d:.6f}*x**2 + {e:.6f}*x + {f:.6f}")

fn = lambda x: round(a*x**5 + b*x**4 + c*x**3 + d*x**2 + e*x + f)

print(fn(1))
print(fn(2))
print(fn(3))
print(fn(4))

fn = lambda x: -9433.011975*x**5 + 81785.062791*x**4 + -204704.849008*x**3 + 32573.601042*x**2 + 400859.570602*x + 698919.625800

1000000
999999
999998
999997

**デフォルトの名無しさん** · 2023/06/20(火) 23:56:19.99

>>813 octave
https://ideone.com/7v5QU9
f = @(n) polyval(polyfit([1 2 3], [1000000 999999 999998], 1), n);

**デフォルトの名無しさん** · 2023/06/21(水) 00:19:23.72

なんて短いんだすげえ

**638** · 2023/06/21(水) 07:20:53.86

>>805
Haskellのｵｼﾞﾁｬﾝは一体どこに回答を書いたんだろう…

**デフォルトの名無しさん** · 2023/06/21(水) 09:26:22.30

Haskell爺さんはリンクを書き忘れましたとさ
メデタシメデタシorz

https://ideone.com/TTY3nD

**蟻人間** ◆T6xkBnTXz7B0 · 2023/06/21(水) 20:25:12.09

お題: 入力を(x, minv, maxv)の3整数とする。xを閉区間[minv, maxv]に制限した値を返すプログラム(ただしminv≦maxv)。

例)
(1, 3, 5)→3.
(100, 5, 120)→100.
(208, 5, 120)→120.

**デフォルトの名無しさん** · 2023/06/21(水) 21:30:09.94

>>819 octave
https://ideone.com/gn1GYh
f = @(x, minv, maxv) min(max(minv, x), maxv);

**蟻人間** ◆T6xkBnTXz7B0 · 2023/06/21(水) 21:34:57.73

お題: 2次元ソート。

与えられた比較関数Compare2Dを用いて2次元のデータを並べ替える。

typedef int DATA;
int Compare2D(DATA left, DATA above, DATA target);
左端でも上端でもない、ターゲットのデータについて
引数leftは一つ左のデータ、
引数aboveは一つ上のデータ、
引数targetはターゲットのデータとする。
比較関数の戻り値は、比較結果が小さいとき-1に、同じとき0に、大きいとき1になる。

比較関数Compare2Dとソートアルゴリズムを適当に定め、アスキーコードの一部(0x20～0x5f)、つまり、アスキー表の一部を乱数で撹乱した二次元データをソートしたときに、
アスキー表の一部を表す長方形状になるようにし、ソート前の撹乱後の二次元データと、ソート後の二次元データを自然にわかりやすく出力するプログラムを作れ。

**蟻人間** ◆T6xkBnTXz7B0 · 2023/06/21(水) 21:38:27.11

>>821
修正。比較関数は次の2つとする。

int CompareX(DATA left, DATA target);
int CompareY(DATA above, DATA target);

**蟻人間** ◆T6xkBnTXz7B0 · 2023/06/21(水) 22:25:34.39

>>822
お題を撤回します。熟慮が足りない。。。

**デフォルトの名無しさん** · 2023/06/21(水) 23:17:43.90

>>819
PowerShell 6以上なら[Math]::Clampを、C++ 2017以上なら#include <algorithm>で
clampを呼び出すだけだな。

**デフォルトの名無しさん** · 2023/06/22(木) 04:06:08.77

お題：数学的な処理を使って東京タワーっぽいアスキーアートを出力せよ
アスキーアートのクオリティは問わない

**デフォルトの名無しさん** · 2023/06/22(木) 10:33:46.03

おじいちゃんスカイツリーでも良いですか？

**デフォルトの名無しさん** · 2023/06/22(木) 17:08:30.10

いいよ

**デフォルトの名無しさん** · 2023/06/22(木) 21:46:09.75

>>811-812
Rでfft関数を使わずに式通りの低速変換。畳み込み積は普通に求めた値を左に併記した。
www.ideone.com/pUV71G

**638** · 2023/06/23(金) 00:36:01.83

>>811-812 Perl5、若いころ物理数学で勉強した記憶を呼び戻しながら、LibraryやComplex型を使用せず、また複素数をﾀﾌﾟﾙで表して愚直に実装してみた。
長さが2のべき乗とのことだがﾊﾞﾀﾌﾗｲ演算による計算量の低減は実装していない。なお10＾-15乗などの微小な数値の仮数部がお手本解と異なるところがあるが計算誤差によるもので実質０だと思う。
(やっぱ記号を使った数式よりも物理的な意味やイメージと対応付けて捉える方が俺にとってはしっくりくるわ）

use utf8;
use constant PI => 3.141592653589793;
use feature qw{signatures say};

sub 基底($波数, $N) { [map{[cos(2*PI*$波数*$_/$N), sin((2*PI*$波数*$_/$N))]} 0..$N-1] }
sub 複素数の積($a, $b) { [$$a[0]*$$b[0] - $$a[1]*$$b[1], $$a[0]*$$b[1] + $$a[1]*$$b[0]] }

use List::Util 'reduce';
sub 積和相関($x, $e) { reduce{[$$a[0]+$$b[0], $$a[1]+$$b[1]]} map{複素数の積 $$x[$_], $$e[$_]} 0..$#$e }

sub FT(@s) { map{ 積和相関(\@s, 基底($_, scalar @s)) } 0..$#s }
sub iFT(@s) { my $n = @s; map{[$$_[0]/$n, $$_[1]/$n]} map{ 積和相関(\@s, 基底(-$_, $n)) } 0..$n-1 }

sub CV($a, $b) { my @c = FT(@$a); my @d = FT(@$b); iFT( map{複素数の積 $c[$_], $d[$_]} 0..$#c ) }

sub prti { join(', ', map{"$$_[0]". (0 <= $$_[1] and '+') ."$$_[1]i"} @_) }

my @a = ([1, 0], [2, 0], [3, 0], [0, 0], [0, 0], [0, 0], [0, 0], [0, 0]);
my @b = ([4, 0], [5, 0], [6, 0], [0, 0], [0, 0], [0, 0], [0, 0], [0, 0]);

say 'FT: ', prti FT(@a);
say 'CV: ', prti CV(\@a, \@b);

実行結果
$ perl 21_811_FT_CV.pl
FT: 6+0i, 2.41421356237309+4.41421356237309i, -2+2i, -0.414213562373095-1.5857864376269i, 2-4.89858719658941e-16i, -0.414213562373094+1.58578643762691i, -2-2i, 2.41421356237309-4.4142135623731i
CV: 4+2.66453525910038e-15i, 13+1.77635683940025e-15i, 28+8.88178419700125e-16i, 27-5.77315972805081e-15i, 18-1.77635683940025e-15i, -6.21724893790088e-15-7.99360577730113e-15i, 8.88178419700125e-15+7.105427357601e-15i, 1.24344978758018e-14-2.8421709430404e-14i

**デフォルトの名無しさん** · 2023/06/23(金) 12:40:23.36

お題（難易度★★）

0, 1, 2, 3, 6, 11, 20, 37 ...

上記の数列の法則を元に、n番目の整数aを求めるプログラムを作成せよ

【条件】
3 <= n <= 1000

【例】
n=6なら、a=11となる
n=9なら、a=68となる

**デフォルトの名無しさん** · 2023/06/23(金) 13:24:19.71

どういう法則なの？

**デフォルトの名無しさん** · 2023/06/23(金) 13:33:04.37

前３つ足すかな

**デフォルトの名無しさん** · 2023/06/23(金) 13:39:27.23

なるほど

**デフォルトの名無しさん** · 2023/06/23(金) 14:36:35.46

constexpr int foo(int n){
constexpr int t[] = {1, 0, 1, 2, 3, 6, 11, 20, 37, 68};
return t[n % std::size(t)];
}

これでOK
ルールを推測させる系は出題側の意図した答えを出させるためにどう制限かけるかが問われる

**デフォルトの名無しさん** · 2023/06/23(金) 15:48:43.65

アスペル回答やめなよみっともない

**デフォルトの名無しさん** · 2023/06/23(金) 15:49:02.54

> これでOK
何いってんだお前

**デフォルトの名無しさん** · 2023/06/23(金) 15:49:31.53

あーあ、お前が潜水艦に乗って爆縮されたら良かったのにな～

**デフォルトの名無しさん** · 2023/06/23(金) 16:23:56.10

潜水艦の操縦がゲームコントローラとかワクワク感たまらねぇ
マジレスするとRustで造ってれば安全だったはず

**デフォルトの名無しさん** · 2023/06/23(金) 20:31:23.73

>>830 ruby
https://ideone.com/lOvKLI
g = ->(m) {
a = (3...m).inject([0, 1, 2]) {|a, _| a << a[-1] + a[-2] + a[-3]}
->(n) {n < 1 || m < n ? nil : a[n - 1]}
}
f = g.(1000)
p [*0..9, 1000, 1001].map {|i| [i, f.(i)]}
↓
[[0, nil], [1, 0], [2, 1], [3, 2], [4, 3], [5, 6], [6, 11], [7, 20], [8, 37], [9, 68], [1000, 1258890285439289522674621215321790399357402658069918084564035590888323288383996894058630489346490443306057821146808944309219589954636534445475146599057985479816395429617207869586544429749851128733512216004490332659216184693670760709292866744282443549293609850952277], [1001, nil]]

**デフォルトの名無しさん** · 2023/06/23(金) 20:38:59.27

>>830
Rでnが大きい場合にも高速に計算（例のnでは意味がないが）
www.ideone.com/FrR91K

C#でHaskell風の遅延評価による無限数列生成
www.ideone.com/ZZhdwh

初期値が一般的な値と異なってもトリボナッチ数列と呼んで良いようなので関数名はそうした。

**デフォルトの名無しさん** · 2023/06/23(金) 20:54:20.93

>>830
Haskell
https://ideone.com/WJrH5y

**638** · 2023/06/24(土) 00:18:48.24

>>830　Perl5

use feature qw{signatures say}; no warnings 'experimental';
use bigint;
sub g($n, @a) {
　push(@a, $a[-3]+$a[-2]+$a[-1]) while @a < $n;
　$a[-1];
}
say g($_, (0, 1, 2)) for 6, 9, 1000;

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

実行結果(CPU: Core-i7 8559u)
$ time perl 21_830.pl
11
68
1258890285439289522674621215321790399357402658069918084564035590888323288383996894058630489346490443306057821146808944309219589954636534445475146599057985479816395429617207869586544429749851128733512216004490332659216184693670760709292866744282443549293609850952277

real 0m0.143s
user 0m0.061s
sys 0m0.062s

**デフォルトの名無しさん** · 2023/06/24(土) 12:05:15.03

この問題10年前ぐらいで外資系のスキルテストで見たことあるな

**デフォルトの名無しさん** · 2023/06/24(土) 14:57:48.91

>>830
Java
https://paiza.io/projects/JYTlI5W0BPVSc-JPPoE2qg

**デフォルトの名無しさん** · 2023/06/24(土) 15:15:39.01

>>819
Java
https://paiza.io/projects/uykeDMT928Po7gCaDq_q9g

**デフォルトの名無しさん** · 2023/06/24(土) 15:31:35.78

>>830 ocaml
https://ideone.com/F63V9S

**デフォルトの名無しさん** · 2023/06/24(土) 19:11:36.41

>>807
Java
https://paiza.io/projects/yOQuLSMbxK4zja1xQGnahw?language=java

**デフォルトの名無しさん** · 2023/06/27(火) 07:02:47.02

この手の代数系のn乗計算に持ち込めるタイプは

a^(2n) = (a^n) × (a^n)
a^(2n+1) = (a^n) × (a^n) × a

を利用する実装ができてるかがミソやな

**デフォルトの名無しさん** · 2023/06/27(火) 17:20:06.80

>>738
C
https://ideone.com/JGH96u

まぁスーパー亀レスなんだけど普段はHaskellerなのでなんとかHaskellで完走できないかとアレやコレやと考えてみたんだけどダメだったorz
多分競プロに出るようなスーパーHaskellerならなんとかなるのかもしれないけど諦めた、試合終了
しかしせっかく色々考えたので備忘録がわりにCに移植
やっぱりCはえー、Haskellだと1分近くかかる計算が0.5秒とか
使ったのは有限体上のFourier変換

p = 1272446977、buffer size = 524288

で計算、buffer sizeを稼ぐためにBuffer sizeが2べきでなくても使えるように組んだんだけどCならそんなもんこだわらなくても余裕の完走なので結局2^19で利用
逆フーリエ変換も不要だと後で分かったけどせっかく作ったので残してあります

**デフォルトの名無しさん** · 2023/06/28(水) 02:38:39.77

>>819
Kotlin

Kotlin には coerceIn() というずばりそれをするための拡張関数があったのでそれを使った。
ついでに入力で負の値も受け付けるようにした。

https://paiza.io/projects/kOpfBfJtefVllIjHTVVX1g

**デフォルトの名無しさん** · 2023/06/28(水) 10:19:23.37

お題(初級)

a+b=cの式において、cが5で割り切れるためのaとbの組み合わせは何通りあるか

条件
1 <= c <= 10000000

**デフォルトの名無しさん** · 2023/06/28(水) 10:27:52.05

>>851
無限

**デフォルトの名無しさん** · 2023/06/28(水) 16:02:12.58

無限なわけ無いだろと思ったけどa, bが自然数とは指定されてないからなぁ

**蟻人間** ◆T6xkBnTXz7B0 · 2023/06/28(水) 17:05:55.94

お題：配膳ロボット。
あるレストランでは1台の配膳ロボットが活躍している。
配膳ロボットの仕事は、キッチンまで料理を取りに行き、
シェフに料理をもらい、料理をお客様まで持っていくことだ。

フロア図（上が北）：
＃＃＃＃＃＃＃
＃＿＿＿＿Ｃ＃
＃＃＃＃＿＃＃
＃Ｋ＿＃＿＿＃
＃＃＿＿＿Ｒ＃
＃＃＃＃＃＃＃

＃：カベ。Ｋ：キッチン。Ｒ：ロボット。Ｃ：お客様。＿：空きスペース。

ロボットには次のようなコマンドが定義されている：
　コマンド0：１つ待つ（料理を載せるのに必要な待ち時間）。
　コマンド1：西に1つ移動。
　コマンド2：東に1つ移動。
　コマンド3：北に1つ移動。
　コマンド4：南に1つ移動。

入力の盤面からロボットの仕事を完了するコマンドリストを生成せよ。

生成例）(1, 1, 1, 3, 1, 0, 2, 4, 2, 2, 3, 3, 3, 2, 0).

**デフォルトの名無しさん** · 2023/06/28(水) 22:25:22.22

>>854
R
www.ideone.com/TmKZmx

**デフォルトの名無しさん** · 2023/06/29(木) 21:40:36.19

>>855はもう少しすっきり書けた。
www.ideone.com/A4TRQe

**蟻人間** ◆T6xkBnTXz7B0 · 2023/06/29(木) 22:07:55.18

>>856
フロア図を変えても動くかな？
解法を少し解説お願いします。

**デフォルトの名無しさん** · 2023/06/29(木) 22:55:32.18

>>857
フロア図を変えた場合の実行例
www.ideone.com/vFtBf4

出発位置から目的位置まで複数の経路がある場合は最短経路が選択されるようになっている。

解法は単純で、行列Aの途中経過表示を見れば分かるように、出発位置fromからi + 1個の
コマンドで行ける位置にi + 1と印をつける操作を、i = 1, 2, 3, , ...について順々に、
目的位置toに到達するまで繰り返すだけ。

**蟻人間** ◆T6xkBnTXz7B0 · 2023/06/30(金) 13:09:46.14

お題：点と長方形の当たり判定。

「x0≦px＜x1かつy0≦py＜y1」のときtrueを返し、その他のときfalseを返す
関数PtInRect(px, py, x0, y0, x1, y1)を作成せよ。

例）
PtInRect(1, 2, 2, 2, 4, 3)→false.
PtInRect(3, 2, 2, 2, 4, 3)→true.
PtInRect(3, 3, 2, 2, 4, 3)→false.
PtInRect(4, 4, 3, 2, 5, 5)→true.
PtInRect(5, 4, 3, 2, 5, 5)→false.

**デフォルトの名無しさん** · 2023/06/30(金) 17:51:07.93

>>859
Kotlin script

fun PtInRect(px: Int, py: Int, x0: Int, y0: Int, x1: Int, y1: Int) = x0 <= px && px < x1 && y0 <= py && py < y1

**蟻人間** ◆T6xkBnTXz7B0 · 2023/06/30(金) 20:29:55.07

お題: テキストキャンバス、再び。

ヨコ20文字×タテ5文字の長方形の半角空白のテキストキャンバスがある。
(1) キャンバスの(x, y)の位置に半角文字chを書き込む関数SetPixelV(x, y, ch)を作成せよ。
(2) SetPixelVを使ってx0≦x≦x1かつy0≦y≦y1を満たす長方形領域(x, y)を半角文字chで塗りつぶす関数FillRect(x0, y0, x1, y1, ch)を作成せよ。
(3) テキストキャンバスを表示する関数PrintCanvas()を作成せよ。
(4) 次の処理を実行せよ。

FillRect(3, 0, 7, 4, '#');
SetPixelV(3, 0, ' ');
SetPixelV(3, 4, ' ');
SetPixelV(7, 4, ' ');
SetPixelV(7, 0, ' ');
FillRect(4, 1, 6, 3, ' ');
FillRect(11, 0, 11, 4, '#');
SetPixelV(12, 2, '#');
SetPixelV(13, 1, '#');
SetPixelV(14, 0, '#');
SetPixelV(13, 3, '#');
SetPixelV(14, 4, '#');
PrintCanvas();

**デフォルトの名無しさん** · 2023/06/30(金) 21:04:09.04

>>861
R　関数の引数には正しい値が与えられるものとし、エラーチェックは省略
www.ideone.com/lb8qym

**デフォルトの名無しさん** · 2023/07/01(土) 09:06:02.22

>>861
Kotlin

折角なのでそれ用のクラスを作った。

https://paiza.io/projects/IG4aL3pei3zdZ1b3br2H9g