プログラミングのお題スレ 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/04(日) 23:24:30.12

>>712 Perl5、もっと簡潔なやり方あるんだった…orz

use feature qw{signatures say};
sub f($n, $s) {
　my $r = '^.{' . ($n - 1) . '}(.)\1*';
　$s =~ /$r/;
　$&;
}
say f 7, 'AABBBCCDDDE';
say f 3, 'AABBB';

実行結果
$ perl 21_712_rex.pl
AABBBCC
AABBB

**デフォルトの名無しさん** · 2023/06/05(月) 17:20:26.45

お題　逆順に

文字列が与えられます
使われている文字のリストを作って並べその“反対の”文字を対応させます
例えば登場文字列が
HELLO WORLD
なら出てくる文字をコード順に並べると
" DEHLORW"
であるので
E → O, L →H, ' '→W
となります(空白、句読点等一切区別せず一文字と考えます)
この対応で入力された文字列を変換してください

例　
HELLO WORLD →
LOHHEW EDHR

⑨⑫⑦②⑤⑭⑰⑳㉔①⑩⑬㉒⑲④⑮⑪⑧㉓⑥③⑯㉑⑱ →
⑯⑬⑱㉓⑳⑪⑧⑤①㉔⑮⑫③⑥㉑⑩⑭⑰②⑲㉒⑨④⑦

**デフォルトの名無しさん** · 2023/06/05(月) 19:56:23.90

>>722
Java
https://paiza.io/projects/ThIWBUU33EC_Tv88KPog8A

**638** · 2023/06/05(月) 20:41:22.90

>>720 もっとすんなり書けるんだった… orz

　　$c, f(0, $c, splice @s, 1) if $c eq $s[0];
　　↓
　　$c, f(0, @s) if $c eq $s[0];

関数全体のコードとしてはこうなる：

sub f($n, $c, @s) {
　if (1 < $n) {
　　$c, f($n - 1, @s);
　} elsif (1 == $n) {
　　$c, f(0, $c, @s);
　} else {
　　$c, f(0, @s) if $c eq $s[0];
　}
}

すっきりした形になりました

**638** · 2023/06/05(月) 21:31:53.30

>>722 Perl5

use feature qw{signatures say};
use utf8; binmode STDOUT => 'utf8';
use Encode 'encode';

sub f($s) {
　@s = split '', $s;
　%h = map{unpack('H*', encode('utf-8', $_)) => $_} @s;
　@i = reverse @c = sort keys %h;
　%o = map{$h{$c[$_]} => $h{$i[$_]}} 0..$#c;
　say map{$o{$_}} @s;
}

f 'HELLO WORLD';
f '⑨⑫⑦②⑤⑭⑰⑳?①⑩⑬?⑲④⑮⑪⑧?⑥③⑯?⑱';

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

実行結果:
$ perl 21_722.pl
LOHHEW EDHR
⑯⑬⑱?⑳⑪⑧⑤①?⑮⑫③⑥?⑩⑭⑰②⑲?⑨④⑦

**638** · 2023/06/05(月) 21:35:18.29

>>722 Perl5 ｽﾏｿ、ﾋﾞｭｰﾜｰから書き込んだら丸数字の一部が文字化けしたのでﾌﾞﾗｳｻﾞから再書き込み

use feature qw{signatures say};
use utf8; binmode STDOUT => 'utf8';
use Encode 'encode';

sub f($s) {
　@s = split '', $s;
　%h = map{unpack('H*', encode('utf-8', $_)) => $_} @s;
　@i = reverse @c = sort keys %h;
　%o = map{$h{$c[$_]} => $h{$i[$_]}} 0..$#c;
　say map{$o{$_}} @s;
}

f 'HELLO WORLD';
f '⑨⑫⑦②⑤⑭⑰⑳㉔①⑩⑬㉒⑲④⑮⑪⑧㉓⑥③⑯㉑⑱';

実行結果
$ perl 21_722.pl
LOHHEW EDHR
⑯⑬⑱㉓⑳⑪⑧⑤①㉔⑮⑫③⑥㉑⑩⑭⑰②⑲㉒⑨④⑦

**デフォルトの名無しさん** · 2023/06/05(月) 22:09:27.65

>>722
PowerShell 4以上 (U+10000以上の文字、結合文字、異体字セレクタに対応)

foreach ($s in "HELLO WORLD", "⑨⑫⑦②⑤⑭⑰⑳㉔①⑩⑬㉒⑲④⑮⑪⑧㉓⑥③⑯㉑⑱", "魚と花󠄁か゚𩸽") {
　　$c = [Globalization.StringInfo]::GetTextElementEnumerator($s) | sort | unique
　　$h = @{}
　　0..($c.length - 1) |% {$h[$c[$_]] = $c[-$_ - 1]}
　　-join $h[[Globalization.StringInfo]::GetTextElementEnumerator($s)]
}

[実行結果]
LOHHEW EDHR
⑯⑬⑱㉓⑳⑪⑧⑤①㉔⑮⑫③⑥㉑⑩⑭⑰②⑲㉒⑨④⑦
と魚花󠄁𩸽か゚

**638** · 2023/06/06(火) 01:24:29.34

>>726 しくった
utf-8文字を可変長16進数にunpackして辞書的順番でsortするので、例題では意図した通りの結果を得られたが、
半角と全角などutf-8でバイト数の異なる文字が混在する文字列の場合には、順番が違ってくるだろうな…

**638** · 2023/06/06(火) 02:40:16.03

>>726 Perlで文字の数値コードを返すord()関数は半角文字の場合にASCIIコードを返すが、
全角Unicode文字ではコードポイントを返す、ということなので、素直にそれを使い、
文字列としてっではなく数値としてsortし

　%h = map{unpack('H*', encode('utf-8', $_)) => $_} @s;
　@i = reverse @c = sort keys %h;
　　↓を
　%h = map{ord($_) => $_} @s;
　@i = reverse @c = sort{$a <=> $b} keys %h;

と修正するのがよさげ。連投ｽﾏｿ

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

>>714 octave
https://ideone.com/MXrAYt
m2c = @(m, r, c) mat2cell(m, repelem(r, size(m, 1) / r), repelem(c, size(m, 2) / c));
s2c = @(s) m2c(s, 1, 3);
function v = e2v(e, v)
if nargin < 2
v = e2v(e, []);
elseif ~isempty(e)
v = e2v(rot90(e(2:end, :)), [v e(1, :)]);
end
end
function ind = eddyind(varargin)
if nargin == 2
ind = e2v(reshape(1:times(varargin{1:2}), varargin{1:2}));
elseif nargin == 1
ind = eddyind(size(varargin{1}, 1), size(varargin{1}, 2));
end
end
s = 省略
c = s2c(s);
n = numel(c);
m = find(rem(n, 1:n) == 0 & size(c, 2) < 1:n)(1);
d = cell(n / m, m);
d(eddyind(d)) = c(eddyind(c));
disp(cell2mat(d));

**デフォルトの名無しさん** · 2023/06/06(火) 21:42:34.58

>>722 ruby
https://ideone.com/yqb6sd
f = ->(s) {s.chars.uniq.sort.join.tap{|u| break s.tr(u, u.reverse)}}
p f.('HELLO WORLD')
p f.('⑨⑫⑦②⑤⑭⑰⑳㉔①⑩⑬㉒⑲④⑮⑪⑧㉓⑥③⑯㉑⑱')
#p f.('HELLO WORLD-') # trのパターンになっちゃう文字があるとダメ

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

>>722
>>727では大・小・全角・半角文字が区別されないのを修正した。PowerShell 2でも正しく動作するようになった。

foreach ($s in "HELLO WORLD", "⑨⑫⑦②⑤⑭⑰⑳㉔①⑩⑬㉒⑲④⑮⑪⑧㉓⑥③⑯㉑⑱", "魚と花󠄁か゚𩸽", "HeLLO ＷoRＬD") {
　　$c = [Globalization.StringInfo]::GetTextElementEnumerator($s) | sort -unique {[int[]][char[]]$_}
　　$h = New-Object Collections.Hashtable
　　0..($c.length - 1) |% {$h[$c[$_]] = $c[-$_ - 1]}
　　-join $h[[Globalization.StringInfo]::GetTextElementEnumerator($s)]
}

[実行結果]
LOHHEW EDHR
⑯⑬⑱㉓⑳⑪⑧⑤①㉔⑮⑫③⑥㉑⑩⑭⑰②⑲㉒⑨④⑦
と魚花󠄁𩸽か゚
oLeeRＷ HODＬ

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

お題
A,B,Cがランダムにいくつか入力されます

隣り合う文字が異なるときそれらは同じグループです
A,B → [A,B]

隣り合う文字が同じ時それらは異なるグループです
A,A → [A],[A]

A,B,A,A,A,B → [A,B,A],[A],[A,B]

もっとも長いグループを出力してください

