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

**383** · 2019/12/20(金) 14:24:42.29

>>383
Ruby で、

ary = "MY FAVORITE SONGS".split.map( &:downcase ) # すべて小文字へ

puts ary.join( "_" ) #=> my_favorite_songs
puts ary.map( &:capitalize ).join #=> MyFavoriteSongs

puts ary.map.with_index { |word, idx|
if idx == 0
word # 最初だけ、そのまま
else
word.capitalize
end
}.join #=> myFavoriteSongs

**デフォルトの名無しさん** · 2019/12/20(金) 17:55:37.64

>>346 julia

println(sum(Set([3:3:1000; 5:5:1000])))

**デフォルトの名無しさん** · 2019/12/20(金) 19:38:12.53

お題（>>346の改変版）

1から100万までの整数のうち、2か3か5か7か11か13か17か19の倍数の合計を
求める処理を3000回繰り返してから、結果を表示せよ。ただし、ideoneの
実行制限時間（5秒）以内に完了すること。

**デフォルトの名無しさん** · 2019/12/20(金) 20:40:12.54

>>392 C++
https://ideone.com/N01T86

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

今アップしようと思ったら
>>393とそっくりだった

**デフォルトの名無しさん** · 2019/12/20(金) 21:22:01.32

素数の数をカウントする代わりに
マイナスを付けて素数を掛け算してるのが違うくらい

**デフォルトの名無しさん** · 2019/12/20(金) 21:28:45.69

お題
3000回じゃなくてもっとマシな出し方なかったのかね？
最適化で1回の結果を使い回されて何回やっても時間同じになっちゃってたよ

3000回数分合計して、最後に3000で割ってたんだけど
最適化が頭良すぎた

**デフォルトの名無しさん** · 2019/12/20(金) 21:49:16.14

やったー僕が考えた効率良いプログラムだと5秒以内で3000回も計算できたぞ！
そうだこれをお題にしてやろう！

**デフォルトの名無しさん** · 2019/12/20(金) 22:16:29.10

C/C++だと
ほんのちょっと数学の知識を使えば
コード上の工夫をまったくしなくても0.01秒
コード上の工夫でまだまだ速くなる
スクリプト系言語でも100倍はかからない気がする

なぜ5秒？
なぜ1000000？
なぜ3000回？

謎だ

**デフォルトの名無しさん** · 2019/12/20(金) 22:30:48.36

些末な最適化など
数学的知識に基づくオーダーの低減に比べたらむなしい

**デフォルトの名無しさん** · 2019/12/20(金) 22:30:49.77

数学的知識を使わないで
単純に足していくアルゴリズムを
コードの工夫で5秒切るって問題？

**デフォルトの名無しさん** · 2019/12/20(金) 22:38:11.88

>>399

>>393は素数の数に対してオーダーは2^n nだけど、
コード上の工夫で2^nになる

さらに、
乗算の数十倍時間がかかる、変数による除算も
コード上の工夫で無くせる

些細な差では無いと思う

**デフォルトの名無しさん** · 2019/12/20(金) 22:38:43.75

>>399

>>393は素数の数に対してオーダーは2^n nだけど、
コード上の工夫で2^nになる

さらに、
乗算の数十倍時間がかかる、変数による除算も
コード上の工夫で無くせる

些細な差では無いと思う

**デフォルトの名無しさん** · 2019/12/20(金) 22:39:52.16

ダブった

**デフォルトの名無しさん** · 2019/12/20(金) 22:50:38.46

数学も計算機学もどっちも大事

**デフォルトの名無しさん** · 2019/12/20(金) 23:00:03.89

>>393
正解。ちなみにRで短く書いたプログラム: https://ideone.com/T9oDqa
結局、奇数個の積の倍数の個数の和から偶数個のそれを引くというやり方は同じだな。

>>397
そう。上のプログラムが5秒以内に余裕を持って終わるように繰り返し回数を設定したw
効率というより短いのが好きで書いた。

>>398
>>393をRにそのまま移植すると5秒以内に終わらず、1000回に減らしても
（https://ideone.com/K94wA8）4.56秒かかって、上のプログラムの2.43秒より
遅いよ。Rでは自前のループを書くよりも、関数や演算子を使って短く書いた方が
速くなることが多い。

