プログラミングのお題スレ 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/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出来るサイトなかったっけ？

**デフォルトの名無しさん** · 2018/04/01(日) 09:35:03.69

>>477
文系だからではなく、元々バカなだけだろううな。
今時は普通なら、知らん事は自分で調べる。

**デフォルトの名無しさん** · 2018/04/01(日) 09:49:03.09

そもそも「素因数分解した時の5の指数」が分からんし！
なんでそれが0の数と関係あるのかも分からんし！
文系を迫害すんなや

◆QZaw55cn4c · 2018/04/01(日) 10:40:13.62

>>480
mediawiki を採用しているところですね
でも自分で mediawiki をビルドしようとすると、TeX 表記導入のところで嵌ります、うまくいかない

**デフォルトの名無しさん** · 2018/04/01(日) 13:21:09.52

これ分からなくなって八つ当たりしてんな、一旦ROMって落ち着けよ
10!=3628800=36288x10^2のように、後ろの0の数は10が何個掛けられているかで決まる
10=2x5だから2と5の掛けられている数のうち小さい方とも言えるな
で、一例として10!=1x2x3x4x5x6x7x8x9x10=2^8x3^4x5^2x7=2^6x3^4x7x(2^2x5^2)だから、0が2つ付くと言える
どう考えても2の素因数は5の素因数より多くなるので5の素因数の数だけ分かれば良い
この時、5の素因数の数はnが5の倍数になった時(n/5)+nが5^2の倍数になった時(n/(5^2))+…と計算すれば求まる端数切り捨てな

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

>>484
> どう考えても2の素因数は5の素因数より多くなる

そうとは限らないじゃん
2の素因数の数も数えなきゃ不正確じゃん

**KAC** · 2018/04/01(日) 14:29:21.34

>>485
それを主張するなら、2の方が多くなる事例をあげるか、証明するかしないと。

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

多い分には問題がない

**デフォルトの名無しさん** · 2018/04/01(日) 15:21:10.32

>>485
任意の2以上の整数nとする. n!に対して素数kの素因数の数が F(n, k) になる事は機知とする.
F(n, k) = [n/k] + [n/(k^2)] + ...
またガウス記号の定義([x] は x を超えない最大の整数)から任意の実数 x に対して,
x - 1 < [x] <= x　　……☆.
m_k を n/(k^m_k) >= 1 となる最大の整数とすると,
n/(k^m_k) >= 1 ⇔ n < k^m_k ⇔ log_k(n) >= m_k　なので, m_k = [log_k(n)].
また m_k より大きな任意の整数 i に対して n/(k^i) < 1 なので, [n/(k^i)] = 0.
従って, F(n, k) = [n/k] + [n/(k^2)] + ... + [n/(k^m_k)].
さて, ☆より
F(n, 5) <= n/5 + n/(5^2) + ... + n/(5^m_5)
= n*(1/5)*(1 - 1/(5^m_5))/(1 - 1/5)
= n*(1 - 1/(5^m_5))/(5 - 1)
= n*(1 - 1/(5^[log_5(n)]))/(5 - 1)
<= n*(1 - 1/(5^log_5(n)))/(5 - 1)
= (n - 1)/4,
F(n, 2) > n/2 - 1 + n/(2^2) - 1 + ... + n/(2^m_2)
= n*(1/2)*(1 - 1/(2^m_2))/(1 - 1/2) + (-1)*m_2
= n*(1 - 1/(2^m_2)) - m_2
> n*(1 - 1/(2^(log_2(n) - 1))) - log_2(n)
= n - log_2(n) - 2.
依って2以上の任意の整数nに対して,
F(n, 5) <= (n - 1)/4 < n - log_2(n) - 2 < F(n, 2)
となり題意は示された.
((n - 1)/4 < n - log_2(n) - 2 は増減表を書くなりして確かめて)

**デフォルトの名無しさん** · 2018/04/01(日) 15:34:29.77

a,bをとりあえず非負実数
[a]をaを超えない最大の整数として
a>=b→[a]>=[b]
[a+b]>=[a]+[b]
はすぐにわかる。
n!を割る2べき数の最大指数は1からnまでに偶数が[n/2]個
あることより[n/2]以上であることもすぐわかる

5^m<=n<5^(m+1)として
[n/5]+[n/5^2]+...+[n/5^m]
<=[n/5+n/5^2+...+n/5^m]
<=[n/5+n/5^2+...]=[n/4]<=[n/2]<=n!を割る2べき数の最大指数

◆QZaw55cn4c · 2018/04/01(日) 15:46:35.74

>>486
「素因数 2 の数は素因数 5 の数よりも多い」
を使うのなら証明は使う側がしないといけないだろう？一定の範囲では 2の倍数の方が 5 の倍数よりも多いとはわかるが、素因数の数について正確なことをいえるかな？

**デフォルトの名無しさん** · 2018/04/01(日) 15:47:58.83