入力
B,A,B,C,B,B,B,A,C,C,A,B,A,A,C,A,B,C,C,C,B,C,A,B,C,A,A,A,C,B

出力
[C,B,C,A,B,C,A]

**638** · 2023/06/08(木) 01:33:27.84

>>733　Perl5

use feature qw{:5.16 signatures say};
@a = ([]);
sub ($c, @s) {
　push @{$a[-1]}, $c;
　push @a, [] if $c eq $s[0];
　__SUB__->(@s) if @s;
}->(qw{B A B C B B B A C C A B A A C A B C C C B C A B C A A A C B});
$c = (sort{@$a <=> @$b} @a)[-1];
$" = ','; say "[@$c]";

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

実行結果
$ perl 21_733.pl
[C,B,C,A,B,C,A]

**デフォルトの名無しさん** · 2023/06/08(木) 10:35:46.63

>>712
Kotlin

抜き出す数の指定が 0 以下の場合は空のリストになるようにした。

https://paiza.io/projects/oE3GVsi4b0sNqSXQ78_7gg

**デフォルトの名無しさん** · 2023/06/08(木) 21:24:06.92

>>733
PowerShell

$s = "B,A,B,C,B,B,B,A,C,C,A,B,A,A,C,A,B,C,C,C,B,C,A,B,C,A,A,A,C,B"
@($s -replace "(.),(?=\1)", "`$1/" -split "/" | group length | sort -descending {[int]$_.name})[0] |% {$_.group}

[実行結果]
C,B,C,A,B,C,A

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

>>733 ocaml
https://ideone.com/jfFx3Y
open List
let (<<) f g x = f (g x)
let flip f x y = f y x
let f =
let aux x = function
[] :: ys -> [x] :: ys
| (z :: _) as y :: ys -> if x = z
then [x] :: y :: ys
else (x :: y) :: ys
in rev << hd << rev << map snd << sort compare << map (fun x -> (length x, x)) << fold_left (flip aux) [[]]
let g = print_newline << iter print_char << f
let () = g ['B';'A';'B';'C';'B';'B';'B';'A';'C';'C';'A';'B';'A';'A';'C';'A';'B';'C';'C';'C';'B';'C';'A';'B';'C';'A';'A';'A';'C';'B']

>>733 ruby
f = ->(a) {a.each_with_object([[]]) {|x, acc| acc[-1][-1] != x ? acc[-1] << x : acc << [x]}.sort_by(&:size)[-1]}
p f.(%w(B A B C B B B A C C A B A A C A B C C C B C A B C A A A C B))

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

お題：1234567以下の素数 a, b, c で a + b + c = 1234567 かつ a ≤ b ≤ c を満たす組み合わせは何通りあるか計算せよ。

**デフォルトの名無しさん** · 2023/06/09(金) 04:35:40.14

>>738
https://ideone.com/4YftKh

力業っぽくなったな、3で割って1余る整数計しか解けない

**デフォルトの名無しさん** · 2023/06/09(金) 08:47:59.66

実質力技しかないやろな
割ったあまりとかで多少減らせる程度にしかならない

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

入力nに対してn以下の素数はn オーダーある
最初に素数list upするのにn オーダー、そこから足してnを見つけるのはどうやってもn²オーダーよりは早くできそうにない

**デフォルトの名無しさん** · 2023/06/09(金) 20:08:26.01

>>738 c
https://ideone.com/Dbl6mc
#include <stdlib.h>
#include <math.h>
#include <stdio.h>
void sieve_of_eratosthenes(int n, int **isprime, int **primes_beg, int **primes_end) {
int i, m, j, nbytes = (1 + n) * sizeof **isprime, *map = malloc(nbytes), *beg = malloc(nbytes), *end;
for (i = 2; i <= n; i++) map[i] = 1;
for (i = 2, m = sqrt(n); i <= m; i++)
if (map[i]) for (j = i * i; j <= n; j += i) map[j] = 0;
for (i = 2, end = beg; i <= n; i++) if (map[i]) *end++ = i;
*isprime = map, *primes_beg = beg, *primes_end = end;
}
int main() {
int n = 1234567, *isprime, *primes_beg, *primes_end;
sieve_of_eratosthenes(n, &isprime, &primes_beg, &primes_end);

int *a, *b, c, count = 0;
for (a = primes_beg; a < primes_end && *a <= n / 3; a++)
for (b = a; b < primes_end && *b <= (c = n - *a - *b); b++)
if (isprime[c]) count++;
printf("count = %d\n", count);
return 0;
}

**蟻人間** ◆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);