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

**デフォルトの名無しさん** · 2018/01/01(月) 11:15:04.40

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

前スレ
プログラミングのお題スレ Part9
https://mevius.5ch.net/test/read.cgi/tech/1480579110/

【出題と回答例】
1 名前：デフォルトの名無しさん
　　お題：お題本文

2 名前：デフォルトの名無しさん
　　>>1 使用言語
　　回答本文

【ソースコードが長くなったら】 (オンラインでコードを実行できる)
http://ideone.com/
http://codepad.org/
http://compileonline.com/
http://rextester.com/runcode
http://runnable.com/
http://code.hackerearth.com/
http://melpon.org/wandbox
https://paiza.io/

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

**デフォルトの名無しさん** · 2018/03/13(火) 04:39:43.81

>>380
すごい48文字でできたんだ
恐れ入りました
ちなみにforの条件のa>1はaでも大丈夫だから46文字になるね

**デフォルトの名無しさん** · 2018/03/13(火) 05:18:44.02

括弧や%のShiftキー分で死ぬんじゃない？ｗ

**デフォルトの名無しさん** · 2018/03/13(火) 05:36:35.30

>>382
するどい！死んだわｗ

**デフォルトの名無しさん** · 2018/03/13(火) 06:07:28.04

>>381
＞ちなみにforの条件のa>1はaでも大丈夫だから46文字になるね

終了しないことを許容することによる短縮か…

**デフォルトの名無しさん** · 2018/03/13(火) 06:08:19.20

いや、終了しなくていいなら ;a>1; は ;; で ok か

**デフォルトの名無しさん** · 2018/03/13(火) 06:11:22.12

>>384
ごめんそれは今俺も気づいてこれダメじゃんと思ってた
もうだめだ俺ポンコツだ

**デフォルトの名無しさん** · 2018/03/13(火) 09:31:38.72

お前のお題つまんない二度とくんな

**デフォルトの名無しさん** · 2018/03/13(火) 12:46:32.28

#include<stdio.h>

int main(void){
int i=0;
int a=720;/*任意の値*/

for(i=2;a>1;printf("%d\n",i),a/=i)for(;犯人はヤス・・・

return 0;
}

**デフォルトの名無しさん** · 2018/03/13(火) 13:13:00.94

お題：考えられる数列aを全て求め、出力せよ
ただし、数列aは次の式を満たす(Nは自然数全体)
a⊆N
∀i,j∈N,i<j;a_i<a_j
log(Σa_i)=Σlog(a_i)
∀i;1≦a_i≦10^18

◆QZaw55cn4c · 2018/03/13(火) 13:27:27.25

>>389
1, 2, 3
くらいですかね、これを計算で出すのはしんどいなあ

**デフォルトの名無しさん** · 2018/03/13(火) 13:29:32.40

log(ab)=log(a)+log(b)だからログ関係なくナイカ?

a1<a2<・・・・<anで、Σai =Πaiを満たすってことだろ。

**デフォルトの名無しさん** · 2018/03/13(火) 14:19:23.53

まず{a_n}が上に有界な時点で∀i , j ∈ N i < j; a_i < a_j が成り立たないから問題として破綻している

**デフォルトの名無しさん** · 2018/03/13(火) 14:19:24.28

a+b+c = abcならば、c = (a+b)/(ab-1)だから、これが整数になるようなやつ見つければいいかと。
たとえば(2+3)/(2*3-1) = 1。

**デフォルトの名無しさん** · 2018/03/13(火) 14:21:35.93

それは増加数列を言いたかったんじゃないか。　a1<a2<・・・・<an
∀i , j 　i<j ならばai < ajでは?

**デフォルトの名無しさん** · 2018/03/13(火) 14:45:44.02

4変数のときを考えると。
上と同様に、d = (a+b+c)/(abc-1)となるから。
これは分母のほうがデカイはずで、分子を割り切るならd=1に限るか?
そうすると、abc = 1 + a+b+c　か。
aについて解くと、a = ( 1 + b + c) /( bc - 1 ) か。
これが再び1ではダメで、しかし分母のほうがデカイはずだから割り切るならa=2に限るか?
2bc - 2 = 1 + b + c　か。
bについて解くと、b = (3 + c)/(2c-1)か。c=4ならば、b=1になるが?

**デフォルトの名無しさん** · 2018/03/13(火) 14:56:18.86

一応、数列は全部で7個になるはず
8個目はa_61が1152921504069976064>1.15×10^18で上限だから
数列の並び方は>>394でお願い、任意の並び方にしちゃうと組み合わせ爆発が発生するかなって思って付けた制約なので

**デフォルトの名無しさん** · 2018/03/13(火) 14:59:51.72

ん？

n
ΠAi = ΣAi < n An
i=1

An で割って

n-1
Π Ai < n
i=1

で左辺は (n-1)! 以上だから n はたかだか 3 じゃない？

**デフォルトの名無しさん** · 2018/03/13(火) 15:02:02.69

……あ、やっべ
これお題として成立していないことに気付いた

**デフォルトの名無しさん** · 2018/03/13(火) 15:04:01.62

ごめんなさい、このお題は無しで
完全数の導出問題のつもりだったけど、aの要素を1個にするだけで10^18通りの解がある
twitterで流れてきた話を投げるべきではないな……反省して暫くお題出さないです

**デフォルトの名無しさん** · 2018/03/13(火) 15:07:29.90

>>394
それなら解はaの位数が１か、a = {1, 2, 3} のみだね
ってプログラミングで解く問題でもないと思うんだけど

**デフォルトの名無しさん** · 2018/03/13(火) 18:03:31.33

1,2,4,7,14
1,2,4,8,16,31,62,124,248
など

**デフォルトの名無しさん** · 2018/03/13(火) 18:25:02.81

お父さんそれは違う問題の答えでしょ

**デフォルトの名無しさん** · 2018/03/13(火) 18:39:09.17

何の話をしているのかサッパリわからんのだが、どうやら終わったようなのでまあいいか。

**デフォルトの名無しさん** · 2018/03/14(水) 00:28:33.06

出題者が出題内容を理解してなさそうだからサッパリわからない人がいても当然

**デフォルトの名無しさん** · 2018/03/17(土) 13:11:23.04

お題
任意の実数の総有効桁数を2にせよ
丸め方法は問わない
R
https://ideone.com/cpLlLw

**デフォルトの名無しさん** · 2018/03/17(土) 15:16:51.53

>>405 Ruby

[12345,
12.34,
1.234,
0.0123].each{|i|puts"%.1e"%i}
#=>
1.2e+04
1.2e+01
1.2e+00
1.2e-02

**デフォルトの名無しさん** · 2018/03/17(土) 19:33:28.44

>>405
>>406とほぼ同じ。perlでコマンドラインからそのまま実行。

$ perl -e 'for(12345,12.34,1.234,.0123){printf("%.1e\n",$_)}'
1.2e+04
1.2e+01
1.2e+00
1.2e-02
$

printf()の%e使わないで自分で何とかするやつ作った方が良いかな?

**デフォルトの名無しさん** · 2018/03/17(土) 21:20:46.09

>>405 Ruby sprintfフォーマット使わない場合

[12345,
12.34,
1.234,
0.0123].each{|i|p i.floor(1-Math.log10(i).floor)}
#=>
12000
12
1.2
0.012

**デフォルトの名無しさん** · 2018/03/18(日) 03:14:20.76

解答としては>>408を推す
他は文字列化しただけで実数を変換できてない

**デフォルトの名無しさん** · 2018/03/18(日) 04:27:15.50

>>405
Kotlin
https://paiza.io/projects/5jjVrOJVlXeQrkvnsmBNNg

**デフォルトの名無しさん** · 2018/03/18(日) 11:47:23.87

任意のx > 0 に対して x を有効桁数n(n ∈ N)で表わした数 c は
r = 10^([log10(x)] - n + 1)
とおくと
c = [x / r] * r
なんだけど、これを丸め誤差を考慮して簡単に解析的に修正するのはちょっと骨が折れるね

**デフォルトの名無しさん** · 2018/03/18(日) 12:55:07.22

それ既に>>408でほぼ既出

**デフォルトの名無しさん** · 2018/03/22(木) 18:13:48.94

まずは大学入試以前に、中学高校の入試問題や公務員試験などを人工知能で解かせたい。
そして現在の人工知能に何が出来て何が出来ないのかを知りたい。

新井紀子教授のAIやコンピュータに関する知識は素人に毛が生えた程度
新井紀子教授の『AI vs. 教科書が読めない子どもたち』という本が大変売れているようです。
私も本を購入し精読させていただきました。
一言で感想を言うと、新井紀子教授のAI技術に関する知識はせいぜいAI関連ニュースに詳しい人レベルであり、
そのベースであるコンピュータに関する知識もほぼ素人だということがわかりました。
https://mywarstory.tokyo/inconvenient-truth/

↑
人工知能の先生方がこんなんでは、どこで誰に学んだらいいのかわからない！

**デフォルトの名無しさん** · 2018/03/22(木) 18:58:31.89

批判に対して女性差別だと返してるところが何だかなあって感じ。
男だったらそもそも人目に触れるポジションにさえ来れていないだろうから、確かに批判はされないんだろうけど。

**デフォルトの名無しさん** · 2018/03/22(木) 19:36:56.32

日本はアセンブラの国。

**デフォルトの名無しさん** · 2018/03/22(木) 20:23:41.20

【史上初】　　　テレパシーで演説　　　≪≪マイトＬーヤ≫≫　　　月面ウサギを公表　　　【ＵＦＯ】
http://rosie.5ch.net/test/read.cgi/liveplus/1521681235/l50

**デフォルトの名無しさん** · 2018/03/23(金) 17:24:50.97

日本の国、まさにPC-98を中心としているアセンブラの国であるぞということを国民の皆さんにしっかりと承知をして戴く

**デフォルトの名無しさん** · 2018/03/24(土) 18:48:50.24

いいからさっさとお題出せよ

**デフォルトの名無しさん** · 2018/03/25(日) 10:48:10.09

日本語の単語がひらがなで与えられる。
これらを用いてしりとりをしたときに最も長く続くケースで使われる単語の数を出力せよ。
ただし；
・一行目は与えられる単語の数(1以上100000以下)
・「ん」から始まる単語はない
・「ゐゑぁぃぅぇぉゃゅょゎー」を含む単語はない

*sample input*
10
あなご
いくら
うなぎ
えい
おくら
かしゆうなつつ
ごはん
ばたあ
ゆば
らあゆ

*sample output*
7
(えいいくららあゆゆばばたああなごごはん)

**デフォルトの名無しさん** · 2018/03/25(日) 12:27:22.28

よく分かんないんだけど巡回セールスマン問題？

**デフォルトの名無しさん** · 2018/03/25(日) 12:34:50.41

ウィキってみたら同じNP困難問題ではあるけどナップサック問題に近いのかな？

**デフォルトの名無しさん** · 2018/03/25(日) 12:58:44.89

動的計画法？？？
なんかめんどいからオナニーでもしよっと

**デフォルトの名無しさん** · 2018/03/25(日) 13:04:27.26

俺もしりとりのお題出そうと思って色々考えた挙句止めたんだよな。何で止めたんだっけかなあ？
まあいいか。

**デフォルトの名無しさん** · 2018/03/25(日) 14:59:33.86

あなご　ごりら　らあゆ　ゆば　ばばあ　あなご
とか永久に続いちゃう場合は？

**デフォルトの名無しさん** · 2018/03/25(日) 15:13:47.39

一度使った単語は、使わないようにすれば？

**デフォルトの名無しさん** · 2018/03/25(日) 15:13:49.64

>>424
同じ単語は高々1回しか使えないということで

**デフォルトの名無しさん** · 2018/03/25(日) 15:24:25.42

>>424
しりとりのルールも知らないのか

**デフォルトの名無しさん** · 2018/03/25(日) 15:59:34.89

input
6
けんばんはーもにか
かみのけ
もうないでしよ
あるよ
けっこんしよう
うん

output
？

**デフォルトの名無しさん** · 2018/03/25(日) 18:50:35.30

>>428
けんばんはーもにか　→　かみのけ　→　けっこんしよう　→　うん
以外に考えられるの？

**デフォルトの名無しさん** · 2018/03/25(日) 20:17:28.76

>>429
///

**デフォルトの名無しさん** · 2018/03/25(日) 20:41:22.44

>>429
「足し算のプログラムを書け、入力は3と4」
という問いに「7しかないでしょ」と答えてるようなもんだぞそれ

**デフォルトの名無しさん** · 2018/03/25(日) 20:51:42.25

アウトプットは赤ちゃんでした

**デフォルトの名無しさん** · 2018/03/25(日) 21:23:06.15

>>431
いや>>428は問題の不備を指摘してるように見えたんだけど違うの
違うならなんなの？

**デフォルトの名無しさん** · 2018/03/25(日) 21:33:15.53

すまんすまんよく読んでなかった

どんな不備？
outputは4で良さそうに思えるが

**デフォルトの名無しさん** · 2018/03/25(日) 21:55:06.19

>>428
・「ゐゑぁぃぅぇぉゃゅょゎー」を含む単語はない
>けんばんはーもにか
'ー'

'を' とか 'う゛'(Unicodeでは1文字) は含むんだろうか？
濁音・半濁音の扱いもローカルルールがあるようだけど？

**デフォルトの名無しさん** · 2018/03/25(日) 22:52:38.78

>>419
Kotlin
https://paiza.io/projects/3JlXbCwKoxeWq4adKPrlaw

**デフォルトの名無しさん** · 2018/03/25(日) 22:56:05.59

>>428

>>436のプログラムでこうなった。

入力
単語数: 6
けんばんはーもにか
かみのけ
もうないでしよ
あるよ
けっこんしよう
うん

出力
単語数: 4
けんばんはーもにか
かみのけ
けっこんしよう
うん

**デフォルトの名無しさん** · 2018/03/25(日) 22:58:48.24

なるほど
お題としては数字とかアルファベットのが見通しがいいな

**デフォルトの名無しさん** · 2018/03/26(月) 20:54:56.37

プログラマ名乗っていい？

◆QZaw55cn4c · 2018/03/26(月) 20:56:27.32

>>439
どうぞ：－）

**デフォルトの名無しさん** · 2018/03/26(月) 21:54:41.90

>>419
https://ideone.com/TCBMbc
C++。サンプルは解けたが相変わらず日本語表示には厳しいな。
こんな感じでいい？

**デフォルトの名無しさん** · 2018/03/26(月) 22:45:31.40

そういえば、必ず”ん”で終わらなければならないっていう制約はないよね。
言葉が尽きても負けなんだし。

**デフォルトの名無しさん** · 2018/03/27(火) 01:45:16.06

すげぇ
しりとりは普通に組むとオーダーが大きくなるからなぁ
お題の単語数10^5に対応するプログラム書ける気がしない
辺は少ないし、これ最大流で解けるんだっけ？

**デフォルトの名無しさん** · 2018/03/27(火) 02:13:31.11

あんまり、オーダー爆発起こすとちょっと大変だな。
次に続く単語数の数が多いほど爆発する。
最大N!だけど、そういうケースは少ないよ。

**デフォルトの名無しさん** · 2018/03/27(火) 03:46:37.52

最適化閃いたけど、無理筋やった。
3変数ごにょごにょするだけで枝切できるかと思ったんだけど。

**デフォルトの名無しさん** · 2018/03/27(火) 05:36:02.02

再帰使わない解を見たいな

**デフォルトの名無しさん** · 2018/03/27(火) 07:06:00.62

>>419
https://ideone.com/LYz9cE
ひらがなは 7bit程度で表せるので、頭と尻だけ数値化、頭でテーブルを分けた。

**デフォルトの名無しさん** · 2018/03/27(火) 07:10:55.86

>>446
スタックを展開するだけだからなぁ。
めんどくさいけど、理論は楽。

**デフォルトの名無しさん** · 2018/03/27(火) 12:16:29.94

https://ideone.com/29wlkp
全探査しなくてもいいので、同じ階層に'あかい','あおい','あさい'など頭と尻が同じ語は枝刈り出来る。

**デフォルトの名無しさん** · 2018/03/27(火) 15:10:13.58

>>444
＞最大N!だけど、そういうケースは少ないよ。

可能な末尾の文字の種類をRとすると次の語を選ぶ選び方は(先頭は与えられているので)末尾違いの高々R
(中間が異なるものからはどれを選んでもいいので先頭のを選べばいい)

先頭の文字別にリストにでも格納しておけば N 単語での計算量は高々 O(N ^ R)

**デフォルトの名無しさん** · 2018/03/30(金) 08:34:52.77

お題
桁の並びが大きい順になっている数をすべてもとめる

**デフォルトの名無しさん** · 2018/03/30(金) 08:35:45.83

意味不明。

**デフォルトの名無しさん** · 2018/03/30(金) 08:51:48.50

9876543210の各桁を表示する・しない、で2^10-1(=1023)通りってことかの？

**デフォルトの名無しさん** · 2018/03/30(金) 08:58:40.80

>>451 Ruby

(1..10).each{|i| puts [*0..9].reverse.combination(i).map(&:join)}

**デフォルトの名無しさん** · 2018/03/30(金) 09:14:47.35

あーそういうことか

**デフォルトの名無しさん** · 2018/03/30(金) 09:39:19.40

rubyがわからないのでわからん
どういうこと？
今スマホでアクセスしてるから試すのもできない

**デフォルトの名無しさん** · 2018/03/30(金) 09:42:37.75

すまほでもコピペしてideoneで試せるんじゃね？
https://ideone.com/ihH1LH

**デフォルトの名無しさん** · 2018/03/30(金) 09:51:09.95

>>457
おお。動いた。
あー。そういう意味か。

**デフォルトの名無しさん** · 2018/03/30(金) 20:28:56.47

お題： n!の末尾の0の個数を数える
たとえば、n = 9のとき9! = 362880なので末尾の0の個数は1
n = 10 のとき 10! = 3628800なので末尾の0の個数は2
制限事項：　gmpなどのライブラリは使用不可。以下の5問を合計1.8秒以内で。

n = 132 , # = ?
n = 743 , # = ?
n = 54321 , # = ?
n = 2147483647 , # = ?
n = 4294967296 , # = ?

**デフォルトの名無しさん** · 2018/03/30(金) 20:39:11.33

>>459 Ruby 0.015秒くらい

[132, 743, 54321, 2147483647, 4294967296].each{|n| puts "n = %d => #%d" % [n, (1..log(n, 5)).map{|i| n / 5**i}.sum]}

# output
n = 132 => #32
n = 743 => #183
n = 54321 => #13576
n = 2147483647 => #536870902
n = 4294967296 => #1073741816

◆QZaw55cn4c · 2018/03/30(金) 21:43:34.36

>>459
https://ideone.com/sSfH5w

＞以下の5問を合計1.8秒以内で。
は未達成、これは難しい‥‥

**デフォルトの名無しさん** · 2018/03/30(金) 21:47:51.34

面白いね

何かお題が出て(>>451)それに対して意味不明の即答’>>452)、
まぁそれはそれでごもっともと思ったらrubyのコード(>>454)が出て、
その後はあーだこーだとレスが続いてく

前スレから見始めた初心者だけど、
未知の課題に対するコーディング能力ってやっぱり大事だ

◆QZaw55cn4c · 2018/03/30(金) 21:49:03.26

>>460
なるほどねえ

**デフォルトの名無しさん** · 2018/03/31(土) 04:32:05.81

>>451
https://ideone.com/SLwoYB
https://ideone451.com/AGDBWO
C++。普通に解いたら20秒くらいかかるからさらに脳筋な方法で解こうと思ったらメモリ足りなかった。
とはいえ階乗では解きたくないし。まぁいいか。

**デフォルトの名無しさん** · 2018/03/31(土) 05:34:00.26

省メモリで解こうと思ったらGCCに匙投げられた。
コンパイルタイムはこれからやな。
https://ideone.com/CScvWR

**デフォルトの名無しさん** · 2018/03/31(土) 05:44:58.45

ruby のを J に移植してみた

入力
(2,#d)$d,>(3 : '+/<.y%5^1+i.<.5^.y') each d=.132 743 54321 2147483647 4294967296

結果
+--+---+-----+---------+----------+
|32|183|13576|536870902|1073741816|
+--+---+-----+---------+----------+

5を数える他の有力なやり方ってどんなだろう

**デフォルトの名無しさん** · 2018/03/31(土) 05:45:55.95

コピペミス
結果は
132 743 54321 2147483647 4294967296
32 183 13576 536870902 1073741816

が正しかった (どうでもいいか)

**デフォルトの名無しさん** · 2018/03/31(土) 05:48:43.09

ちなみに頭の(2,#d)$d,>がないと>>466の出力となる

**デフォルトの名無しさん** · 2018/03/31(土) 05:56:26.94

int count(unsigned int n){
int sum=0;
while(n){
n/=5;
sum+=n;
}
return sum;
}

この関数を５個の整数値に対して実行するのに
1.8秒以上かかるのかよｗ
（アセンブラでやる限り）8bitマイコンでもそこまで
かからない希ガスｗ

**デフォルトの名無しさん** · 2018/03/31(土) 05:58:47.42

それただのlog5

**デフォルトの名無しさん** · 2018/03/31(土) 06:00:14.81

違うかn足してるからいいのか

**デフォルトの名無しさん** · 2018/03/31(土) 18:37:28.47

俺の頭ではいまだにやり方がわからない。
既に1.8日を超えたような気がする。

**デフォルトの名無しさん** · 2018/03/31(土) 21:03:57.21

n!を素因数分解した時の5の指数が求める数だから
Σ{k∈N}[n/5^k] を計算すればいいだけ

**デフォルトの名無しさん** · 2018/03/31(土) 23:35:26.94

>>473
意味分からん暗号書くなや

**デフォルトの名無しさん** · 2018/04/01(日) 00:08:24.40

Σ 総和
∈ 左は右の元である
N 自然数
[ ] 越えない最大の整数
/ 除算
^ べき乗

**デフォルトの名無しさん** · 2018/04/01(日) 02:06:20.43

記号の優先順位も書けや
あと{}の意味はぶくなや

**デフォルトの名無しさん** · 2018/04/01(日) 07:11:43.66

そんなのだから文系ってバカにされるんだぞ？

**デフォルトの名無しさん** · 2018/04/01(日) 07:16:13.39

意味わからん暗号て。。。
論理と集合やらんかったのか？
まだ習ってない歳なの？

**デフォルトの名無しさん** · 2018/04/01(日) 07:36:56.40

高卒にはつらい文字だ。

**デフォルトの名無しさん** · 2018/04/01(日) 07:50:55.11

こういう数式をTEX記法でup出来るサイトなかったっけ？