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

[過去ﾛｸﾞ] プログラミングのお題スレ Part16 (981ﾚｽ)
上下前次 1-新

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索歴削→次ｽﾚ栞削→次ｽﾚ過去ﾛｸﾞﾒﾆｭｰ

204: 2019/12/10(火)06:55 ID:cIwr+d9F(1) AAS
>>197 J

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

4
6
9
10
...
9991
9993
9995
省2

205(1): 2019/12/10(火)07:06 ID:qBy9puuu(1/4) AAS
問題の一区分である素数判定、並びに範囲内の素数列挙するコード
外部ﾘﾝｸ:ideone.com
~/bin/is_prime.exe 2 10000
とやれば1万までの素数が列挙され、
~/bin/is_prime.exe 2017
と1つ引数与えればそれだけ判定
引数無いとURLの用にOFする限界付近まで全部

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

206(1): 2019/12/10(火)08:49 ID:92MPgAr5(1) AAS
5000までの素数で十分だって言ってるのに

207(2): 2019/12/10(火)09:32 ID:WOcT9SPT(1) AAS
>>197
お題：このお題の回答を論理式で表すとどうなるでしょうか。

208: 2019/12/10(火)09:53 ID:gKYhlG5V(1) AAS
>>207
それはプログラミングのお題なのか？