[n/5]+2[n/5^2]+3[n/5^3]+...+m[n/5^m]
を評価しなければいけなかった（。。）

mを非負整数とするときm[a]<=[am]
だから
[n/5]+2[n/5^2]+3[n/5^3]+...+m[n/5^m]<=
[n/5]+[2n/5^2]+[3n/5^3]+...+[mn/5^m]<=
[n/5+2n/5^2+...+mn/5^m+...]<=
[n (1/5)(1+2(1/5)+3(1/5)^2+....)]
=[n(1/5)/(1-1/5)^2]
=[5n/16]<=[n/2]
あとは同じ 👀
Rock54: Caution(BBR-MD5:0be15ced7fbdb9fdb4d0ce1929c1b82f)

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

なんか長々と書かせちゃってごめん
正の整数の全範囲が対象じゃなくてあくまで「n!」だってこと忘れてたわ

**デフォルトの名無しさん** · 2018/04/01(日) 18:24:24.96

勘違い

**デフォルトの名無しさん** · 2018/04/01(日) 18:24:43.79

>>491は無視して

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

>>462
>未知の課題に対するコーディング能力
とか言ってるが、高校数学ではよくある問題だぞ？

ttp://examist.jp/mathematics/integer/kaijyou-soinsu/
ttp://www.geocities.jp/math12345go/math-qa/kaijou.htm
ttps://www.school-turnup.com/p-12594/
ttps://www.shinko-keirin.co.jp/keirinkan/tea/kou/jissen/sugaku/201603/index.html

高卒なんて言い訳になんねーよ

**デフォルトの名無しさん** · 2018/04/01(日) 22:25:21.45

>>495
数I・Aで100点だったが、数II・Bで0点取って、数III・Cは選択しなかった俺に謝れ

**デフォルトの名無しさん** · 2018/04/02(月) 01:59:38.46

お題そのものが数学のお題だったということだな。

**デフォルトの名無しさん** · 2018/04/02(月) 07:50:16.86

プログラミング的には、n!を割る最大の5のべき乗の指数が最大の2のべき乗の指数
を超えないということを使わずに（＝知らずに）
それでも十分な速度（実質>>469程度の処理しかしない）なものが書けるかということが課題

高校レベルの課題に見えて実は決してそうじゃないな

**KAC** · 2018/04/02(月) 08:54:14.80

>>498
設計したこと無いの？

**デフォルトの名無しさん** · 2018/04/02(月) 09:32:15.39

select max(m) from select m where 10^m|n!
と同レベルの可読性だが
やることは割り算しながら足し算となるコードなんて
そもそもあるのかよw

**デフォルトの名無しさん** · 2018/04/02(月) 12:18:57.87

>>498
>知らずに十分な速度
その程度なら2の個数も数えるだけだから簡単だし高速だと思う
が、普通はちょっと考えて5だけで良いなと5だけ数えるコードを書くんじゃないかな
何も知らず何も考えず計算機任せの力技ってのだけがプログラミングじゃないでしょ。

**デフォルトの名無しさん** · 2018/04/02(月) 12:28:13.55

高校レベルの数学をすっかり忘れたおぢさんにやさしく教えておくれ。

**デフォルトの名無しさん** · 2018/04/02(月) 12:41:49.07

素因数の数が
m := [log(n)/log(k)]として
　m
　Σ[n/k^i]
i=1
明らかにmも[]の中もkに対して(広義)単調減少なんだから
素数が大きくなるほどn!のその素因数の数が減ることも明確というお話

**デフォルトの名無しさん** · 2018/04/03(火) 00:32:23.81

>>503
ご覧ください、これがアスペです

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

>>498
中学生が手計算で出来るレベルだ
数学苦手でしょ？

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

>>502
1～132の整数の中に5の倍数は何個ある？
1～132の整数の中に25の倍数は何個ある？
1～132の整数の中に125の倍数は何個ある？
1～132の整数の中に625の倍数は何個ある？
...

132の階乗を素数の積で表したとき
5は何回出てくるる？

132の階乗の右に並ぶ0の数は？

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

何時までやってんだよｗ

**デフォルトの名無しさん** · 2018/04/03(火) 09:25:43.98

>>506
132という値を出した理由は？
5,25,125,625を出した理由は？

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

こんだけ話題が伸びてる問題なのに出題後高々10分でほぼ理想的なコードが掛かれてるってのが面白いな

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

個々の住人数学が滅茶苦茶できてコードが3割みたいな人いるからな。

**デフォルトの名無しさん** · 2018/04/03(火) 10:49:30.76

>>508
> 132という値を出した理由は？
１問目の数値からから

> 5,25,125,625を出した理由は？
考えてみよう

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

俺は理想的なコードは割って足すループの方だ
可読性だなんだの風潮はあるが、ああいう一工夫がこういうプログラミングの煌めき

と思う

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

