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

1 名前：デフォルトの名無しさん mailto:sage [2019/11/17(日) 09:00:22.10 ID:xqEdXdr6.net] プログラミングのお題スレです。 【出題と回答例】 1 名前：デフォルトの名無しさん 　　お題：お題本文 2 名前：デフォルトの名無しさん 　　>>1 使用言語 　　回答本文 　　結果がある場合はそれも 【ソースコードが長くなったら】 (オンラインでコードを実行できる) https://ideone.com/ codepad.org/ compileonline.com/ rextester.com/runcode https://runnable.com/ https://code.hackerearth.com/ melpon.org/wandbox https://paiza.io/ 宿題は宿題スレがあるのでそちらへ。 ※前スレ プログラミングのお題スレ Part15 mevius.5ch.net/test/read.cgi/tech/1564310397/ 411 名前：デフォルトの名無しさん mailto:sage [2019/12/20(金) 22:38:43.75 ID:ZH5ZbPnE.net] >>399 >>393は素数の数に対してオーダーは2^n nだけど、 コード上の工夫で2^nになる さらに、 乗算の数十倍時間がかかる、変数による除算も コード上の工夫で無くせる 些細な差では無いと思う 412 名前：デフォルトの名無しさん mailto:sage [2019/12/20(金) 22:39:52.16 ID:ZH5ZbPnE.net] ダブった 413 名前：デフォルトの名無しさん mailto:sage [2019/12/20(金) 22:50:38.46 ID:qHTdS2+z.net] 数学も計算機学もどっちも大事 414 名前：デフォルトの名無しさん [2019/12/20(金) 23:00:03.89 ID:KibkA5Ab.net] >>393 正解。ちなみにRで短く書いたプログラム: https://ideone.com/T9oDqa 結局、奇数個の積の倍数の個数の和から偶数個のそれを引くというやり方は同じだな。 >>397 そう。上のプログラムが5秒以内に余裕を持って終わるように繰り返し回数を設定したw 効率というより短いのが好きで書いた。 >>398 >>393をRにそのまま移植すると5秒以内に終わらず、1000回に減らしても （https://ideone.com/K94wA8）4.56秒かかって、上のプログラムの2.43秒より 遅いよ。Rでは自前のループを書くよりも、関数や演算子を使って短く書いた方が 速くなることが多い。 415 名前：デフォルトの名無しさん mailto:sage [2019/12/20(金) 23:06:22.58 ID:ZH5ZbPnE.net] >>405 Rだと3桁倍も時間がかかるのか 衝撃 416 名前：デフォルトの名無しさん [2019/12/20(金) 23:10:59.45 ID:KibkA5Ab.net] 1000までではなく与えられた自然数までということ以外は>>346と同じ問題が オライリーの「Modern C++チャレンジ」に載っているが、示されている解答は if (i % 3 == 0 || i % 5 == 0) sum += i; という単純に足していく方式だな。 本の副題は「C++17プログラミング力を鍛える100問」だが、何が鍛えられられるのか よく分からない。 417 名前：デフォルトの名無しさん mailto:sage [2019/12/20(金) 23:11:25.23 ID:ZH5ZbPnE.net] C/C++で1秒かかる問題は C/C++限定になっちゃう感じだね 418 名前：デフォルトの名無しさん mailto:sage [2019/12/20(金) 23:14:31.11 ID:ZH5ZbPnE.net] >>407 算数やアルゴリズムじゃなくて 言語の勉強ってことでしょ 419 名前：デフォルトの名無しさん mailto:sage [2019/12/21(土) 05:43:11.08 ID:vVh8rrgH.net] 連投アスペ君うざいよ 学歴詐称までしてたみたいだけど 420 名前：デフォルトの名無しさん [2019/12/21(土) 17:30:00.35 ID:BSqycIZI.net] お題 ビットコインの採掘問題です 000 〜 300 までの3桁の整数の文字列を、MD5 で暗号化した時に、 冒頭部分から、5 が最も多く続く、整数は何？ 答え、239 : 555d6〜 421 名前：デフォルトの名無しさん [2019/12/21(土) 21:23:49.40 ID:WOeaPgYE.net] >>411 Java https://paiza.io/projects/CEzxtHHxdDnP_sglVIdxMg 422 名前：デフォルトの名無しさん [2019/12/21(土) 22:58:23.57 ID:hbXQRpYW.net] >>411　PowerShell $MD5 = new-object "System.Security.Cryptography.MD5CryptoServiceProvider" $a = 0..3 423 名前：00 $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 [] [ここ壊れてます] 424 名前：デフォルトの名無しさん [2019/12/22(日) 03:50:07 ID:lBW/6Z3k.net] >>411 Kotlin https://paiza.io/projects/Y5gSI5-FC_UyaaRC1V_69w 425 名前：デフォルトの名無しさん [2019/12/22(日) 14:00:57.91 ID:sfBU8dhx.net] >>411 Ruby require 'digest' p ("000".."300").map{|i|[Digest::MD5.hexdigest(i).index(/[^5]/),i]}.max[1] 426 名前：411 mailto:sage [2019/12/22(日) 19:20:37.12 ID:u+b66RrE.net] >>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 427 名前：デフォルトの名無しさん [2019/12/23(月) 15:49:57.54 ID:8tSOZ4fL.net] >>411 Perl5 https://paiza.io/projects/tD4ph2pfNvHIVTsKVqCbuA 428 名前：デフォルトの名無しさん mailto:sage [2019/12/24(火) 02:05:20.47 ID:3/kDRwCG.net] >>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 にて可能。 429 名前：デフォルトの名無しさん mailto:sage [2019/12/24(火) 02:16:33.78 ID:3/kDRwCG.net] 　#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 430 名前：デフォルトの名無しさん mailto:sage [2019/12/24(火) 06:16:15 ID:cUFUrp77.net] おめでとう 次は(2,2,2) 431 名前：デフォルトの名無しさん mailto:sage [2019/12/24(火) 06:33:05.83 ID:cUFUrp77.net] n=13を考えるとき 真ん中2本が空いてる時にはn=12までは動かせる っていう仮定を使うと 考え方が楽になりますよ これが出来たら あとは(2,1)のn=8から1枚ずつ増やしていく帰納法が使えます 432 名前：デフォルトの名無しさん mailto:sage [2019/12/24(火) 07:26:03.90 ID:cUFUrp77.net] 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 433 名前：デフォルトの名無しさん mailto:sage [2019/12/24(火) 07:43:48.05 ID:cUFUrp77.net] (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 434 名前：デフォルトの名無しさん mailto:sage [2019/12/24(火) 07:48:24.24 ID:cUFUrp77.net] ミスった n = min { a, f(b-1,c,d,e) } + min { b, f(c-1,d,e) } + min { c, f(d-1,e) } + e 435 名前：デフォルトの名無しさん mailto:sage [2019/12/24(火) 19:47:21.14 ID:cUFUrp77.net] 動かせる枚数だけですがコードにしました https://ideone.com/X01d46 436 名前：デフォルトの名無しさん mailto:sage [2019/12/25 ] [ここ壊れてます] 437 名前：(水) 16:51:57.78 ID:eBvDhPt7.net mailto: [お題]　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] [] [ここ壊れてます] 438 名前：デフォルトの名無しさん mailto:sage [2019/12/25(水) 19:05:13.68 ID:LrSoTBV6.net] 2) 3) は瞬時だけど 1) は難しい 出題者は出来たんだよね？ 439 名前：426 mailto:sage [2019/12/25(水) 19:20:25.05 ID:eBvDhPt7.net] >>427 1)は二年前の大晦日に、part9で ほぼ既出問題。 とても大きな数字になるから、 全探索しないでね、って意味で1)においたのだが…… 440 名前：デフォルトの名無しさん mailto:sage [2019/12/25(水) 22:46:56.00 ID:LrSoTBV6.net] https://ideone.com/UhFnyK 441 名前：デフォルトの名無しさん mailto:sage [2019/12/25(水) 22:48:16.07 ID:LrSoTBV6.net] 合ってる？ 442 名前：デフォルトの名無しさん mailto:sage [2019/12/25(水) 22:57:35.89 ID:LrSoTBV6.net] 辞書順最後は { 53, 59, 61, 67, 71, 73, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151 } 443 名前：426 mailto:sage [2019/12/25(水) 23:33:28.28 ID:eBvDhPt7.net] >>429, 431 当方とおなじです。 >>426 　https://ideone.com/SuOGod 数が程々なので、まとめて手抜きの"文字列DP"をやってます。 (pypyで1秒以内で回っているのだから、真面目にやる必要ないでしょう) 444 名前：デフォルトの名無しさん mailto:sage [2019/12/26(木) 01:18:40.30 ID:rIhsLdYp.net] がんばって速くしてみたけどあまり速くならなかった https://ideone.com/lalB7F 445 名前：デフォルトの名無しさん mailto:sage [2019/12/26(木) 01:28:39.37 ID:rIhsLdYp.net] C++だから速いはず だけど大差無いって事は アルゴリズムで負けてる？ 446 名前：デフォルトの名無しさん mailto:sage [2019/12/26(木) 04:04:05.93 ID:Wc5llTmi.net] >>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個移動するのはどうかと思うけど････ 447 名前：デフォルトの名無しさん mailto:sage [2019/12/26(木) 07:13:27.63 ID:rIhsLdYp.net] >>435 帰納法を使えば 具体的な手順は>>423の手順だけで ≧を示せる と言ってるだけですよ 帰納法の仮定として ・>>422の式より円盤の枚数が少ない時は動かせる ・>>422の条件より置ける置ける枚数が少ない時は>>422が成り立つ を使う 448 名前：デフォルトの名無しさん mailto:sage [2019/12/26(木) 07:22:33.88 ID:rIhsLdYp.net] >>371から>>423に進化して 本数も枚数も一般化出来た ( >>425 ) 帰納法の仮定を使って >>423の(n)は任意のn枚に出来る これによって手順の記述が対称になり 非常に簡略化出来てます 最短手順を求めるのはまた別の話で これは帰納的には求められないと思っています 449 名前：デフォルトの名無しさん mailto:sage [2019/12/26(木) 07:28:47.21 ID:rIhsLdYp.net] ちなみに >>371の式は最大枚数ではなくて Cをn枚にすることで最大になります 動かせる最大枚数はわかったので 残る 450 名前：課題は｢最短手順を求める｣のみ [] [ここ壊れてます] 451 名前：蟻人間 mailto:sage [2019/12/26(木) 15:19:10.12 ID:Npbug+/w.net] お題: 半角英数からなるユーザーIDとパスワードで認証できるアカウントのシステムを以下の要件で作る。 1.新規登録を選んでユーザーIDとパスワードとメールアドレスを入力するとアカウント登録ができる。 2. 複数アカウント対応。ユーザーIDの重複はダメ。 3. アカウント一覧を選ぶとアカウントの一覧とログイン状態が見える。 4. ログインを選んでユーザーIDとパスワードの入力が一致すればログインできる。 5. ログアウトを選べばログアウトできる。 6. パスワードを忘れたとき、アカウントの回復を選んでメルアド入力すると、メールが来てパスワードがリセットされる。 452 名前：デフォルトの名無しさん mailto:sage [2019/12/26(木) 19:06:46.63 ID:ArA1I+l7.net] >>432 　https://ideone.com/SuOGod 　 　よくある経路復元方式に変更。 　(大量な文字列のコピーが減った) 453 名前：デフォルトの名無しさん mailto:sage [2019/12/26(木) 19:20:20.20 ID:nVG7mTn1.net] >>429を少し速くした https://ideone.com/Hysp8W 454 名前：デフォルトの名無しさん mailto:sage [2019/12/26(木) 21:44:10.91 ID:nVG7mTn1.net] https://ideone.com/XFJToQ vectorを使いまわしするようにしたら速くなった 455 名前：デフォルトの名無しさん mailto:sage [2019/12/27(金) 00:16:14.43 ID:N7T+QvJX.net] https://ideone.com/tm5nPe まだ省くことができた 456 名前：蟻人間 mailto:sage [2019/12/27(金) 18:58:01.81 ID:0l4cUgpw.net] Web系もプログラミングの一種なんだけど、日本のIT教育では軽視されてるみたいなんだ。 457 名前：デフォルトの名無しさん [2019/12/27(金) 20:56:28.17 ID:JVKHwIo7.net] <('o')>ﾌｰﾝ 458 名前： mailto:sage [2019/12/27(金) 21:03:47.38 ID:9iE1xeZJ.net] >>444 web 系をはじめるには、どういう環境で学べばいいですか？ 459 名前：デフォルトの名無しさん mailto:sage [2019/12/27(金) 21:12:37.24 ID:IA42SgXa.net] https://ideone.com/3sneU6 >>440のアルゴリズムの方が速いね 460 名前：デフォルトの名無しさん mailto:sage [2019/12/27(金) 21:14:11.36 ID:IA42SgXa.net] ↑が100回 これが1回 https://ideone.com/ndU5d2 461 名前：デフォルトの名無しさん mailto:sage [2019/12/27(金) 22:14:31.51 ID:novkoLBo.net] >>426 類似問題 素数を20個使って、総合計で2020を作る。 (同じ素数を複数使ってよい） 何種類できるか(組合せで)。 -->? (同じ数字は区別しない -> ソートして数列が異なるもので1種類) ちなみに、辞書順最小が[ 2(* 18), 5, 1979] 、最大が[ 101(* 20)]になる。 ※ 2020で20個なら、まだint64_tでおさまる 462 名前：デフォルトの名無しさん mailto:sage [2019/12/27(金) 22:54:15.08 ID:IA42SgXa.net] ↑ >>429の+1を消すだけ 463 名前：デフォルトの名無しさん mailto:sage [2019/12/27(金) 22:58:27.12 ID:Wx5tgQ31.net] お題: 「Happy New Year!!」と出力するプログラムを2020年元日に投稿せよ 464 名前：デフォルトの名無しさん mailto:sage [2019/12/27(金) 23:32:30.61 ID:novkoLBo.net] >>450 やっぱり(既にできていて)、その程度なのだろう。 自分の方も、ユニーク時は更新が伝播しないように 逆順で処理していたのを、伝播するよう正順に戻すだけ。 >>449 　https://ideone.com/nQJWLb 465 名前：デフォルトの名無しさん mailto:sage [2019/12/27(金) 23:43:22.25 ID:IA42SgXa.net] >>452 お題 同じ数は4個まで 466 名前：デフォルトの名無しさん mailto:sage [2019/12/28(土) 01:41:03.72 ID:HU/ZZyYG.net] >>447のだと for (j = N - 1; j >= 0; j--) { これを for (j = 0; j < N; j++) { こう逆にすると重複の計算ができるんだね 467 名前：デフォルトの名無しさん mailto:sage [2019/12/28(土) 03:25:23 ID:HeaGj5a1.net] >>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 とする。 468 名前：デフォルトの名無しさん mailto:sage [2019/12/28(土) 03:28:09 ID:HeaGj5a1.net] 　ABCD, -, -, - 　B 469 名前：CD, -, -, 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 [] [ここ壊れてます] 470 名前：デフォルトの名無しさん mailto:sage [2019/12/28(土) 03:34:05 ID:HeaGj5a1.net] 　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 471 名前：デフォルトの名無しさん mailto:sage [2019/12/28(土) 12:49:55.64 ID:eBmyBfXD.net] いつまでハノイのメモ帳続けるんだよｗ 472 名前：デフォルトの名無しさん mailto:sage [2019/12/28(土) 16:57:29.50 ID:hZH7LPev.net] >>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 ******************** 473 名前：デフォルトの名無しさん [2019/12/28(土) 19:46:33.82 ID:mH66EenF.net] >>426の1)はRで短く書ける(先頭・末尾行は正味の実行時間計測用)。 https://ideone.com/7eV3Kh Rでは整数は32ビットまでなので、浮動小数点型(double型)で計算しているが、 double型の有効桁数は15桁なので、小数部を非表示にすれば、答である13桁の 整数は正しく表示される。 64ビット整数を扱うbit64というパッケージも一応あるが、それを使うと 正味の実行時間が4.3倍もかかってしまう。 https://ideone.com/hzr0rq 474 名前：デフォルトの名無しさん mailto:sage [2019/12/28(土) 21:25:10.79 ID:4BOt7DVD.net] >>453 >>447を使って書いた https://ideone.com/EwLCGD メモリの使用を抑えたのも書いたけど遅くなった 475 名前：デフォルトの名無しさん [2019/12/28(土) 22:48:40.84 ID:AtehPr/g.net] お題 最小値のあるインデックスから離れるほど数字が大きくなる数列があります 増加量はランダムです その数列の中から効率よく最小値を探してください 入力: 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 476 名前：デフォルトの名無しさん [2019/12/28(土) 23:28:52.09 ID:mH66EenF.net] >>462 二分探索で答えてもらいたいんだろ。 https://ideone.com/PKF7cQ 477 名前：デフォルトの名無しさん [2019/12/28(土) 23:34:06.76 ID:AtehPr/g.net] >>463 私が用意してた答えは二分探索ではありませんでした� 478 名前：ｪ二分探索でできるんですねすごいです [] [ここ壊れてます] 479 名前：デフォルトの名無しさん [2019/12/28(土) 23:38:08.54 ID:mH66EenF.net] >>463 訂正。signが抜けていた。 https://ideone.com/28YBxQ 480 名前：デフォルトの名無しさん [2019/12/28(土) 23:42:14.62 ID:mH66EenF.net] 再度訂正。1行目が消えていた。 https://ideone.com/mgNo9a 481 名前：デフォルトの名無しさん mailto:sage [2019/12/28(土) 23:45:03.69 ID:4BOt7DVD.net] 最初に思いつくのが二分探索だからそれより速い方法があるんだろうなと思った 482 名前：デフォルトの名無しさん [2019/12/29(日) 00:04:58.67 ID:Jtzyjysr.net] https://ideone.com/gcG2Ls 483 名前：デフォルトの名無しさん [2019/12/29(日) 00:15:11.87 ID:Jtzyjysr.net] https://ideone.com/Oj779u 484 名前：デフォルトの名無しさん [2019/12/29(日) 00:41:31.56 ID:wJ/DeyFk.net] >>466 最小値が複数ある場合の条件分けが抜けていた。 https://ideone.com/Lcraw3 Rのbinsearch関数は値の返し方に癖があって、条件分けを見落としやすいな。 485 名前：デフォルトの名無しさん [2019/12/29(日) 02:13:42.53 ID:2ZGuf6bc.net] >>462 Java 三分探索で2/3に範囲を狭めてく https://paiza.io/projects/NjNBWH-afFYHO5H9w8EJeQ 1/2に減らせる二分探索には敵わない 傾きを二分探索するって発想はなかったわー 486 名前：デフォルトの名無しさん [2019/12/29(日) 02:17:13.97 ID:2ZGuf6bc.net] >>468 実装の効率はパないすね、効率はそういう意味でもありましたホントです 487 名前：デフォルトの名無しさん mailto:sage [2019/12/29(日) 09:24:17.66 ID:Y3W4ZjXN.net] いやいや ただのリニア検索より遅いのはあり得ん 488 名前：デフォルトの名無しさん [2019/12/29(日) 19:39:43.67 ID:Jtzyjysr.net] でも出てる中で一番速いけど。 489 名前：デフォルトの名無しさん [2019/12/29(日) 21:33:41.90 ID:wJ/DeyFk.net] >>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 490 名前：デフォルトの名無しさん [2019/12/29(日) 21:37:04.80 ID:Jtzyjysr.net] >>475 >>469の場合だとどんな感じ？ 491 名前：デフォルトの名無しさん [2019/12/29(日) 21:41:48.80 ID:2ZGuf6bc.net] なんかすまんなみんな、ワイのせいで・・・ワイのせいで・・・ワイは悪くない 492 名前：デフォルトの名無しさん mailto:sage [2019/12/29(日) 22:06:29.15 ID:Y3W4ZjXN.net] >>462くらい乱数に法則があれば2分検索より速いアルゴリズムを作れる 例としてはイマイチ 493 名前：デフォルトの名無しさん mailto:sage [2019/12/29(日) 22:38:51.59 ID:Byl7yBSZ.net] このスレだけマジで何言ってんのか理解できない やっぱまずいよなあ、数学勉強し直さなきゃなあ 494 名前：デフォルトの名無しさん [2019/12/29(日) 22:43:46.32 ID:KptD7+e9.net] >>426 1)数百万規模でありそう。 495 名前：デフォルトの名無しさん mailto:sage [2019/12/30(月) 08:49:27.55 ID:1DW7Hzfm.net] >>475 最適化されたCとC++のSTLならCのほうが分があるということ？ 496 名前：デフォルトの名無しさん mailto:sage [2019/12/30(月) 09:13:40.00 ID:W9rqQHA3.net] 突き詰めた機械語にコンバートされるCと 汎用性のSTL どちらに分があるのか 497 名前：デフォルトの名無しさん mailto:sage [2019/12/30(月) 11:48:55.51 ID:1DW7Hzfm.net] 戦争になりそうだが、俺は膝にassertを受けちまってな 皆の力にはなれない、すまない 498 名前：デフォルトの名無しさん mailto:sage [2019/12/30(月) 13:23:07.59 ID:I3iMR+1 ] [ここ壊れてます] 499 名前：Y.net mailto: Rのsortは基数ソート使ってるらしいからその差かもしれない c++のもこのデータの場合stable_sortに変えると3倍くらい速くなった [] [ここ壊れてます] 500 名前：デフォルトの名無しさん [2019/12/30(月) 15:32:52.11 ID:fFRqMrLq.net] いいっすねー、新しいお題用意してるからちょっとまってて 501 名前：デフォルトの名無しさん [2019/12/30(月) 15:44:13.04 ID:fFRqMrLq.net] お題 四角形の縦の長さの数列と 四角形の横の長さの数列と 四角形の面積が与えられます 縦の長さと横の長さを組み合わせて 与えられた面積と一致する四角形をいくつ 作ることができるか求めてください 入力: 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? 502 名前：デフォルトの名無しさん [2019/12/30(月) 15:45:24.75 ID:fFRqMrLq.net] 195の後ろの文字化けは無視してください 195と書きたかったのです 503 名前：デフォルトの名無しさん [2019/12/30(月) 15:47:28.48 ID:fFRqMrLq.net] 入力の数列の長さが数万になってもちょっぱやで計算できるとなお良いです 504 名前：デフォルトの名無しさん mailto:sage [2019/12/30(月) 16:18:52.49 ID:pgNmBWor.net] 四角形の縦の長さの定義は？ まさか四角形＝長方形じゃないでしょ 505 名前：デフォルトの名無しさん [2019/12/30(月) 16:21:26.52 ID:fFRqMrLq.net] >>489 ではそのまさかということで 四角形とは長方形のことです！ 506 名前：デフォルトの名無しさん [2019/12/30(月) 16:26:20.78 ID:fFRqMrLq.net] 問題を書いたときは長方形以外の四角形がこの世に存在するとは思いもよらなかったので四角形と書いたのです 507 名前：デフォルトの名無しさん mailto:sage [2019/12/30(月) 18:39:14.57 ID:JZjS6BbQ.net] オーダーは n log n 問題には 数列に同じ値が複数あった場合に1個とするのか別カウントするのかという曖昧性がある 508 名前：デフォルトの名無しさん [2019/12/30(月) 18:41:24.69 ID:fFRqMrLq.net] >>492 同じ値は別カウントで良いです 509 名前：デフォルトの名無しさん mailto:sage [2019/12/30(月) 18:54:14.71 ID:JZjS6BbQ.net] 数列が整数限定 数列の数が大きい 面積が小さい なら 素因数分解っていうアプローチもあるのかな？ 510 名前：デフォルトの名無しさん [2019/12/30(月) 19:25:46.59 ID:fFRqMrLq.net] >>486 同じ値を別カウントにするとベラボーに難しいですね 同じ値は1個とカウントして良いです 511 名前：デフォルトの名無しさん [2019/12/30(月) 19:25:50.71 ID:2F+fuXCx.net] >>486 数万程度なら、Rで何の工夫もなしに素直に書いても瞬時に求められるな。 https://ideone.com/tLSpKT

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef