- 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/
- 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
- 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 で計算すればいい。 []
- [ここ壊れてます]
|
 |
