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

**デフォルトの名無しさん** · 2023/05/23(火) 21:04:58.28

>>700
こっちのPowerShellでやれば全部OK
https://github.com/PowerShell/PowerShell
Name Value
---- -----
PSVersion 7.3.4
PSEdition Core

.NET 7凄すぎ

**デフォルトの名無しさん** · 2023/05/27(土) 01:36:20.91

お題：現在の日時の文字列が与えられるのでその文字列の先頭から秒数分を切り出して出力せよ

**デフォルトの名無しさん** · 2023/05/27(土) 02:11:47.73

>>702
それって秒の部分だけが残れば良いってこと? たとえば 2023/05/27 02:03:45 なら最後の 45 だけになれば良いの?
もしそうなら sed 使ってこうすればできるな。

sed 's/^.*://'

YYYY/MM/DD hh:mm:ss 形式ではなく秒が最後に出て来ない形式だったとしても最後のコロンの直後の数字が秒で、
その秒の数字文字列の後に数字でない文字が必ず来るのだとすれば (例えば Sat May 27 02:05:47 JST 2023 の
ような形式だとすれば)こうすれば良い。

sed 's/^.*://;s/[^0-9].*$//'

**デフォルトの名無しさん** · 2023/05/27(土) 02:42:42.27

サンプルケース書いてくれ

**デフォルトの名無しさん** · 2023/05/28(日) 09:45:16.03

お題　ナイトツアー

5×5の狭いチェスボードのどこかにナイトのコマを置きそこからナイトの可能な動きでコマを動かします
ただし同じマスは2回通れません
このとき全マス25マスを全て通る手順の数を数え上げて下さい
しかし実際全部数えるのは流石に無駄なので対称性を利用して
♯{A1→B3}×8
+ ♯{A3→B5}×8 + ♯{A3→C4}×8
+ ♯{B2→C4}×8
+ ♯{C3→D5}×8
はよいとします

例
♯{A1→B3} = 152

--ナイトの動き--
桂馬の動きと同じ、水平方向の移動量+垂直方向の移動量 = 3となる移動(もちろん盤の中)

**デフォルトの名無しさん** · 2023/05/28(日) 11:22:07.87

>>705

訂正
> --ナイトの動き--
水平方向の移動量+垂直方向の移動量 = 3となる移動で水平、垂直な移動はなし(もちろん盤の中)

**デフォルトの名無しさん** · 2023/05/28(日) 23:12:57.01

>>705
対称性を考慮するのは面倒なので全部数え上げる。Rで書いたら5秒以内に到底終わらなかったので、
ideone.com/y5Dwy7
C++に移植した。盤面表示はideoneでは途中で切れてしまうので非表示にした（関数moveの
コメント部分をコメントでなくせば表示される）。
ideone.com/6Muw9F

対称性を考慮すれば、手順数は1728 / 8 = 216通りになる。

**蟻人間** ◆T6xkBnTXz7B0 · 2023/05/29(月) 01:40:51.78

お題: 水の流れる複数のタンクにおいて水の流れをシミュレーションしたいので、以下に定義する入力文字列でタンクと
水の流れなどを記述する。入力文字列は次のような形式の行の並びとする。

「(タンクの名前), (タンクの底面積[m^2]), (タンクの底からの排水口までの高さ[m]), (次のタンクの名前)」

各行は各タンクの情報とその次のタンクを表す。入力文字列の最初の行は最初に水が入るタンクに対応する。最初のタンクには外部から水が0.5[m^3/min]の速度で入る。タンクの形状は円錐か四角錐とし、底面は平面状とする。
各タンクには排水口が付いているかも知れない。排水口があるのならそれはタンクの底より高く、タンクの側面に付いている。
排水口は次のタンクにつながっている。次のタンクはその前のタンクより低い位置にある。各タンクにおいて排水口に水が届いていないときは水は排水されない。
タンクとタンクの間の長さと水の落差にかかる時間は無視して構わない。次のタンクがN/Aならそのタンクに排水口と排水先はない。

シミュレーション開始後、1分ごとに各タンクに何[m^3]の水が入っているかを出力せよ。タンクCが満タンなら終了せよ。

(入力)
A, 3, 0.5, B
B, 2, 0.7, C
C, 1, 0.4, N/A

**デフォルトの名無しさん** · 2023/05/29(月) 01:46:57.43

>>705
Kotlin

馬鹿正直に再帰で全パターンやっているだけ。
途中経過は出力しない。既に置かれたマスは1bitで記録されるようにして 5 * 5 = 25 bit で Int (32bit) に収まるのでそれを利用している。
恐らく Boolean の配列を使って書くとそこまで最適化されなさそうなのでこうした。

https://paiza.io/projects/O4Ejxs76h64GSeXYCVs2mg

結果は同じ 1728 になったので多分これで合っていると思う。

**デフォルトの名無しさん** · 2023/05/29(月) 23:38:05.56

