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

**デフォルトの名無しさん** · 2019/11/17(日) 09:00:22.10

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

【出題と回答例】
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/

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

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

**デフォルトの名無しさん** · 2019/12/07(土) 22:36:30.68

>>160
Rでお決まりの再帰呼び出し。
https://ideone.com/LkPChG

**デフォルトの名無しさん** · 2019/12/07(土) 23:22:48.98

分割数でググれば考え方いっぱい出てくるよ

**デフォルトの名無しさん** · 2019/12/08(日) 13:36:47.70

>>160
C++
https://ideone.com/QVywdv

**デフォルトの名無しさん** · 2019/12/08(日) 13:57:09.43

>>154
最後の文はどこから出てきたの？

**デフォルトの名無しさん** · 2019/12/08(日) 13:58:38.12

>>164
元のスレ

**デフォルトの名無しさん** · 2019/12/08(日) 14:21:04.90

しらんがな

**デフォルトの名無しさん** · 2019/12/08(日) 14:22:15.55

その制限が無い方がアルゴリズムとしておもしろい
制限があるとつまらなすぎる

**デフォルトの名無しさん** · 2019/12/08(日) 17:19:46.37

知らんがなって
なら聞くなアホ

**デフォルトの名無しさん** · 2019/12/08(日) 17:53:26.22

すまん

不満は>>150に言ったつもり
そんな重要な事を省略すんなって

**デフォルトの名無しさん** · 2019/12/08(日) 19:17:22.87

別に項数の制限はつけていませんよ
「項数の制限が無い」という事を省略したのに怒っているのならすいません。
ですが制限があるのなら普通に問題文に加えますし、別に書くほどの事では無いかな～と

**デフォルトの名無しさん** · 2019/12/08(日) 19:37:55.14

>>150
https://ideone.com/OJyvxF
C++。総当たりです。スカイレークのi7で12秒くらいかかります。
久しぶりにまじめに総当たりを書いた気がしました。

**デフォルトの名無しさん** · 2019/12/08(日) 19:44:34.35

>>150
https://ideone.com/p6FUh4

オマケで、答えが見える版を置いておきます。C++。

**デフォルトの名無しさん** · 2019/12/08(日) 20:22:49.16

ちなみにオーダーは大体O(N!)位です。（笑

**デフォルトの名無しさん** · 2019/12/08(日) 20:35:11.71

ギャグですけど、並列化は比較的簡単なのでそれで時間短縮はできます。
底の値をシェアードにすると早く終わります。Nになってると思うんだけど。

**デフォルトの名無しさん** · 2019/12/08(日) 20:48:51.01

一回を関数に切り出して実行した場合、
一回のイテレーションが大体100回のループに収まるはずなのでザクザクおわります。
多分。

**デフォルトの名無しさん** · 2019/12/08(日) 20:49:16.37

一回を関数に切り出して実行した場合、
一回のイテレーションが大体100回のループに収まるはずなのでザクザクおわります。
多分。

**デフォルトの名無しさん** · 2019/12/08(日) 20:59:32.19

ぐあ、重複した・・・。

**デフォルトの名無しさん** · 2019/12/08(日) 21:17:04.79

>>150
これは問題の設定がつまらないな。1～20の中から10個を選んで元の集合を作るから、
結果に1個か2個の和しかほとんど現れず、集合の最初の方をパッと見ただけで
暗算でも分かってしまう。1～5000の中から10個を選ぶ設定にすると、
結果がなしだったり、3個の和と4個の和だったり、2個の和と6個の和だったり、
変化に富んで面白くなる。https://ideone.com/kmihyT

例えば、リンク先にある

入力: [63, 70, 269, 949, 1337, 2670, 3538, 3764, 4183, 4320]
出力: Σ[3764, 4183] = Σ[63, 70, 269, 1337, 2670, 3538] = 7947

なんてパッと見では思いつかないから、コンピュータに探させる意義がある。

**デフォルトの名無しさん** · 2019/12/08(日) 21:27:36.39

>>178
異様に早いなーと思ったら、言語にコンビネーションあるんかいな。
裏山シー。

**デフォルトの名無しさん** · 2019/12/08(日) 22:01:27.05