**デフォルトの名無しさん** · 2019/12/20(金) 23:06:22.58

>>405
Rだと3桁倍も時間がかかるのか
衝撃

**デフォルトの名無しさん** · 2019/12/20(金) 23:10:59.45

1000までではなく与えられた自然数までということ以外は>>346と同じ問題が
オライリーの「Modern C++チャレンジ」に載っているが、示されている解答は
if (i % 3 == 0 || i % 5 == 0) sum += i; という単純に足していく方式だな。
本の副題は「C++17プログラミング力を鍛える100問」だが、何が鍛えられられるのか
よく分からない。

**デフォルトの名無しさん** · 2019/12/20(金) 23:11:25.23

C/C++で1秒かかる問題は
C/C++限定になっちゃう感じだね

**デフォルトの名無しさん** · 2019/12/20(金) 23:14:31.11

>>407
算数やアルゴリズムじゃなくて
言語の勉強ってことでしょ

**デフォルトの名無しさん** · 2019/12/21(土) 05:43:11.08

連投アスペ君うざいよ
学歴詐称までしてたみたいだけど

**デフォルトの名無しさん** · 2019/12/21(土) 17:30:00.35

お題
ビットコインの採掘問題です

000 ～ 300 までの3桁の整数の文字列を、MD5 で暗号化した時に、
冒頭部分から、5 が最も多く続く、整数は何？

答え、239 : 555d6～

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

>>411
Java
https://paiza.io/projects/CEzxtHHxdDnP_sglVIdxMg

**デフォルトの名無しさん** · 2019/12/21(土) 22:58:23.57

>>411　PowerShell
$MD5 = new-object "System.Security.Cryptography.MD5CryptoServiceProvider"
$a = 0..300
$hash = $a |% {-join ($MD5.ComputeHash([char[]]("{0:000}" -f $_)) |% {"{0:x2}" -f $_})}
$n = $hash |% {[RegEx]::Match($_, "^5+").length}
$max = ($n | measure -max).Maximum
$a |? {$n[$_] -eq $max} |% {"$_ : " + $hash[$_]}

-- 実行結果 --
239 : 555d6702c950ecb729a966504af0a635

**デフォルトの名無しさん** · 2019/12/22(日) 03:50:07.73

>>411
Kotlin
https://paiza.io/projects/Y5gSI5-FC_UyaaRC1V_69w

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

>>411 Ruby

require 'digest'
p ("000".."300").map{|i|[Digest::MD5.hexdigest(i).index(/[^5]/),i]}.max[1]

**411** · 2019/12/22(日) 19:20:37.12

>>411 Ruby

require 'digest'

# :count は、先頭から続く、5の数
Result = Struct.new( :num, :md5, :count )

res = ( "000".."300" ).each_with_object( Result.new( nil, nil, -1 ) ) do |num, res|
md5 = Digest::MD5.hexdigest( num ) # ハッシュ化

md5.each_char.with_index do |char, idx| # 1文字ずつ処理する
if char != "5"
if idx > res.count # 大きい時だけ更新する
res.num = num
res.md5 = md5
res.count = idx
end
break
end
end
end

puts "#{ res.num } : #{ res.md5 }"
#=> 239 : 555d6702c950ecb729a966504af0a635

**デフォルトの名無しさん** · 2019/12/23(月) 15:49:57.54

>>411
Perl5
https://paiza.io/projects/tD4ph2pfNvHIVTsKVqCbuA

**デフォルトの名無しさん** · 2019/12/24(火) 02:05:20.47

>>377
>>389

・n=13 のとき
　条件(2,2)
{12345678} = A, {9,10} = B, 11=C, 12=D, 13=E と略記する。

　ABCDE, -, -, -
　　手順１
　CDE, -, -, AB
　　手順２
　CD, E, -, AB
　ACD, E, -, B
　　手順３
　ACD, -, -, BE
　CD, -, -, ABE
　　手順２
　C, D, -, ABE
　AC, D, -, BE　
　　手順３
　AC, -, -, BDE
　C, -, -, ABDE
　-, C, -, ABDE
　A, C, -, BDE
　　手順３
　A, -, -, BCDE
　-, -, -, ABCDE
にて可能。