209: 2019/12/10(火)13:07 ID:bINIS1ks(1) AAS
また数(ry

210(2): 2019/12/10(火)13:10 ID:FDwwVytW(1) AAS
出題者はいろんな言語の表記方法を知りたいだけか？
数学やアルゴリズム的には全然おもしろくないのばかり

211: 2019/12/10(火)15:09 ID:zIz8I18p(1/2) AAS
>>197
外部ﾘﾝｸ:ideone.com
C++。>>205 の素数判定パクりました。楽すぎ。
と、思ったらこれ、俺の回答間違ってる。

212: 2019/12/10(火)15:15 ID:zIz8I18p(2/2) AAS
>>197
外部ﾘﾝｸ:ideone.com

C++。こうかいな。

213(1): 2019/12/10(火)16:37 ID:hI+yeapE(1) AAS
>>210
お前が面白い問題出せばいいじゃん
たぶん誰も解かないだろうけどwww

214(1): 2019/12/10(火)17:22 ID:Ajx0JUvY(1/2) AAS
過去スレからお題引っ張りたいんだけど、有料会員じゃないからむりぽ

215: 2019/12/10(火)17:45 ID:qBy9puuu(2/4) AAS
2chscとかいうのが無料サルベージに向いていると聞いたことがある

216(1): 2019/12/10(火)17:47 ID:ClyY78bX(1/2) AAS
>>214
普通のブラウザで見ても出ないんだっけ？

217(2): 2019/12/10(火)18:57 ID:W3sLZ8lM(1/3) AAS
>>213
問題を出して人に解かせるのはあまり好きじゃない
解く方が好き

218: 2019/12/10(火)19:01 ID:W3sLZ8lM(2/3) AAS
過去の良問があればおしえろください

219(1): 2019/12/10(火)19:30 ID:Ajx0JUvY(2/2) AAS
>>216
見れた( ﾟДﾟ)

220: 2019/12/10(火)20:07 ID:ClyY78bX(2/2) AAS
>>219
そうか。普通のブラウザだとエロ広告が激しく付くからそれで過去スレ見せる料金なんとかしてるのかもね。

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

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

221: 2019/12/10(火)20:25 ID:6QYDHDQi(1) AAS
じゃあ四角形を全部違う大きさの円で埋める

222: 2019/12/10(火)21:05 ID:0RQ6ozIG(1) AAS
>>207
答えは高々有限個の整数でしかないんだから論理式にはならない

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

C#, Julia, PowerShellでも類似の書き方ができる（>>206の通り素数は5000までにした）。
C#　外部ﾘﾝｸ:ideone.com
Julia　外部ﾘﾝｸ:ideone.com
PowerShell　外部ﾘﾝｸ:ideone.com
省12

224(3): 2019/12/10(火)22:54 ID:ZImsJVBi(2/2) AAS
>>217
じゃあ、これ解いてみる?

整数x, y, z, kに関する方程式x^3 + y^3 + z^3 = kの解を、k = 1から100までの場合について求めよ。
外部ﾘﾝｸ[html]:engineer.fabcross.jp

225: 2019/12/10(火)23:25 ID:qBy9puuu(3/4) AAS
k = 64, z = 4の時
任意の整数を+-反転した組が x,yの解であり、その個数は無限

226: 2019/12/10(火)23:27 ID:W3sLZ8lM(3/3) AAS
なぜ
k=1, z=1
じゃない？

227: 2019/12/10(火)23:47 ID:qBy9puuu(4/4) AAS
あとから追加されそうな条件の
仮に全部0以上の整数とした時に
5*5*5>125,100 >4*4*4のメモ代り

228: 2019/12/10(火)23:59 ID:RjwvfByt(1) AAS
k=1から100のどれかに対してじゃなくて、
k=1から100のそれぞれすべてに対して求めるんじゃろ…

229: 2019/12/11(水)00:11 ID:10jfhd7e(1/7) AAS
外部ﾘﾝｸ:ideone.com

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

230: 2019/12/11(水)00:13 ID:10jfhd7e(2/7) AAS
C#の10000以下より速い！

231: 2019/12/11(水)00:30 ID:10jfhd7e(3/7) AAS
>>224
k=1の時からいきなり難しいなあ

232: 2019/12/11(水)00:40 ID:10jfhd7e(4/7) AAS
>>224
ん？
解を全て求めるのではなく
各kに対して1個解を求めればいいの？

233(5): 2019/12/11(水)09:11 ID:aadkbL3F(1) AAS
>>197 seq, factor, awk

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

234(1): 2019/12/11(水)09:24 ID:ztpKOEip(1) AAS
>>233
awkのとここれどういう意味？わたし女騎士だけど教えて！

235: 2019/12/11(水)10:31 ID:dG8VWZ74(1/2) AAS
>>234
女騎士？

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

236: 2019/12/11(水)12:05 ID:dG8VWZ74(2/2) AAS
>>197
Kotlin
外部ﾘﾝｸ:paiza.io

237: 2019/12/11(水)13:38 ID:ivhCTlPt(1/3) AAS
>>233
素因数分解しちゃえばいいのか
サイコー

238: 2019/12/11(水)13:42 ID:QbvBtpFM(1/3) AAS
>>233
やってみたら
--- Data stack:
って出力が10000行並ぶだけなんだけど…
なんかオプションいる？

239: 2019/12/11(水)14:03 ID:jagg9gKF(1/2) AAS
普通にできたけど
何のシェル使ってるの？

240: 2019/12/11(水)14:35 ID:QbvBtpFM(2/3) AAS
bash。macで。

241: 2019/12/11(水)14:38 ID:jagg9gKF(2/2) AAS
俺もbashもだけど
seq 100くらいなら動くの？

242: 2019/12/11(水)15:36 ID:QbvBtpFM(3/3) AAS
$ 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
省6

243(1): 2019/12/11(水)16:49 ID:1E1+DBtw(1) AAS
>>233
約数が3個な数を列挙ってこと？
4の約数は1,2,4の3個だけど
6の約数は1,2,3,6の4個だよ

244: 2019/12/11(水)17:02 ID:hUZCfnLs(1) AAS
factorみりゃわかんだろ……
素因数の数だっつーの

245: 2019/12/11(水)18:01 ID:10jfhd7e(5/7) AAS
素因数の数が3？

246: 2019/12/11(水)18:12 ID:ivhCTlPt(2/3) AAS
こんな具合だろ
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

247(1): 2019/12/11(水)19:33 ID:ReYSFEXH(1) AAS
>>224
とりあえず7個を除いて出来た
ここからが長いのかな？

248: ◆QZaw55cn4c 2019/12/11(水)19:46 ID:6E3wj7zP(1/2) AAS
>>243
そうそう、それに
8 の約数は　1, 2, 4, 8 の 4 個だけれども、これは >>197 のいう半素数ではないんですよね

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

249: 2019/12/11(水)20:44 ID:WjX/lCwK(1) AAS
QZがそういうなら合ってるんじゃないの？

250: 2019/12/11(水)20:51 ID:7CYZ1E2N(1/3) AAS
反面教師？

251(2): 2019/12/11(水)20:54 ID:7CYZ1E2N(2/3) AAS
お題
1兆以下の半素数の個数を求めよ

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

252(2): 2019/12/11(水)21:07 ID:ivhCTlPt(3/3) AAS
素数判定で書いた
long long int のC言語でも100億ぐらいを上限でサポートしてる
100億以上の判定は遅くてより優れた判定アルゴリズムが必要だからだ

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

253: 2019/12/11(水)21:11 ID:7CYZ1E2N(3/3) AAS
素数判定する必要は無いよ

254(5): ◆QZaw55cn4c 2019/12/11(水)22:08 ID:6E3wj7zP(2/2) AAS
>>252
＞long long int のC言語でも100億ぐらいを上限でサポートしてる

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

255: 2019/12/11(水)22:15 ID:10jfhd7e(6/7) AAS
何年も前に素数の数を数え時は
シングルスレッドのコードで
5000億までで1時間弱

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

256(1): 2019/12/11(水)22:46 ID:10jfhd7e(7/7) AAS
>>254
詳しそうなので>>251をよろしく！

257(1): 2019/12/11(水)23:52 ID:VagVWTF0(1) AAS
知り合いから、「子供の宿題なんだけど解けない」と言われた。

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

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

258: 2019/12/12(木)00:28 ID:UvCIGzud(1/13) AAS
A=19
B=38

259: 2019/12/12(木)00:32 ID:UvCIGzud(2/13) AAS
>>247
3乗して64bitに収まる範囲全て調べたけど
7個から減らなかった

260: 2019/12/12(木)00:35 ID:UvCIGzud(3/13) AAS
7個になるまで9秒
3乗して64bitに収まる範囲検索2031秒

261: 2019/12/12(木)00:42 ID:UvCIGzud(4/13) AAS
>>257
プログラミングの宿題じゃないはずなので
解き方は他の板で聞いて

262: 2019/12/12(木)00:44 ID:UvCIGzud(5/13) AAS
k=30, 33, 42, 52, 74, 75, 84
の時がわからん

263(4): 2019/12/12(木)06:06 ID:wmbGd8tm(1/3) AAS
>>254
f(x) = 1 if x is prime
f(x) = 0 otherwise
なる f: R -> R が存在しないってなんで言い切れんの？
頭悪すぎ

264: 2019/12/12(木)07:32 ID:UvCIGzud(6/13) AAS
>>254も>>263も頭悪すぎだ

265(2): 2019/12/12(木)07:40 ID:UvCIGzud(7/13) AAS
>>252
素数判定は不要

>>254
uint64_tの上限じゃなくて素数判定可能な範囲
また、実際に割ってみる以外の方法も色々と存在する

>>263
fは存在する
あなたが書いた通りの定義そのままをfとすれば良い
fの存在と素数判定の方法が存在するかどうかは無関係

266(1): 2019/12/12(木)07:48 ID:wmbGd8tm(2/3) AAS
>>265
お前も馬鹿だな
簡単な関数で f が定義できるならそれはそのまま簡単な計算で素数判定ができることに他ならない
こちらはそんな方法が存在するといっているわけではなく、無配慮にそんなものは存在しないと一刀両断する数学的リテラシーの無さを指摘しているだけなんだが

267: 2019/12/12(木)08:00 ID:UvCIGzud(8/13) AAS
>>263
｢簡単な関数でfが定義できる｣
非常に重要な言葉を後付けだし
これが最初からあったとしても、
単に簡単に素数判定可能可能を言い換えただけの
何の意味もないレス

リテラシーの無さの指摘の方法が頭が悪い

268: 2019/12/12(木)08:08 ID:UvCIGzud(9/13) AAS
現代の技術で言えば

特殊な形であれば高速に判定する方法はある
特殊な形でなければ高速に判定する方法は見つかっていない
実際に割ってみる以外の判別方法は存在する

269: 2019/12/12(木)08:25 ID:UvCIGzud(10/13) AAS
なんでNやZじゃなくてRにしたのか気になる

270: 2019/12/12(木)12:56 ID:wmbGd8tm(3/3) AAS
文脈無視して揚げ足取ってて草
こいつ関数は全射しか存在しないとでも思ってんのか

271: 2019/12/12(木)14:55 ID:2PtCb74v(1) AAS
単純な疑問だよ
なんかこだわりとか深い意味とかあるのかと

｢実数が素である｣とか書かれると、
素数じゃない別の意味を指してると思うわけで

揚げ足取られたと思ったってことは
ミスったと思ったんだよね？

272: 2019/12/12(木)15:35 ID:zRSUYply(1) AAS
いつもの連投アスペ君じゃん
相手すんなよ

273: 2019/12/12(木)17:58 ID:2C/x7O5N(1) AAS
論破されて捨て台詞
の典型でした

274: 2019/12/12(木)18:19 ID:RcQND7/k(1) AAS
5chリテラシーが低いやつもだいぶ減ってはきてるが
このスレはちょいちょい出てくるよなぁ

275: 2019/12/12(木)18:27 ID:cffvEFbc(1/3) AAS
>>263を書いておいて良くいうよ

276: [age] 2019/12/12(木)18:39 ID:JPTMcftT(1) AAS
論破を禁止します

277: 2019/12/12(木)19:05 ID:f2lx0DlC(1) AAS
まーたロンパンジーが湧いてんのかよ

278: 2019/12/12(木)19:12 ID:cffvEFbc(2/3) AAS
リテラシー君
よほど悔しかったのかな？

279(1): ◆QZaw55cn4c 2019/12/12(木)19:15 ID:bwSkQtN1(1/2) AAS
>>256
単に上限値を増やしただけのお題なんて糞だと思います

280: ◆QZaw55cn4c 2019/12/12(木)19:17 ID:bwSkQtN1(2/2) AAS
>>265
＞また、実際に割ってみる以外の方法も色々と存在する
私の初等的な教科書にはウィルソンの定理の証明が載っていました、>>254 はちょっと勇み足でしたね

>>266
＞無配慮にそんなものは存在しないと一刀両断する数学的リテラシーの無さ
まあ、認めましょう

281: 2019/12/12(木)19:18 ID:cffvEFbc(3/3) AAS
>>279
そう思うってことは上限値以外の差がわからんて事だね
決定的な違いがある

282(1): 2019/12/12(木)20:55 ID:uIjgN9ep(1) AAS
お題：

(A) 階乗の下z桁がすべて0となるような最小の自然数を、z = 1, 12, 123, 1234, 12345,
123456, 1234567, 12345678, 123456789の各場合について求めよ。存在しないときは
そう表示せよ。

(B) (A)の「下z桁がすべて0となる」という条件を「0である桁がz個となる」に置き換えて解け。

(A)はちょっと考えれば簡単に解ける。(B)はどうか知らない。多桁整数計算ができるJuliaでは
z = 12345までは力任せでも求められたが。

283(1): 2019/12/12(木)21:21 ID:qa03h3dy(1) AAS
5で割っていく感じだから
整数無視して無限に割ると
おおまかに4で割った感じの数0が並ぶ
126！は4で割って31ぐらい

284: 2019/12/12(木)22:14 ID:WrPVO4K2(1) AAS
連投論破野郎が論破されてて草

285(1): 2019/12/12(木)23:15 ID:UvCIGzud(11/13) AAS
(A)だけ C++
外部ﾘﾝｸ:ideone.com

286: 2019/12/12(木)23:18 ID:UvCIGzud(12/13) AAS
(B)は実際に下限から順番に計算していかないとダメじゃないか？

287(3): 2019/12/12(木)23:52 ID:UvCIGzud(13/13) AAS
n ! のゼロの個数は大雑把にはこのくらい
log_10(n !) / 10 + n * 9 / 40

逆算すれば大体の値はわかる
でも最小値だから正確に求めるのには使えない

288(1): 2019/12/13(金)18:36 ID:0Lb/VhZx(1) AAS
[お題]
今月(2019/12)の13日は金曜日。
開始年月と終了年月が与えられる。年は西暦、年月区切りは"/"。
開始年月一日から終了年月末日の間で"13日の金曜日"は何回あるか。
現在のグレゴリオ歴ルールで、終了年月末日まで変わらないとする。

制約: 1970 <= 年 <= 300億, 1 <= 月 <= 12, 開始年月 <= 終了年月

1)　2019/1 2019/12 --> 2　　 // 今年は9月と12月が該当
2)　1980/1 2012/12 --> 57
3)　213456/8 453212/4 --> 412380
4)　2000/1 2399/12 -->?
省5

