プログラミングのお題スレ 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/ 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 512 名前：デフォルトの名無しさん [2019/12/30(月) 19:28:13.92 ID:fFRqMrLq.net] >>496 マジですか・・・すごいです 513 名前：デフォルトの名無しさん [2019/12/30(月) 19:31:03.47 ID:fFRqMrLq.net] >>462 そういえばこの問題って.NETのLINQとかJavaのStreamとか 使ってソートすればたぶんヒープが使われて逐次処理が行われるんで 全部の値をソートせずに答えが求められるんじゃないかと思った ほぼ線形探索 514 名前：デフォルトの名無しさん [2019/12/30(月) 19:34:34.59 ID:2F+fuXCx.net] >>486 数列が重複要素可で、>>495の条件で求めるなら、>>496のdの右辺をunique()で囲めば良い。 515 名前：デフォルトの名無しさん mailto:sage [2019/12/30(月) 19:38:11.16 ID:JZjS6BbQ.net] >>495 アルゴリズム的にはどっちもかわらん 特定の言語で記述しにくいってことはあるかもしれないけど 516 名前：デフォルトの名無しさん [2019/12/30(月) 19:39:21.71 ID:fFRqMrLq.net] >>500 マジですか・・・ 517 名前：デフォルトの名無しさん [2019/12/30(月) 20:14:35.59 ID:2F+fuXCx.net] >>484 Rのマニュアルを調べたら確かにそういう仕様だね。sort関数のmethod引数で ソート方式を指定できるが、省略時は2^31要素未満の数値ベクトルに対しては 基数ソート、それ以外に対してはシェルソートが選択されると書かれている。 ということで、method引数を明示的に指定して実行時間を比較してみると、 基数、クイック、シェルソートがそれぞれ50.8, 45.2, 38.2ミリ秒で、基数ソートが 何故か一番遅いな。PCで実行したら基数<クイック<シェルの順だったのに。 RのクイックソートでもC++ STLのsortよりはまだ速い。https://ideone.com/g2JEPF 二分探索をCで書けば爆速で、実行時間は0.042マイクロ秒。Rの二分探索と3桁違う。 (キャッシュの影響があるのかも知れないが)。https://ideone.com/Dm65Sp Rの関数はCかFortranで書かれているものが多いが、binsearch関数はRで書かれているし、 戻り値のフラグ判定が文字列照合という非効率な処理だから、二分探索としては あまり速くない。 518 名前：デフォルトの名無しさん mailto:sage [2019/12/30(月) 20:30:55.63 ID:0ybHI6rZ.net] >>492 重複なしなら 縦の数列をハッシュテーブルに入れる 横の数値に対して... ・0 ならスキップ ・面積を横の数値で割った余りが０でないならスキップ ・面積を横の数値で割った値がハッシュテーブルになければスキップ ・カウントアップ を繰り返せばいいだけだからO(n) （要するに>>496なんだけど） 重複ありで別カウントならハッシュテーブルの代わりにディクショナリにして値に個数を入れといてカウントアップ時に縦横の個数を掛けたものを加算すればいいだけ 519 名前：デフォルトの名無しさん mailto:sage [2019/12/30(月) 20:46:19.63 ID:JZjS6BbQ.net] ハッシュテーブルの検索はオーダー1じゃないと思うんだ 520 名前：デフォルトの名無しさん mailto:sage [2019/12/30(月) 21:43:46.47 ID:0ybHI6rZ.net] >>504 実装とかによるけど大抵の実装だとほぼO(1)だよ 521 名前：デフォルトの名無しさん mailto:sage [2019/12/30(月) 22:39:47.32 ID:JZjS6BbQ.net] ほぼ1ってなんだよwww オーダー1の実装だと 値の範囲という別のオーダーが生まれる 522 名前：デフォルトの名無しさん [2019/12/30(月) 22:44:20.79 ID:fFRqMrLq.net] >>506 平均のことかと 523 名前：デフォルトの名無しさん mailto:sage [2019/12/30(月) 22:53:03.82 ID:JZjS6BbQ.net] ああ平均か 最悪値は非常に悪いよね 524 名前：デフォルトの名無しさん mailto:sage [2019/12/30(月) 22:55:25.07 ID:JZjS6BbQ.net] てっきり超巨大ハッシュテーブルを作るのかと思った 525 名前：デフォルトの名無しさん [2019/12/30(月) 22:58:46.54 ID:fFRqMrLq.net] たしかにハッシュテーブルの最悪の計算量はO(n)だけれども そうなることってマレだよ むかしVBで使われてたScripting.Dictionaryはテーブルサイズが1万固定のようで それ以上になると計算コストがバク上がりしてた 最近のライブラリだとテーブルサイズが可変になってるので問題ない あとはWebサービスに対する攻撃としてキーが衝突するデータを大量に送りつけるってのが 数年前に話題になったかな ハッシュ関数を予測してデータを作為的に作らない限り最悪の計算コストになることはないかと ハッシュテーブル使うときはO(1)で考えて良いと思う 526 名前：デフォルトの名無しさん mailto:sage [2019/12/30(月) 23:12:19.04 ID:p3QJuMJ/.net] Ruby のハッシュでは、データ数と共に、バケット数を増やしていく。 バケット数は、2 の累乗の次に現れる素数。 2^n + a, 2 <= n <= 30 8 + 3 = 11 16 + 3 = 19 32 + 5 = 37 64 + 3 = 67 128 + 3 = 131 256 + 27 = 283 512 + 9 = 521 データ数が、バケット数の5倍を超えると、ハッシュが再構成される。 再構成時には、極端に遅くなる 11 * 5 = 55 だから、データ数が56 個になると、バケット数が19 になる。 19 * 5 = 95 だから、データ数が96 個になると、バケット数が37 になる 527 名前：デフォルトの名無しさん mailto:sage [2019/12/30(月) 23:30:39.44 ID:JZjS6BbQ.net] 最近は結構インテリジェントに作られてるんだね unordered_set/map もたまには使ってみようかな 528 名前：デフォルトの名無しさん [2019/12/31(火) 07:26:10.17 ID:kRQlhKMg.net] 制約論理型言語だと変数の上限下限を自動的に切ってくれる。 529 名前：デフォルトの名無しさん mailto:sage [2019/12/31(火) 09:03:13.10 ID:hkax3Wzu.net] お題 フィボナッチ数列のn番目をF(n)とした時 F(F(80))の下位8桁を求めよ フィボナッチ数列は以下で定義される数列である F(1)=1 F(2)=1 F(n)=F(n-2)+F(n-1) 530 名前：デフォルトの名無しさん [2019/12/31(火) 10:24:38.95 ID:NKLtpqnc.net] >>514 21055810 あってるかな。 フィボナッチ数列は行列を使うアルゴリズムで 531 名前：O(log n)で計算できるもんね。外側の計算はmod100000000 で計算すればいい。 [] [ここ壊れてます] 532 名前：デフォルトの名無しさん [2019/12/31(火) 12:24:58.82 ID:5aZymNkm.net] >>515 Rは整数が32ビットまでで桁あふれするから、Juliaで書く。 F = Int64[1 1; 1 0] n = (F ^ 80)[1, 2] P = Int64[1 0; 0 1] R = F while n > 0 　　global r = n % 2 　　global n = div(n, 2) 　　if r > 0 　　　　global P = P * R .% 100000000 　　end 　　global R = R * R .% 100000000 end println(P[1, 2]) -- 実行結果 -- 21055810 533 名前：デフォルトの名無しさん [2019/12/31(火) 12:26:30.15 ID:5aZymNkm.net] >>515じゃなくて>>514だった。 534 名前：デフォルトの名無しさん [2019/12/31(火) 13:18:28.06 ID:5aZymNkm.net] >>514 Rでも多桁計算パッケージgmpを使ったら、正しく計算できた。 https://ideone.com/OY6Adr 535 名前：デフォルトの名無しさん [2019/12/31(火) 17:23:41.22 ID:NKLtpqnc.net] >>514 >>516 515です。コード上げてなかった。 https://ideone.com/SPRgPf 536 名前：513 mailto:sage [2019/12/31(火) 18:46:25.67 ID:H+c+1UtF.net] >>513 64ビットに収まるようにしたので簡単でしたかね C++ https://ideone.com/VRdN4q 537 名前：デフォルトの名無しさん mailto:sage [2019/12/31(火) 18:47:43.73 ID:H+c+1UtF.net] >>514でした すみません 538 名前：デフォルトの名無しさん mailto:sage [2019/12/31(火) 19:45:18.11 ID:5fWgt8Ro.net] >>449 https://ideone.com/nisdwQ C++。問題勘違いして全探索かいたんだよ〜。 おわらねー。Orz 539 名前：デフォルトの名無しさん [2019/12/31(火) 20:25:50.73 ID:W8YPZd1D.net] >>522 100億人に2020になる素数をプレゼント出来そうだ。 540 名前：デフォルトの名無しさん mailto:sage [2019/12/31(火) 20:58:55.61 ID:5fWgt8Ro.net] >>523 100億！！？？？マジで？？ そら手に余るわ。教えてくれてありがとう。 プレゼントするときは、「あなたに特別な2020を！」って感じか。 541 名前：デフォルトの名無しさん [2020/01/01(水) 07:48:09.89 ID:W9Zu1XGU.net] >>523 素数2個の2020は41人しかあげられない。 542 名前： mailto:sage [2020/01/01(水) 12:10:34.36 ID:WIYGoppO.net] あけおめ 543 名前：デフォルトの名無しさん mailto:sage [2020/01/01(水) 12:56:41.11 ID:WIYGoppO.net] お題 a^n + b^n + c^n = 2020 の整数解のうちnが最大の物を求めよ 544 名前： mailto:sage [2020/01/01(水) 15:06:53.67 ID:/JBKhr80.net] あけおめ〜 545 名前：デフォルトの名無しさん mailto:sage [2020/01/01(水) 15:29:53.46 ID:qVK/11PV.net] A HAPPY NEW YEAR !!! というコード。

---

---

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

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