**デフォルトの名無しさん** · 2019/12/24(火) 02:16:33.78

　#A = f(2,1) = 8,　　　#B = 2
* 手順１
　ABX, -, -, -
　BX, -, -, A
　OX, 9, -, A
　AOX, 9, -, -
　AOX, -, -, 9
　OX, -, -, A9
　X, O, -, A9
　AX, O, -, 9
　AX, O, 9, -
　AX, -, 9, O
　AX, -, -, B
　X, -, -, AB
*手順２
　CDY, -, -, *
　DY, C, -, *
　Y, C, D, *
　Y, -, CD, *
　-, Y, CD, *
　-, CY, D, *
　D, CY, -, *
　CD, Y, -, *
* 手順３
　*, Y, -, BZ
　*, 9Y, -, OZ
　*, 9Y, O, Z
　*, Y, B, Z
　*, -, B, YZ
　*, 9, O, YZ
　*, 9, -, OYZ
　*, -, -, BYZ

**デフォルトの名無しさん** · 2019/12/24(火) 06:16:15.22

おめでとう
次は(2,2,2)

**デフォルトの名無しさん** · 2019/12/24(火) 06:33:05.83

n=13を考えるとき
真ん中2本が空いてる時にはn=12までは動かせる
っていう仮定を使うと
考え方が楽になりますよ

これが出来たら
あとは(2,1)のn=8から1枚ずつ増やしていく帰納法が使えます

**デフォルトの名無しさん** · 2019/12/24(火) 07:26:03.90

a≧b≧c≧d≧e≧1

f(a,b,c,d,e)=f(a-1,b,c,d,e)+2n+1

n = max { a, f(b-1,c,d,e) }
+ max { b, f(c-1,d,e) }
+ max { c, f(d-1,e) }
+ e

**デフォルトの名無しさん** · 2019/12/24(火) 07:43:48.05

(a,b,c,d,e) の動かしかた

A : 小さい f(a-1,b,c,d,e) 枚
X : 最大の1枚
(n) : A,X以外の任意のn枚
n : >>422で定義

A(2n)X / - / -
(n)X / - / A(n)
(n) / X / A(n)
A(n) / X / (n)
A(n) / - / (n)X
- / - / A(2n)X

**デフォルトの名無しさん** · 2019/12/24(火) 07:48:24.24

ミスった

n = min { a, f(b-1,c,d,e) }
+ min { b, f(c-1,d,e) }
+ min { c, f(d-1,e) }
+ e

**デフォルトの名無しさん** · 2019/12/24(火) 19:47:21.14

動かせる枚数だけですがコードにしました
https://ideone.com/X01d46

**デフォルトの名無しさん** · 2019/12/25(水) 16:51:57.78

[お題]　2020と素数

　"2020"の省略形は"20"
　異なる素数を20個使って、総合計で2020を作る。

1) 何種類できるか(組合せで)。 --> ?

　　以下数列は昇順でソート済みでの比較
2) 数列の比較で(辞書順)最小な数列を出力。
--> [3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,73,1381]
3) 数列の比較で(辞書順)最大な数列を出力。
--> ?

例) 総合計 26 で要素数 3の場合
　種類は[2,5,19],[2,7,17],[2,11,13]の3種類、
　最小は[2,5,19], 最大は[2,11,13]

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

2) 3) は瞬時だけど
1) は難しい

出題者は出来たんだよね？

**426** · 2019/12/25(水) 19:20:25.05

>>427
1)は二年前の大晦日に、part9でほぼ既出問題。
とても大きな数字になるから、
全探索しないでね、って意味で1)においたのだが……

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

https://ideone.com/UhFnyK

**デフォルトの名無しさん** · 2019/12/25(水) 22:48:16.07

合ってる？

**デフォルトの名無しさん** · 2019/12/25(水) 22:57:35.89

辞書順最後は
{ 53, 59, 61, 67, 71, 73, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151 }

**426** · 2019/12/25(水) 23:33:28.28

>>429, 431 当方とおなじです。

>>426
　https://ideone.com/SuOGod

数が程々なので、まとめて手抜きの"文字列DP"をやってます。
(pypyで1秒以内で回っているのだから、真面目にやる必要ないでしょう)