サンプルだから人間が簡単に検証できるようにしてるんでしょ
普通それぐらいはわかりそうなもんだけど、>>165みたいに項数だと思う奴とか>>178みたいにイチャモンつける奴とか世の中広いわw

**デフォルトの名無しさん** · 2019/12/08(日) 22:35:33.47

>>180
そんなことは分かっているよ。だから、お題通りの1～20の場合も>>157でちゃんと回答した。
その上で、もっと面白い場合の追加を提案してみただけ。

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

>>150
N!より速い方法ある？

**デフォルトの名無しさん** · 2019/12/09(月) 00:53:44.24

>>182
動的計画法？

**デフォルトの名無しさん** · 2019/12/09(月) 01:15:42.30

https://ideone.com/52jcdq
全ての和を計算して並べ替えるだけ
多分最も愚直な方法

**デフォルトの名無しさん** · 2019/12/09(月) 01:57:50.57

bit演算で面倒なことやってたけどpairっての使えば良かったのか

**デフォルトの名無しさん** · 2019/12/09(月) 02:04:04.39

>>150　https://ideone.com/tKvgv3

By PyPy、　ノーマルpythonでは力業の(N=20)が8秒くらいかな、

力業が　2^N * N

最小値だけなら、N*数列の合計 = N^2 * 数の平均(/2) ででる(みたい？)
(自信ががないDP解)

**デフォルトの名無しさん** · 2019/12/09(月) 02:51:44.21

>>180
日本語が読め無い馬鹿発見

**デフォルトの名無しさん** · 2019/12/09(月) 04:54:54.63

>>181
わかってたら
> これは問題の設定がつまらないな。
なんていう物言いにはならんだろ

>>187
夜中まで必死だな…
何に必死なのかよくわからんけどw

**デフォルトの名無しさん** · 2019/12/09(月) 05:00:22.33

必死なのはお前だろ
お前一人だけ日本語すらまともに読めてない馬鹿だって気づけよ

**デフォルトの名無しさん** · 2019/12/09(月) 06:12:33.29

うわっ、アホが無駄に絡んできたよw

**デフォルトの名無しさん** · 2019/12/09(月) 06:42:21.59

明け方からどんだけ必死なんだよ
以降、劣等感の塊のID:wE9bCkNRくんが全レスしてくれるってよ！

**デフォルトの名無しさん** · 2019/12/09(月) 06:46:34.43

こいつ少し上の方でレスバしてたアホやろ？
さんざん馬鹿にされて悔しい思いしたから早朝にちょろっと顔出してるんやろ

**デフォルトの名無しさん** · 2019/12/09(月) 07:23:51.05

単芝ガイジ君、情けなさ過ぎて草

**デフォルトの名無しさん** · 2019/12/09(月) 12:30:02.62

>>192
自己紹介乙ww

**デフォルトの名無しさん** · 2019/12/09(月) 15:19:21.58

https://ideone.com/aYEPpX
C++面白いな

**デフォルトの名無しさん** · 2019/12/09(月) 15:48:30.74

(sum[i].second & sum[i + 1].second) == 0
この比較はいらないのかな
これが重なってるならより小さい重なってない組合せが必ず存在するか

**デフォルトの名無しさん** · 2019/12/09(月) 21:07:53.73

お題：2つの素数（2つは同じでもよい）の積で表される数は半素数と呼ばれる。
1万以下の半素数をすべて表示せよ。

**デフォルトの名無しさん** · 2019/12/09(月) 21:20:18.06

int prime[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,91};

**デフォルトの名無しさん** · 2019/12/09(月) 21:22:25.12

91じゃなかった

◆QZaw55cn4c · 2019/12/09(月) 21:29:40.49

>>197
https://mevius.5ch.net/test/read.cgi/tech/1434079972/
2625個、でしょうか？

◆QZaw55cn4c · 2019/12/09(月) 21:35:00.48

やりなおします
>>197
https://mevius.5ch.net/test/read.cgi/tech/1434079972/62
2625個

**デフォルトの名無しさん** · 2019/12/09(月) 22:42:10.29

ふるいで5000以下の素数を求めて
2重ループで列挙

が速いかな

**デフォルトの名無しさん** · 2019/12/09(月) 22:48:18.91

