プログラミングのお題スレ 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/

**蟻人間** ◆T6xkBnTXz7B0 · 2023/06/09(金) 20:55:26.51

お題: 与えられた4頂点が長方形または正方形を形成するかどうか判定せよ。長方形または正方形のときtrueを返すものとする。頂点の順序は無視する。

例)
{ (0, 0), (1, 0), (1, 1), (0, 1) } → true.
{ (0, -1), (0, 1), (1, 0), (-1, 0) } → true.
{ (0, -2), (1, 0), (0, 2), (-1, 0) } → false.

**蟻人間** ◆T6xkBnTXz7B0 · 2023/06/09(金) 22:16:01.89

お題: コマンドロボット。

ロボットはx-y平面の原点(0, 0)に居る。
コマンドIDはロボットによる何かのアクションを表す0以上4以下の整数で、次のように定義する。

コマンド0は何もしない。
コマンド1は位置が(-1, 0)だけ動く。
コマンド2は位置が(+1, 0)だけ動く。
コマンド3は位置が(0, -1)だけ動く。
コマンド4は位置が(0, +1)だけ動く。

入力として、コマンドIDのリストが与えられる。コマンドを順番に実行したときの最終位置を出力せよ。

例)
(2, 3, 0, 3, 1) → (0, -2).
(1, 1, 4, 0, 0, 2) → (-1, 1).

**デフォルトの名無しさん** · 2023/06/09(金) 22:46:11.50

>>743
R
www.ideone.com/hNR3VK

**デフォルトの名無しさん** · 2023/06/09(金) 22:55:53.04

>>739 >>742
正解。

出題者によるプログラム
www.ideone.com/0R9KaI

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

>>744
R
www.ideone.com/eH07Wk

**蟻人間** ◆T6xkBnTXz7B0 · 2023/06/09(金) 23:20:35.60

お題: コマンドロボット2。

ロボットはx-y平面の原点(0, 0)に居る。
コマンドIDはロボットによる何かのアクションを表す0以上4以下の整数で、次のように定義する。

コマンド0は何もしない。
コマンド1は位置が(-1, 0)だけ動く。
コマンド2は位置が(+1, 0)だけ動く。
コマンド3は位置が(0, -1)だけ動く。
コマンド4は位置が(0, +1)だけ動く。

入力として、最終位置が与えられる。原点から最終位置まで移動する最短のコマンドIDリストを生成せよ。
最終位置のx成分とy成分がどちらも非ゼロならx成分から先に移動せよ。

例)
(2, -3) → (2, 2, 3, 3, 3).
(-1, 3) → (1, 4, 4, 4).

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

>>748
R

FormatArray <- function(a) paste0("(", paste0(a, collapse = ", "), ")")
P <- list(c(2, -3), c(-1, 3), c(0, 0))
for (p in P) cat(FormatArray(p), " → ", FormatArray(rep((sign(p) + c(3, 7)) / 2, abs(p))), "\n", sep = "")

[実行結果]
(2, -3) → (2, 2, 3, 3, 3)
(-1, 3) → (1, 4, 4, 4)
(0, 0) → ()

**デフォルトの名無しさん** · 2023/06/10(土) 01:30:29.55

>>722
Kotlin

○付き数字はブラウザやフォントの設定によっては表示が文字ごとに大きかったり小さかったりするかも知れない。

https://paiza.io/projects/I5rPp0OBjWg6RdMlWu3t5g

**蟻人間** ◆T6xkBnTXz7B0 · 2023/06/10(土) 11:10:34.93

お題: x=0～πの範囲(step: π/8)でsin(x)を数値微分(dx=0.001)すると、その値sin'(x)がほぼcos(x)に一致することを示せ。
xの各値に対する計算結果(x, sin(x), sin'(x), cos(x))を一行に並べて表示せよ。
各数値は小数点以下3桁まで表示するものとする。

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

>>748 ruby

def moves(x, y)
[].fill(x < 0 ? 1 : 2, ...x.abs) + [].fill(y < 0 ? 3 : 4, ...y.abs)
end
=> :moves
moves(2, -3)
=> [2, 2, 3, 3, 3]
moves(-1, 3)
=> [1, 4, 4, 4]
moves(0, 0)
=> []

**蟻人間** ◆T6xkBnTXz7B0 · 2023/06/10(土) 12:03:39.21

お題: 物理シミュレーション。

運動方程式によると、位置の微分が速度になり、速度の微分が加速度となっている。
逆に言えば加速度の積分と初速から現在の速度が求まり、速度の積分と初期位置から現在の位置が求まる。

数直線上を移動可能な点Pがある。Pの初期位置は原点0[cm]とする。Pの初速はゼロ[cm/s]とする。

入力として加速度[cm/s^2]と加速時間[s]のペアのリストが与えられる。時刻t=0[s]から入力に従って点Pが加速する。
dt=0.1として区分求積法により加速度と速度を数値積分し、1秒ごとのPの位置と速度を5秒後まで出力せよ。各数値は小数点以下2桁まで表示せよ。

例) ((1, 1), (-1, 1), (2, 0.5), (-4, 0.25), (3, 1.25), (-8, 1))

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