**デフォルトの名無しさん** · 2019/12/26(木) 01:18:40.30

がんばって速くしてみたけどあまり速くならなかった

https://ideone.com/lalB7F

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

C++だから速いはず
だけど大差無いって事は
アルゴリズムで負けてる？

**デフォルトの名無しさん** · 2019/12/26(木) 04:04:05.93

>>421

>>418 は >>371 にEを追加したものです。

　ピン0⇔ピン3 間で移動する「4ピン手順」と
　ピン{{0,1,2} または {1,2,3} 間で移動する「3ピン手順」
　を交互に行ないます。

*手順１は4ピン手順で、ABの10個を移動します。
*手順2、手順3 は3ピン手順です。
　　ピン0→ピン{1,2}　あるいはピン{1,2}→ピン3　間でxを移動するときは
　　xより小さい円盤を1本のピンに集めることが必要で、これがネックですね。
　　最初に12個移動するのはどうかと思うけど････

**デフォルトの名無しさん** · 2019/12/26(木) 07:13:27.63

>>435
帰納法を使えば
具体的な手順は>>423の手順だけで
≧を示せる

と言ってるだけですよ

帰納法の仮定として
・>>422の式より円盤の枚数が少ない時は動かせる
・>>422の条件より置ける置ける枚数が少ない時は>>422が成り立つ
を使う

**デフォルトの名無しさん** · 2019/12/26(木) 07:22:33.88

>>371から>>423に進化して
本数も枚数も一般化出来た
( >>425 )

帰納法の仮定を使って
>>423の(n)は任意のn枚に出来る
これによって手順の記述が対称になり
非常に簡略化出来てます

最短手順を求めるのはまた別の話で
これは帰納的には求められないと思っています

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

ちなみに >>371の式は最大枚数ではなくて
Cをn枚にすることで最大になります

動かせる最大枚数はわかったので
残る課題は｢最短手順を求める｣のみ

**蟻人間** ◆T6xkBnTXz7B0 · 2019/12/26(木) 15:19:10.12

お題: 半角英数からなるユーザーIDとパスワードで認証できるアカウントのシステムを以下の要件で作る。

1.新規登録を選んでユーザーIDとパスワードとメールアドレスを入力するとアカウント登録ができる。
2. 複数アカウント対応。ユーザーIDの重複はダメ。
3. アカウント一覧を選ぶとアカウントの一覧とログイン状態が見える。
4. ログインを選んでユーザーIDとパスワードの入力が一致すればログインできる。
5. ログアウトを選べばログアウトできる。
6. パスワードを忘れたとき、アカウントの回復を選んでメルアド入力すると、メールが来てパスワードがリセットされる。

**デフォルトの名無しさん** · 2019/12/26(木) 19:06:46.63

>>432
　https://ideone.com/SuOGod
　
　よくある経路復元方式に変更。
　(大量な文字列のコピーが減った)

**デフォルトの名無しさん** · 2019/12/26(木) 19:20:20.20

>>429を少し速くした
https://ideone.com/Hysp8W

**デフォルトの名無しさん** · 2019/12/26(木) 21:44:10.91

https://ideone.com/XFJToQ
vectorを使いまわしするようにしたら速くなった

**デフォルトの名無しさん** · 2019/12/27(金) 00:16:14.43

https://ideone.com/tm5nPe
まだ省くことができた

**蟻人間** ◆T6xkBnTXz7B0 · 2019/12/27(金) 18:58:01.81

Web系もプログラミングの一種なんだけど、日本のIT教育では軽視されてるみたいなんだ。

**デフォルトの名無しさん** · 2019/12/27(金) 20:56:28.17

<('o')>ﾌｰﾝ

◆QZaw55cn4c · 2019/12/27(金) 21:03:47.38

>>444
web 系をはじめるには、どういう環境で学べばいいですか？

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

https://ideone.com/3sneU6

>>440のアルゴリズムの方が速いね

**デフォルトの名無しさん** · 2019/12/27(金) 21:14:11.36

↑が100回

これが1回
https://ideone.com/ndU5d2

**デフォルトの名無しさん** · 2019/12/27(金) 22:14:31.51

>>426 類似問題

素数を20個使って、総合計で2020を作る。
(同じ素数を複数使ってよい）

何種類できるか(組合せで)。 -->?
(同じ数字は区別しない -> ソートして数列が異なるもので1種類)

ちなみに、辞書順最小が[ 2(* 18), 5, 1979] 、最大が[ 101(* 20)]になる。

※ 2020で20個なら、まだint64_tでおさまる

**デフォルトの名無しさん** · 2019/12/27(金) 22:54:15.08

↑
>>429の+1を消すだけ

**デフォルトの名無しさん** · 2019/12/27(金) 22:58:27.12

お題: 「Happy New Year!!」と出力するプログラムを2020年元日に投稿せよ

**デフォルトの名無しさん** · 2019/12/27(金) 23:32:30.61

>>450
やっぱり(既にできていて)、その程度なのだろう。

自分の方も、ユニーク時は更新が伝播しないように
逆順で処理していたのを、伝播するよう正順に戻すだけ。

>>449
　https://ideone.com/nQJWLb

**デフォルトの名無しさん** · 2019/12/27(金) 23:43:22.25

>>452
お題
同じ数は4個まで

**デフォルトの名無しさん** · 2019/12/28(土) 01:41:03.72

>>447のだと
for (j = N - 1; j >= 0; j--) {
これを
for (j = 0; j < N; j++) {
こう逆にすると重複の計算ができるんだね

**デフォルトの名無しさん** · 2019/12/28(土) 03:25:23.74

>>423

m≧n≧1 のとき
　ピン2に大円盤が1枚以下のときは、ピン0⇔ピン1間、ピン1⇔ピン3間で
　n枚組の円盤を移動できますね。 (3ピン手順)

　A: 1,2,････,x　のx個組　ただし x=f(m-1,n)
　B: x+1,...,x+n　のn個組
　C: x+n+1,････,x+2n+1 のn個組
　D: x+2n+1
とする。

**デフォルトの名無しさん** · 2019/12/28(土) 03:28:09.64

　ABCD, -, -, -
　BCD, -, -, A
　　手順２
　BC(2..n)D, -, C(1), A
　ABC(2..n)D, -, C(1), -
　ABC(2..n)D, -, -, C(1)
　BC(2..n)D, -, -, AC(1)
　　手順２
　BC(3..n)D, -, C(2), AC(1)
　ABC(3..n)D, -, C(2), C(1)
　　手順３
　ABC(3..n)D, -, -, C(1..2)
　････
　同様にしてC(k)とDを移動する。(k=1..n)
　････
　ABD, -, -, C
　BD, -, -, AC
　　手順２
　B, -, D, AC
　AB, -, D, C
　　手順３
　AB, -, -, CD
　B, -, -, ACD
　B(2..n), -, B(1), ACD
　AB(2..n), -, B(1), CD
　AB(2..n), -, -, B(1)CD
　B(2..n), -, -, AB(1)CD
　B(3..n), -, B(2), AB(1)CD
　AB(3..n), -, B(2), B(1)CD
　　手順３
　AB(3..n), -, -, B(1..2)CD

**デフォルトの名無しさん** · 2019/12/28(土) 03:34:05.21

　B(3..n), -, -, AB(1..2)CD
　･････
　同様にしてB(k) を移動する。(k=1..n)
　･･････
　B(n), -, -, AB(1..n-1)CD
　-, -, B(n), AB(1..n-1)CD
　A, -, B(n), B(1..n-1)CD
　　手順３’
　A, -, -, BCD
　-, -, -, ABCD

∴　f(m,n) ≧ f(m-1,n) + 2n + 1,

・手順２
　BC(k..n)D, -, -, *
　C(k..n)D, B, -, *
　C(k+1..n)D, B, C(k), *
　BC(k+1..n)D, -, C(k), *　

・手順３
　*, -, C(k), C(1..k-1)
　*, C(1..k-1), C(k), -
　*, C(1..k-1), -, C(k)
　*, -, -, C(1..k)

・手順３’
　*, -, B(k), B(1..k-1)CD
　*, B(1..k-1), B(k), CD
　*, B(1..k-1), -, B(k)CD
　*, -, -, B(1..k)CD

**デフォルトの名無しさん** · 2019/12/28(土) 12:49:55.64

いつまでハノイのメモ帳続けるんだよｗ

**デフォルトの名無しさん** · 2019/12/28(土) 16:57:29.50

>>453
本気でやるには、"もらう"へ作り変える必要もあり、辛い

4つ程度なら、4倍回して出しちゃうだろう。
　(四重ループで汚すぎるのでソースは非公開)
　4と6の結果のみ載せておこう、あっているかも微妙。
　
合計: 2020 使用個数: 20 複数制限: 4-->
15100329420197868
[2, 2, 2, 2, 3, 3, 3, 3, 5, 5, 5, 5, 7, 7, 7, 7, 11, 11, 17, 1913]
[89, 89, 89, 97, 97, 97, 101, 101, 101, 101, 103, 103, 103, 103, 107, 107, 107, 107, 109, 109]
********************************************* 0.43922sec ********************

合計: 2020 使用個数: 20 複数制限: 6-->
16509239212753751
[2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 5, 5, 5, 5, 5, 7, 7, 1951]
[97, 97, 97, 97, 97, 97, 101, 101, 101, 101, 101, 101, 103, 103, 103, 103, 103, 103, 107, 107]
********************************************* 0.30568sec ********************

**デフォルトの名無しさん** · 2019/12/28(土) 19:46:33.82

>>426の1)はRで短く書ける(先頭・末尾行は正味の実行時間計測用)。
https://ideone.com/7eV3Kh

Rでは整数は32ビットまでなので、浮動小数点型(double型)で計算しているが、
double型の有効桁数は15桁なので、小数部を非表示にすれば、答である13桁の
整数は正しく表示される。

64ビット整数を扱うbit64というパッケージも一応あるが、それを使うと
正味の実行時間が4.3倍もかかってしまう。
https://ideone.com/hzr0rq

**デフォルトの名無しさん** · 2019/12/28(土) 21:25:10.79

>>453
>>447を使って書いた
https://ideone.com/EwLCGD
メモリの使用を抑えたのも書いたけど遅くなった

**デフォルトの名無しさん** · 2019/12/28(土) 22:48:40.84

お題
最小値のあるインデックスから離れるほど数字が大きくなる数列があります
増加量はランダムです
その数列の中から効率よく最小値を探してください

入力: 115, 109, 107, 101, 92, 85, 76, 66, 65, 62, 53, 49, 40, 38, 35, 25, 23, 17, 9, 2, 0, 5, 8, 10, 11, 20, 30, 37, 42, 47
出力: 0

入力: 110, 104, 96, 93, 84, 83, 87, 93, 98, 103, 113, 120, 121, 128, 133, 134, 142, 152, 159, 169, 171, 174, 183, 186, 196, 203, 210, 212, 221, 224
出力: 83

入力: 138, 135, 127, 124, 122, 112, 103, 98, 92, 87, 77, 73, 71, 63, 59, 51, 41, 36, 45, 54, 63, 71, 81, 88, 90, 98, 105, 112, 114, 119
出力: 36

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

>>462
二分探索で答えてもらいたいんだろ。
https://ideone.com/PKF7cQ

**デフォルトの名無しさん** · 2019/12/28(土) 23:34:06.76

>>463
私が用意してた答えは二分探索ではありませんでしたが二分探索でできるんですねすごいです

**デフォルトの名無しさん** · 2019/12/28(土) 23:38:08.54

>>463 訂正。signが抜けていた。
https://ideone.com/28YBxQ

**デフォルトの名無しさん** · 2019/12/28(土) 23:42:14.62

再度訂正。1行目が消えていた。
https://ideone.com/mgNo9a

**デフォルトの名無しさん** · 2019/12/28(土) 23:45:03.69

最初に思いつくのが二分探索だからそれより速い方法があるんだろうなと思った

**デフォルトの名無しさん** · 2019/12/29(日) 00:04:58.67

https://ideone.com/gcG2Ls

**デフォルトの名無しさん** · 2019/12/29(日) 00:15:11.87

https://ideone.com/Oj779u

**デフォルトの名無しさん** · 2019/12/29(日) 00:41:31.56

>>466 最小値が複数ある場合の条件分けが抜けていた。
https://ideone.com/Lcraw3

Rのbinsearch関数は値の返し方に癖があって、条件分けを見落としやすいな。

**デフォルトの名無しさん** · 2019/12/29(日) 02:13:42.53

>>462
Java 三分探索で2/3に範囲を狭めてく
https://paiza.io/projects/NjNBWH-afFYHO5H9w8EJeQ

1/2に減らせる二分探索には敵わない
傾きを二分探索するって発想はなかったわー

**デフォルトの名無しさん** · 2019/12/29(日) 02:17:13.97

>>468
実装の効率はパないすね、効率はそういう意味でもありましたホントです

**デフォルトの名無しさん** · 2019/12/29(日) 09:24:17.66

いやいや
ただのリニア検索より遅いのはあり得ん

**デフォルトの名無しさん** · 2019/12/29(日) 19:39:43.67

でも出てる中で一番速いけど。

**デフォルトの名無しさん** · 2019/12/29(日) 21:33:41.90

>>474
そりゃ、例の数列では要素数が少なくてアルゴリズムの差が出にくいからだろ。
「効率よく」とわざわざ書いてある問題なんだから、もっと大きなデータを与えた
場合も想定して答えるのが普通。

例えば、100万から1までの連番の後に2から50万までの連番が続く数列を与えれば
アルゴリズム間の違いは歴然。

Rで二分探索、min関数、sort関数で求めたときの1回あたり平均実行時間を計測すると、
0.132, 2.08, 55.2ミリ秒で桁が違う (PCでは二分探索はもう少し速かった)。
計算量オーダーがO(log n), O(n), O(n log n)だから当たり前だが。
https://ideone.com/kuqONz

C++の>>468に同じデータを与えると108ミリ秒かかり、何とRのsort関数より遅い。
Rの関数はCで書かれているものが多いから、この差はつまりはCとC++のSTLの
性能差によるものだろう。
https://ideone.com/jMCCfP

**デフォルトの名無しさん** · 2019/12/29(日) 21:37:04.80

>>475
>>469の場合だとどんな感じ？

**デフォルトの名無しさん** · 2019/12/29(日) 21:41:48.80

なんかすまんなみんな、ワイのせいで・・・ワイのせいで・・・ワイは悪くない

**デフォルトの名無しさん** · 2019/12/29(日) 22:06:29.15

>>462くらい乱数に法則があれば2分検索より速いアルゴリズムを作れる
例としてはイマイチ

**デフォルトの名無しさん** · 2019/12/29(日) 22:38:51.59

このスレだけマジで何言ってんのか理解できない

やっぱまずいよなあ、数学勉強し直さなきゃなあ

**デフォルトの名無しさん** · 2019/12/29(日) 22:43:46.32

>>426
1)数百万規模でありそう。

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

>>475
最適化されたCとC++のSTLならCのほうが分があるということ？

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

突き詰めた機械語にコンバートされるCと
汎用性のSTL
どちらに分があるのか

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

戦争になりそうだが、俺は膝にassertを受けちまってな
皆の力にはなれない、すまない

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

Rのsortは基数ソート使ってるらしいからその差かもしれない
c++のもこのデータの場合stable_sortに変えると3倍くらい速くなった

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

いいっすねー、新しいお題用意してるからちょっとまってて

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

お題
四角形の縦の長さの数列と
四角形の横の長さの数列と
四角形の面積が与えられます

縦の長さと横の長さを組み合わせて
与えられた面積と一致する四角形をいくつ
作ることができるか求めてください

入力: 41, 9, 25, 92, 48, 15, 69, 61, 85, 22, 82, 79, 7, 34, 86, 29, 36, 77, 16, 79, 57, 8, 9, 58, 86, 0, 24, 83, 63, 46
入力: 12, 79, 11, 65, 9, 33, 44, 54, 30, 43, 76, 23, 24, 86, 15, 35, 21, 97, 57, 96, 6, 3, 59, 51, 29, 58, 93, 94, 49, 8
入力: 195?

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

195の後ろの文字化けは無視してください
195と書きたかったのです

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

入力の数列の長さが数万になってもちょっぱやで計算できるとなお良いです

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

四角形の縦の長さの定義は？
まさか四角形＝長方形じゃないでしょ