>>201
正解。Rでエラトステネスの篩を使って求めるプログラムを一応貼っておく。
https://ideone.com/anqKGW

**デフォルトの名無しさん** · 2019/12/10(火) 06:55:28.37

>>197 J

(smoutput~ 2=#@q:)@>>:i.10000

4
6
9
10
...
9991
9993
9995
9997
9998

**デフォルトの名無しさん** · 2019/12/10(火) 07:06:32.14

問題の一区分である素数判定、並びに範囲内の素数列挙するコード
https://ideone.com/fGT115
~/bin/is_prime.exe 2 10000
とやれば1万までの素数が列挙され、
~/bin/is_prime.exe 2017
と1つ引数与えればそれだけ判定
引数無いとURLの用にOFする限界付近まで全部

1万までの素数出して、それパイプで処理したら楽かなと思った

**デフォルトの名無しさん** · 2019/12/10(火) 08:49:47.69

5000までの素数で十分だって言ってるのに

**デフォルトの名無しさん** · 2019/12/10(火) 09:32:39.88

>>197
お題：このお題の回答を論理式で表すとどうなるでしょうか。

**デフォルトの名無しさん** · 2019/12/10(火) 09:53:12.04

>>207
それはプログラミングのお題なのか？

**デフォルトの名無しさん** · 2019/12/10(火) 13:07:12.61

また数(ry

**デフォルトの名無しさん** · 2019/12/10(火) 13:10:37.69

出題者はいろんな言語の表記方法を知りたいだけか？
数学やアルゴリズム的には全然おもしろくないのばかり

**デフォルトの名無しさん** · 2019/12/10(火) 15:09:39.15

>>197
https://ideone.com/wVVsOF
C++。>>205 の素数判定パクりました。楽すぎ。
と、思ったらこれ、俺の回答間違ってる。

**デフォルトの名無しさん** · 2019/12/10(火) 15:15:40.70

>>197
https://ideone.com/1Vax7p

C++。こうかいな。

**デフォルトの名無しさん** · 2019/12/10(火) 16:37:43.07

>>210
お前が面白い問題出せばいいじゃん
たぶん誰も解かないだろうけどwww

**デフォルトの名無しさん** · 2019/12/10(火) 17:22:00.22

過去スレからお題引っ張りたいんだけど、有料会員じゃないからむりぽ

**デフォルトの名無しさん** · 2019/12/10(火) 17:45:48.68

2chscとかいうのが無料サルベージに向いていると聞いたことがある

**デフォルトの名無しさん** · 2019/12/10(火) 17:47:09.91

>>214
普通のブラウザで見ても出ないんだっけ？

**デフォルトの名無しさん** · 2019/12/10(火) 18:57:11.15

>>213
問題を出して人に解かせるのはあまり好きじゃない
解く方が好き

**デフォルトの名無しさん** · 2019/12/10(火) 19:01:43.67

過去の良問があればおしえろください

**デフォルトの名無しさん** · 2019/12/10(火) 19:30:15.36

>>216
見れた( ﾟДﾟ)

**デフォルトの名無しさん** · 2019/12/10(火) 20:07:19.37

>>219
そうか。普通のブラウザだとエロ広告が激しく付くからそれで過去スレ見せる料金なんとかしてるのかもね。

>>217
そんなあなたにとっておきのお題をひとつ。

お題: 面白いお題を作れ。

**デフォルトの名無しさん** · 2019/12/10(火) 20:25:27.92

じゃあ四角形を全部違う大きさの円で埋める

**デフォルトの名無しさん** · 2019/12/10(火) 21:05:07.05

>>207
答えは高々有限個の整数でしかないんだから論理式にはならない

**デフォルトの名無しさん** · 2019/12/10(火) 22:54:03.68

>>210
まあ、そんな所だね。このスレは競技プログラミングじゃないから、アルゴリズムや
パフォーマンスの追求よりは、各自が使う言語で楽な書き方ができるのを披露する方が多い。
>>203も可変長ベクトルへの再代入の繰り返しという非効率なことをやっているが、
自前のforループ不要で簡潔に書けるし、篩い落とす操作を忠実に表してもいる。
昔と違ってこれでも実用な速度で動くので、色々な書き方ができるようになった。

C#, Julia, PowerShellでも類似の書き方ができる（>>206の通り素数は5000までにした）。
C#　https://ideone.com/YWc3f8
Julia　https://ideone.com/8NdOe3
PowerShell　https://ideone.com/DRoOMU
R　https://ideone.com/34lnNQ

C#のstatic void Main()の中だけを抜き出したC#スクリプトも作って、それぞれの実行時間を
PowerShellの

measure-command {semiprime.exe}
measure-command {csi semiprime.csx}
measure-command {julia semiprime.jl}
measure-command {semiprime.ps1}
measure-command {rscript semiprime.R}

で計測すると、C#を1倍として、R 3.40倍、C#スクリプト 10.1倍、Julia 16.6倍、
PowerShell 199倍となった。PowerShellだけは延々と待たされ実用的でない。
他の4つはすぐに終わるが、右へ行くほどややもたつく。Rは遅いと言われているが、
スクリプト言語の中ではかなり速い。

**デフォルトの名無しさん** · 2019/12/10(火) 22:54:55.70

>>217
じゃあ、これ解いてみる?

整数x, y, z, kに関する方程式x^3 + y^3 + z^3 = kの解を、k = 1から100までの場合について求めよ。
https://engineer.fabcross.jp/archeive/190921_charity-engine.html

**デフォルトの名無しさん** · 2019/12/10(火) 23:25:26.63

k = 64, z = 4の時
任意の整数を+-反転した組が x,yの解であり、その個数は無限

**デフォルトの名無しさん** · 2019/12/10(火) 23:27:52.24

なぜ
k=1, z=1
じゃない？

**デフォルトの名無しさん** · 2019/12/10(火) 23:47:24.77

あとから追加されそうな条件の
仮に全部0以上の整数とした時に
5*5*5>125,100>4*4*4のメモ代り

**デフォルトの名無しさん** · 2019/12/10(火) 23:59:19.26

k=1から100のどれかに対してじゃなくて、
k=1から100のそれぞれすべてに対して求めるんじゃろ…

**デフォルトの名無しさん** · 2019/12/11(水) 00:11:02.49

https://ideone.com/WP5jkx

10000000以下で0.04秒
C++は速い！

**デフォルトの名無しさん** · 2019/12/11(水) 00:13:04.91

C#の10000以下より速い！

**デフォルトの名無しさん** · 2019/12/11(水) 00:30:48.20

>>224
k=1の時からいきなり難しいなあ

**デフォルトの名無しさん** · 2019/12/11(水) 00:40:32.37

>>224
ん？
解を全て求めるのではなく
各kに対して1個解を求めればいいの？

**デフォルトの名無しさん** · 2019/12/11(水) 09:11:06.45

>>197 seq, factor, awk

seq 10000 | factor | awk 'NF == 3'

**デフォルトの名無しさん** · 2019/12/11(水) 09:24:12.51

>>233
awkのとここれどういう意味？わたし女騎士だけど教えて！

**デフォルトの名無しさん** · 2019/12/11(水) 10:31:05.38

>>234
女騎士？

まあいいや。NFが3になる行だけ出力するんだよ。NFはフィールド数ね。
区切り文字がデフォルトのままだと空白文字で区切った時の個数。例えば行に a b c って入ってたら 3 になる。

**デフォルトの名無しさん** · 2019/12/11(水) 12:05:48.97

>>197
Kotlin
https://paiza.io/projects/6zHoXJXw1KuNLWZViVDYug

**デフォルトの名無しさん** · 2019/12/11(水) 13:38:08.03

>>233
素因数分解しちゃえばいいのか
サイコー

**デフォルトの名無しさん** · 2019/12/11(水) 13:42:56.98

>>233
やってみたら
--- Data stack:
って出力が10000行並ぶだけなんだけど…
なんかオプションいる？

**デフォルトの名無しさん** · 2019/12/11(水) 14:03:27.78

普通にできたけど
何のシェル使ってるの？

**デフォルトの名無しさん** · 2019/12/11(水) 14:35:31.47

bash。macで。

**デフォルトの名無しさん** · 2019/12/11(水) 14:38:38.09

俺もbashもだけど
seq 100くらいなら動くの？

**デフォルトの名無しさん** · 2019/12/11(水) 15:36:13.32

$ seq 3 | factor で止めてawk飛ばすと以下の出力です。
Factor 0.98 x86.64 (1886, heads/master-211d69561a, Jul 2 2018 17:46:19)
[Clang (GCC 4.2.1 Compatible Apple LLVM 7.3.0 (clang-703.0.29))] on macosx
IN: scratchpad
--- Data stack:
1
IN: scratchpad
--- Data stack:
1
2
IN: scratchpad
--- Data stack:
1
2
3
IN: scratchpad

**デフォルトの名無しさん** · 2019/12/11(水) 16:49:11.52

>>233
約数が3個な数を列挙ってこと？
4の約数は1,2,4の3個だけど
6の約数は1,2,3,6の4個だよ

**デフォルトの名無しさん** · 2019/12/11(水) 17:02:16.44

factorみりゃわかんだろ……
素因数の数だっつーの

**デフォルトの名無しさん** · 2019/12/11(水) 18:01:04.84

素因数の数が3？

**デフォルトの名無しさん** · 2019/12/11(水) 18:12:47.35

こんな具合だろ
seq 100 | ~/bin/factorization.pl| awk -F, "NF==2" | ~/bin/align.pl "=" 4 2,2
6 2,3
9 3,3
10 2,5
14 2,7
......
9995 5,1999
9997 13,769
9998 2,4999

**デフォルトの名無しさん** · 2019/12/11(水) 19:33:15.23

>>224
とりあえず7個を除いて出来た
ここからが長いのかな？

◆QZaw55cn4c · 2019/12/11(水) 19:46:53.70

>>243
そうそう、それに
8 の約数は　1, 2, 4, 8 の 4 個だけれども、これは >>197 のいう半素数ではないんですよね

>>233 は間違っていますね

**デフォルトの名無しさん** · 2019/12/11(水) 20:44:53.42

QZがそういうなら合ってるんじゃないの？

**デフォルトの名無しさん** · 2019/12/11(水) 20:51:31.74

反面教師？

**デフォルトの名無しさん** · 2019/12/11(水) 20:54:12.94

お題
1兆以下の半素数の個数を求めよ

これだとスクリプト系は無理かな？

**デフォルトの名無しさん** · 2019/12/11(水) 21:07:14.36

素数判定で書いた
long long int のC言語でも100億ぐらいを上限でサポートしてる
100億以上の判定は遅くてより優れた判定アルゴリズムが必要だからだ

推定:C系、優れた判定、現代スペックのPCが必要

**デフォルトの名無しさん** · 2019/12/11(水) 21:11:52.35

素数判定する必要は無いよ

◆QZaw55cn4c · 2019/12/11(水) 22:08:07.74

>>252
＞long long int のC言語でも100億ぐらいを上限でサポートしてる

極めて不正確ですよ
C99 後は uint64_t の最大値は 1844'6744'0737'0955'1615=約 1844 京ですね
それに実際に割ってみる方法以外には素数判定があるとでも？そんなものは存在しませんね

**デフォルトの名無しさん** · 2019/12/11(水) 22:15:54.42

何年も前に素数の数を数え時は
シングルスレッドのコードで
5000億までで1時間弱

だから>>251もそのくらいで求まるはず

**デフォルトの名無しさん** · 2019/12/11(水) 22:46:17.34

>>254
詳しそうなので>>251をよろしく！

**デフォルトの名無しさん** · 2019/12/11(水) 23:52:51.14

知り合いから、「子供の宿題なんだけど解けない」と言われた。

「正方形13枚と正三角形を何枚か組み合わせて、凸多面体を作るとき、その頂点数は A 個または B 個である。ただし一つの頂点には同じ枚数の面が集まっているものとし、A < B とする。」

途中経過を適宜表記しつつ解くプログラムを!

**デフォルトの名無しさん** · 2019/12/12(木) 00:28:15.32

A=19
B=38

**デフォルトの名無しさん** · 2019/12/12(木) 00:32:27.86

>>247
3乗して64bitに収まる範囲全て調べたけど
7個から減らなかった

**デフォルトの名無しさん** · 2019/12/12(木) 00:35:14.01

7個になるまで9秒
3乗して64bitに収まる範囲検索2031秒