>>738 c
・>>742から若干の省メモリ化
　判別用配列の要素をintからcharへ
　素数の個数を数えてから一覧用領域を確保
・組み合わせループの条件を>>746さんを参考に改善
https://ideone.com/CixK7I

>>738 c
・上記からさらに省メモリ化
　判別用配列はint配列だが判別はビットごと
https://ideone.com/JDcFjV

**754** · 2023/06/10(土) 16:17:23.88

>>754
誤： for (i = 2; i <= n; i++) if (at(map, i)) nprimes++;
正： for (i = 2, nprimes = 0; i <= n; i++) if (at(map, i)) nprimes++;

**蟻人間** ◆T6xkBnTXz7B0 · 2023/06/10(土) 20:13:01.15

>>751
C++ 回答例
https://ideone.com/QdLtnJ

**デフォルトの名無しさん** · 2023/06/10(土) 23:02:02.89

>>744
Java
https://paiza.io/projects/Y3CoVhKtAgw03ZnnwF8GEA

**デフォルトの名無しさん** · 2023/06/10(土) 23:37:30.81

>>749
Java
https://paiza.io/projects/79057xQfec28jB_BAD40oQ?language=java

**デフォルトの名無しさん** · 2023/06/11(日) 00:07:26.45

お題：数学的に植物を描画せよ

**デフォルトの名無しさん** · 2023/06/11(日) 00:37:53.77

>>753
www.ideone.com/jv00La

Rで書いたらdouble型の精度の問題で期待通りに動作しなかったので、decimal型を使えるC#で書いた。
例のリストで解析解と一致する数値解が得られるように、速度は台形則、位置は台形則と中点則の平均
（結局は刻み幅が半分での台形則に一致するが）で計算した。参考のためstdinに解析解を書いておいた。

**638** · 2023/06/11(日) 02:58:42.46

力ずく問題は苦手なインタプリタ―だが、速度に配慮した書き方をすればこの規模だと数分程度で解ける…

use feature qw{:5.16 signatures say};
$m = 1234567;
%h = map{$_ => ++$k} 2..$m;
for $i (2..int(sqrt $m)) {
　if (exists $h{$i}) {
　　for ($i..(int($m / $i)+1)) { delete $h{$i * $_} }
　}
}
@p = sort{$a <=> $b} keys %h;
%o = map{$p[$_] => $_} 0..$#p;
for $i (0..$#p-2) {
　$p1 = $p[$i];
　last if $m <= 3 * $p1;
　for $j ($i+1..$#p-1) {
　　$p2 = $p[$j]; $s = $p1 + $p2;
　　$r = $m - $s; last if $r <= $p2;
　　$n++ if exists $o{$r};
　}
}
print "n = $n\n";

実行結果 (CPUは Core-i7 8995u、Mem: 32GB)
$ time perl 21_738_prime+1234567.pl
n = 151055501

real 5m48.035s
user 5m44.468s
sys 0m3.250s

出題者の解と合わん…＞＜

**638** · 2023/06/11(日) 03:01:19.54

>>761 アンカーしくった＞＜
>>738 Perl5

**デフォルトの名無しさん** · 2023/06/11(日) 20:59:06.26

>>761
インタプリタでもRだともっと速い。以下のプログラムを https: //tio.run で実行すると
9.96秒で完了し、解は>>746の151060650通りと合う。>>761は制限時間 (1分) 以内に
完了しない。Rは自前のループをなるべく書かずにベクトル演算にすれば割と速い。

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
p <- which(isprime)
q <- cumsum(isprime)

k <- 0L
for (i in p[1:q[n %/% 3L]]) {
　　m <- n - i
　　k <- k + sum(isprime[m - p[q[i]:q[m %/% 2L]]])
}
cat(k, "通り\n", sep = "")

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