>>705
>>707にちょっと付け加えたら対称性を考慮して数え上げることができた。
://ideone.com/NSyJcK (R)
://ideone.com/S1VIUA (C++)

Rでは5秒以内に終わらなかった。

**蟻人間** ◆T6xkBnTXz7B0 · 2023/05/30(火) 20:06:49.36

お題: x-y平面上に摩擦のないすべり台がある。重力加速度を9.8[m/s^2]とし、重力はy軸とは逆向きに作用している。
この滑り台は動かないように固定されている。横位置x>=0[m]についてf(x)がすべり台の面の高さ[m]を表す。
体重35kgの子どもがx=0の場所から滑り台を滑り始めた。次の場合の5秒後の子どもの位置ベクトルと速度ベクトルを求めよ。空気抵抗は無視する。

(i) f(x)=10-sqrt(x)。
(ii) f(x)=10-sqrt(sqrt(x))。

※ xの平方根をsqrt(x)とする。

**デフォルトの名無しさん** · 2023/06/01(木) 09:25:39.43

お題

アルファベットが入力されます
> [A, A, B, B, B, C, C, D, D, D, E]

出力上限が入力されます
> 7

出力上限以内のアルファベットを出力してください
> [A, A, B, B, B, C, C]

ただし、出力上限で切った場合に同じアルファベットが分割される場合は出力上限を超えて
同じアルファベットが続く限り出力してください

アルファベット: [A, A, B, B, B]
出力上限: 3
出力: [A, A, B, B, B]

**デフォルトの名無しさん** · 2023/06/01(木) 21:49:43.70

>>712
C#でループを使わずに出力
www.ideone.com/Xk3ACt

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

お題：矩形に整形された全角文字のテキストが与えられる。左上から時計回りに
渦巻き状に読んだ文字列を、元の矩形と同文字数で桁数がより多く最も近い矩形に
左上から時計回りに渦巻き状に並べて出力せよ。

[例]
プログラ　　→　　プログラミン
題スレミ　　　　　レス題おのグ
おのグン

[問題]
メロスは激怒した。必ず、かの邪智暴虐の王を除かなけ
ては、人一倍に敏感であった。きょう未明メロスは村れ
し、内気な妹と二人暮しだ。この妹は、村の或る律をば
対の嫁の衣裳やら祝宴の御馳走やらを買いに、は気出な
に六花ロスには竹馬の友があった。セリヌンテるな発ら
悪十、メてみるつもりなのだ。久しく逢わなィば一しぬ
邪。え。ねスは、まちの様子を怪しく思っかウる牧、と
もいゆた訪ロのは当りまえだが、けれどたっス市人野決
ど無れいらメい全体が、やけに寂しいも。たでにをを意
れもそ歩かに暗市不安になって来た。、ひのあや、越し
け房、られちの、ん衆をつかまえ。のなっだるっ近えた
。女はぶこうちくだい若たっ逢で路んんそか。て々山。
た。スら、るま無んだ、もスロメなきだりら今来、越メ
来いロぶをい、はでりかばいせの夜、かし、はた花えロ
て無メを友ててち落も日に既うも。るいて訪此の婿、ス
しも。路のい歩。るあでみし楽がのく行てねのだと十に
暮母る大そ。るいてしを工石、で市のスクラシ。し里は
で、あの都らかれそ、め集い買を々品のそ、ず先ては政
んもでのなか近間も式婚結。たいてっなに事るえ迎な治
遊父はにスロメ。た来てっやに市のスクラシの此たれが
と羊、き吹を笛。るあで人牧の村、はスロメ。ぬらかわ

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

>>714
この部分の意味がわからない。どうしろというのか？

> 元の矩形と同文字数で桁数がより多く最も近い矩形

**デフォルトの名無しさん** · 2023/06/02(金) 00:10:19.23

>>715
[例]で言えば、3行×4桁=12文字が矩形に並ぶのは1, 2, 3, 4, 6, 12桁のときだから、
4桁より多く4桁に最も近いのは6桁となる。

**デフォルトの名無しさん** · 2023/06/03(土) 18:04:48.61

>>712
Kotlin
https://paiza.io/projects/o3Y5W0EXe0CxGFZTAXhtAQ

**蟻人間** ◆T6xkBnTXz7B0 · 2023/06/04(日) 14:05:22.78

お題: 郵便切手の問題。

切り離されていない、一列に並んだn枚の切手を考える。
一枚の切手の上に全ての切手を折り込む時、
左端の切手を表向きで一番上に折り込む方法は何通りか計算せよ。

**638** · 2023/06/04(日) 19:16:56.02

>>714 Perl5
https://www.ideone.com/XpTafZ

**638** · 2023/06/04(日) 20:52:10.72

>>712 Perl5

use feature qw{signatures say};
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, $c, splice @s, 1) if $c eq $s[0];
　}
}

say f 7, qw[A A B B B C C D D D E];
say f 3, qw[A A B B B];

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

実行結果

$ perl 21_712.pl
AABBBCC
AABBB

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