289(1): 2019/12/13(金)20:06 ID:KAf60mjk(1) AAS
300億にしても年の曜日は14パターンしか無いのであっという間に解ける気が…
曜日は400年周期だから400年分求めればあとは割り算するだけかな？

290: 2019/12/13(金)20:15 ID:QuzLYYNu(1/10) AAS
C++
外部ﾘﾝｸ:ideone.com

291: 2019/12/13(金)20:16 ID:QuzLYYNu(2/10) AAS
>>289
今日やらないとダメだよ

292: 2019/12/13(金)20:32 ID:7JZ8Vcg3(1/2) AAS
>>288
ずるいやり方だが、取り敢えずPowerShellに
　1..12 |? {([DateTime]"2000/$_/13").DayOfWeek -eq "Friday"}
　1..12 |? {([DateTime]"2400/$_/13").DayOfWeek -eq "Friday"}
と打ち込んでみると、
　10
　10
と表示され、2000年と2400年の13日の金曜日は10月で一致する。
これと閏年調整のパターンが400年周期であることを組み合わせると、
13日の金曜日の出現パターンも400年周期になることが分かる。
省10

293(1): 2019/12/13(金)20:57 ID:7JZ8Vcg3(2/2) AAS
>>285
正解。例によってRで簡潔に書いた解答例: 外部ﾘﾝｸ:ideone.com