何が煌きだよｗ
定石（じょうしき）だろｗ

**デフォルトの名無しさん** · 2018/04/03(火) 22:23:56.22

>>510
というか至極単純なコードならついついゴルフしたくなってしまうというか

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

お題
与えられたデータを間引きして小さいな順に並べる
間引くデータの個数の最小値を求める

**デフォルトの名無しさん** · 2018/04/03(火) 22:58:26.43

日本語でおｋ

**デフォルトの名無しさん** · 2018/04/03(火) 23:00:28.05

任意の有限長の実数列に対し
単調増加列の中で最大長となる部分列を求めよ

って感じ？

**デフォルトの名無しさん** · 2018/04/03(火) 23:07:35.66

要素数の最大はどれくらい？

**デフォルトの名無しさん** · 2018/04/03(火) 23:31:42.00

>>509
すぐに「n!の末尾の0の個数」などをｸﾞｸﾞって
WEBに書かれている方式をコーディングするか、
自分の頭で方式から考えはじめるかの違いだろうな

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

まさかな…

**デフォルトの名無しさん** · 2018/04/04(水) 00:25:41.22

>>513
そのわりには>>469に至るまで出てきてないわけだが
コロンブスの卵にケチ付けた奴みたいだな

**デフォルトの名無しさん** · 2018/04/04(水) 00:27:47.47

>>515
1,1,1の場合、0個で良いのか？

**デフォルトの名無しさん** · 2018/04/04(水) 00:42:07.59

>>519
ググるような問題か？
普通に義務教育を出てれば一瞬でわかると思うのだが

**デフォルトの名無しさん** · 2018/04/04(水) 00:46:27.40

>>522
「小さいな順」ってどっちだろうね？
単調増加か単調非減少か
私は単調増加だと思ったから答えは2個
普通のソートだと単調非減少だから単調増加？

どっちにしろアルゴリズムは大して変わらん

**デフォルトの名無しさん** · 2018/04/04(水) 00:51:30.79

>>523
義務教育でlogはやら無いぞ
何分でコーディング完了して動作確認までいったのよ

**デフォルトの名無しさん** · 2018/04/04(水) 00:52:29.89

logなんて使わん

**デフォルトの名無しさん** · 2018/04/04(水) 00:53:18.67

素因数分解を習えば十分

**デフォルトの名無しさん** · 2018/04/04(水) 00:53:53.74

>>526
何番のお台の話をしてるんだよ
ずれてるぞボケが

**デフォルトの名無しさん** · 2018/04/04(水) 00:56:57.83

ずれたとしたら俺のせいではない
>>519か>>525が悪い

**デフォルトの名無しさん** · 2018/04/04(水) 00:58:01.53

いや、お前が悪い。きっぱり

**デフォルトの名無しさん** · 2018/04/04(水) 00:59:08.89

んで、お前はその簡単な問題を
何分で問題解決しコーディング完了して動作確認までいったのよ

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

>>519は>>459の問題であることは明らか

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

log使ってんじゃん

普通に義務教育を出てれば一瞬でわかると思って
お前はその簡単な問題を
何分で問題解決しコーディング完了して動作確認までいったのよ
上の方のレスでどれがお前の回答よ

**デフォルトの名無しさん** · 2018/04/04(水) 01:04:22.37

>>531
簡単すぎて書く気にもならんレベル
logなんか使わん

**デフォルトの名無しさん** · 2018/04/04(水) 01:05:01.45

>>506にlogなんか出て来ないだろ？

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

>>534
じゃあlogを使わない計算量の多い方法でもいいよ。

義務教育を出てれば一瞬でわかる問題を
お前が一から考えて自力で解いてコーディングして動作を確かめ
書き込んだレスは上の何番だよ

**デフォルトの名無しさん** · 2018/04/04(水) 01:09:27.61

人のレスをを見たら簡単だと印象を持ったんだろ
自力ですぐには解けなかったんだろ

**デフォルトの名無しさん** · 2018/04/04(水) 01:09:59.83

そもそもlogを使ったコードなんて出てきたか？

**デフォルトの名無しさん** · 2018/04/04(水) 01:10:40.77

ぼけがｗ

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

考え方は>>506
以上

**デフォルトの名無しさん** · 2018/04/04(水) 01:20:52.57

もう構うなよ

**デフォルトの名無しさん** · 2018/04/04(水) 01:39:06.43

>>524
順に並べるということから同値の連続は許して広義の単調増加でよいのでは

工夫のない力技のを描いてみた
https://www.onlinegdb.com/ByuL67-iG

**デフォルトの名無しさん** · 2018/04/04(水) 01:41:20.57

↑
一応2行ほど費やしてほんのちょびっとだけ枝刈りしてある

**デフォルトの名無しさん** · 2018/04/04(水) 02:12:06.95

なら自分も広義単調増加で
LISだし二分探索のO(NlogN)で実装
https://ideone.com/kN5UFU