>>287
やっぱり無理か。ちなみに、Juliaでz = 12345まで力任せで求めるプログラム
外部ﾘﾝｸ:ideone.com

--- 実行結果 ---
階乗の0である桁が1個になる最小値は5です。
階乗の0である桁が12個になる最小値は37です。
階乗の0である桁が123個になる最小値は299です。
階乗の0である桁が1234個になる最小値は2414です。
省1

294: 2019/12/13(金)21:27 ID:QuzLYYNu(3/10) AAS
>>293

>>287の式に20177を入れると12349.7
かなりいい線行ってる

295(1): 2019/12/13(金)22:22 ID:QuzLYYNu(4/10) AAS
123456個は存在しない

296(1): 2019/12/13(金)23:21 ID:QuzLYYNu(5/10) AAS
123457桁になる 30484!
から
下位に0が123457個続く 493840!
までの間に存在しない事を示せば
存在しない証明になりますが
もっと範囲を絞った証明は出来ないですかねえ

確率的には>>287の付近だけ調べれば良いんですが...

297: 2019/12/13(金)23:47 ID:r78PztnN(1) AAS
全部調べる感じでぶん回してるけど1234567までが長いお(´・ω・`)　(123456は>>295の言う通り出なかった)
1時間ぶん回して900000!まで行ったが…

298: 2019/12/13(金)23:49 ID:r2S5lo/C(1/2) AAS
数学でワープできる分手計算のほうが早い

299: 2019/12/13(金)23:49 ID:QuzLYYNu(6/10) AAS
kwsk

300: 2019/12/13(金)23:50 ID:r2S5lo/C(2/2) AAS
>283

301: 2019/12/13(金)23:52 ID:QuzLYYNu(7/10) AAS
(A)は解決済み
(B)の話

302: 2019/12/13(金)23:53 ID:QuzLYYNu(8/10) AAS
数学で絞れるのは>>296くらいかと

303: 2019/12/13(金)23:56 ID:QuzLYYNu(9/10) AAS
下限の n! を計算するのは速い
そこから順番に1個ずつnを増やしていって
0を数えていかないとならない

見つからなければ上限までずっと

上下前次 1-新書関写板覧索設栞歴

あと 678 ﾚｽあります
ｽﾚ情報赤ﾚｽ抽出画像ﾚｽ抽出歴の未読ｽﾚ AAｻﾑﾈｲﾙ

ぬこの手ぬこTOP 0.025s