[過去ﾛｸﾞ] プログラミングのお題スレ Part16 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
453(2): 2019/12/27(金)23:43 ID:IA42SgXa(4/4) AAS
>>452
お題
同じ数は4個まで
454: 2019/12/28(土)01:41 ID:HU/ZZyYG(1) AAS
>>447のだと
for (j = N - 1; j >= 0; j--) {
これを
for (j = 0; j < N; j++) {
こう逆にすると重複の計算ができるんだね
455: 2019/12/28(土)03:25 ID:HeaGj5a1(1/3) AAS
>>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
とする。
456: 2019/12/28(土)03:28 ID:HeaGj5a1(2/3) AAS
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)
省21
457: 2019/12/28(土)03:34 ID:HeaGj5a1(3/3) AAS
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
省16
458: 2019/12/28(土)12:49 ID:eBmyBfXD(1) AAS
いつまでハノイのメモ帳続けるんだよｗ
459: 2019/12/28(土)16:57 ID:hZH7LPev(1) AAS
>>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]
省6
460: 2019/12/28(土)19:46 ID:mH66EenF(1/4) AAS
>>426の1)はRで短く書ける(先頭・末尾行は正味の実行時間計測用)。
外部ﾘﾝｸ:ideone.com
Rでは整数は32ビットまでなので、浮動小数点型(double型)で計算しているが、
double型の有効桁数は15桁なので、小数部を非表示にすれば、答である13桁の
整数は正しく表示される。
64ビット整数を扱うbit64というパッケージも一応あるが、それを使うと
正味の実行時間が4.3倍もかかってしまう。
外部ﾘﾝｸ:ideone.com
461: 2019/12/28(土)21:25 ID:4BOt7DVD(1/2) AAS
>>453
>>447を使って書いた
外部ﾘﾝｸ:ideone.com
メモリの使用を抑えたのも書いたけど遅くなった
462(4): 2019/12/28(土)22:48 ID:AtehPr/g(1/2) AAS
お題
最小値のあるインデックスから離れるほど数字が大きくなる数列があります
増加量はランダムです
その数列の中から効率よく最小値を探してください
入力: 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
463(2): 2019/12/28(土)23:28 ID:mH66EenF(2/4) AAS
>>462
二分探索で答えてもらいたいんだろ。
外部ﾘﾝｸ:ideone.com
464: 2019/12/28(土)23:34 ID:AtehPr/g(2/2) AAS
>>463
私が用意してた答えは二分探索ではありませんでしたが二分探索でできるんですねすごいです
465: 2019/12/28(土)23:38 ID:mH66EenF(3/4) AAS
>>463 訂正。signが抜けていた。
外部ﾘﾝｸ:ideone.com
466(1): 2019/12/28(土)23:42 ID:mH66EenF(4/4) AAS
再度訂正。1行目が消えていた。
外部ﾘﾝｸ:ideone.com
467: 2019/12/28(土)23:45 ID:4BOt7DVD(2/2) AAS
最初に思いつくのが二分探索だからそれより速い方法があるんだろうなと思った
468(2): 2019/12/29(日)00:04 ID:Jtzyjysr(1/4) AAS
外部ﾘﾝｸ:ideone.com
469(1): 2019/12/29(日)00:15 ID:Jtzyjysr(2/4) AAS
外部ﾘﾝｸ:ideone.com
470: 2019/12/29(日)00:41 ID:wJ/DeyFk(1/2) AAS
>>466 最小値が複数ある場合の条件分けが抜けていた。
外部ﾘﾝｸ:ideone.com
Rのbinsearch関数は値の返し方に癖があって、条件分けを見落としやすいな。
471: 2019/12/29(日)02:13 ID:2ZGuf6bc(1/3) AAS
>>462
Java 三分探索で2/3に範囲を狭めてく
外部ﾘﾝｸ:paiza.io
1/2に減らせる二分探索には敵わない
傾きを二分探索するって発想はなかったわー
472: 2019/12/29(日)02:17 ID:2ZGuf6bc(2/3) AAS
>>468
実装の効率はパないすね、効率はそういう意味でもありましたホントです
473: 2019/12/29(日)09:24 ID:Y3W4ZjXN(1/2) AAS
いやいや
ただのリニア検索より遅いのはあり得ん
474(1): 2019/12/29(日)19:39 ID:Jtzyjysr(3/4) AAS
でも出てる中で一番速いけど。
475(2): 2019/12/29(日)21:33 ID:wJ/DeyFk(2/2) AAS
>>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)だから当たり前だが。
外部ﾘﾝｸ:ideone.com
省4
476: 2019/12/29(日)21:37 ID:Jtzyjysr(4/4) AAS
>>475
>>469の場合だとどんな感じ？
477: 2019/12/29(日)21:41 ID:2ZGuf6bc(3/3) AAS
なんかすまんなみんな、ワイのせいで・・・ワイのせいで・・・ワイは悪くない
478: 2019/12/29(日)22:06 ID:Y3W4ZjXN(2/2) AAS
>>462くらい乱数に法則があれば2分検索より速いアルゴリズムを作れる
例としてはイマイチ
479: 2019/12/29(日)22:38 ID:Byl7yBSZ(1) AAS
このスレだけマジで何言ってんのか理解できない
やっぱまずいよなあ、数学勉強し直さなきゃなあ
480: 2019/12/29(日)22:43 ID:KptD7+e9(1) AAS
>>426
1)数百万規模でありそう。
481: 2019/12/30(月)08:49 ID:1DW7Hzfm(1/2) AAS
>>475
最適化されたCとC++のSTLならCのほうが分があるということ？
482: 2019/12/30(月)09:13 ID:W9rqQHA3(1) AAS
突き詰めた機械語にコンバートされるCと
汎用性のSTL
どちらに分があるのか
483: 2019/12/30(月)11:48 ID:1DW7Hzfm(2/2) AAS
戦争になりそうだが、俺は膝にassertを受けちまってな
皆の力にはなれない、すまない
484(1): 2019/12/30(月)13:23 ID:I3iMR+1Y(1) AAS
Rのsortは基数ソート使ってるらしいからその差かもしれない
c++のもこのデータの場合stable_sortに変えると3倍くらい速くなった
485: 2019/12/30(月)15:32 ID:fFRqMrLq(1/13) AAS
いいっすねー、新しいお題用意してるからちょっとまってて
486(4): 2019/12/30(月)15:44 ID:fFRqMrLq(2/13) AAS
お題
四角形の縦の長さの数列と
四角形の横の長さの数列と
四角形の面積が与えられます
縦の長さと横の長さを組み合わせて
与えられた面積と一致する四角形をいくつ
作ることができるか求めてください
入力: 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?
487: 2019/12/30(月)15:45 ID:fFRqMrLq(3/13) AAS
195の後ろの文字化けは無視してください
195と書きたかったのです
488: 2019/12/30(月)15:47 ID:fFRqMrLq(4/13) AAS
入力の数列の長さが数万になってもちょっぱやで計算できるとなお良いです
489(1): 2019/12/30(月)16:18 ID:pgNmBWor(1) AAS
四角形の縦の長さの定義は？
まさか四角形＝長方形じゃないでしょ
490: 2019/12/30(月)16:21 ID:fFRqMrLq(5/13) AAS
>>489
ではそのまさかということで
四角形とは長方形のことです！
491: 2019/12/30(月)16:26 ID:fFRqMrLq(6/13) AAS
問題を書いたときは長方形以外の四角形がこの世に存在するとは思いもよらなかったので四角形と書いたのです
492(2): 2019/12/30(月)18:39 ID:JZjS6BbQ(1/8) AAS
オーダーは n log n
問題には
数列に同じ値が複数あった場合に1個とするのか別カウントするのかという曖昧性がある
493: 2019/12/30(月)18:41 ID:fFRqMrLq(7/13) AAS
>>492
同じ値は別カウントで良いです
494: 2019/12/30(月)18:54 ID:JZjS6BbQ(2/8) AAS
数列が整数限定
数列の数が大きい
面積が小さい
なら
素因数分解っていうアプローチもあるのかな？
495(2): 2019/12/30(月)19:25 ID:fFRqMrLq(8/13) AAS
>>486
同じ値を別カウントにするとベラボーに難しいですね
同じ値は1個とカウントして良いです
496(3): 2019/12/30(月)19:25 ID:2F+fuXCx(1/3) AAS
>>486
数万程度なら、Rで何の工夫もなしに素直に書いても瞬時に求められるな。
外部ﾘﾝｸ:ideone.com
497: 2019/12/30(月)19:28 ID:fFRqMrLq(9/13) AAS
>>496
マジですか・・・すごいです
498: 2019/12/30(月)19:31 ID:fFRqMrLq(10/13) AAS
>>462
そういえばこの問題って.NETのLINQとかJavaのStreamとか
使ってソートすればたぶんヒープが使われて逐次処理が行われるんで
全部の値をソートせずに答えが求められるんじゃないかと思った
ほぼ線形探索
499: 2019/12/30(月)19:34 ID:2F+fuXCx(2/3) AAS
>>486
数列が重複要素可で、>>495の条件で求めるなら、>>496のdの右辺をunique()で囲めば良い。
500(1): 2019/12/30(月)19:38 ID:JZjS6BbQ(3/8) AAS
>>495
アルゴリズム的にはどっちもかわらん
特定の言語で記述しにくいってことはあるかもしれないけど
501: 2019/12/30(月)19:39 ID:fFRqMrLq(11/13) AAS
>>500
マジですか・・・
502: 2019/12/30(月)20:14 ID:2F+fuXCx(3/3) AAS
>>484
Rのマニュアルを調べたら確かにそういう仕様だね。sort関数のmethod引数で
ソート方式を指定できるが、省略時は2^31要素未満の数値ベクトルに対しては
基数ソート、それ以外に対してはシェルソートが選択されると書かれている。
ということで、method引数を明示的に指定して実行時間を比較してみると、
基数、クイック、シェルソートがそれぞれ50.8, 45.2, 38.2ミリ秒で、基数ソートが
何故か一番遅いな。PCで実行したら基数<クイック<シェルの順だったのに。
RのクイックソートでもC++ STLのsortよりはまだ速い。外部ﾘﾝｸ:ideone.com
二分探索をCで書けば爆速で、実行時間は0.042マイクロ秒。Rの二分探索と3桁違う。
(キャッシュの影響があるのかも知れないが)。外部ﾘﾝｸ:ideone.com
省3
503: 2019/12/30(月)20:30 ID:0ybHI6rZ(1/2) AAS
>>492
重複なしなら
縦の数列をハッシュテーブルに入れる
横の数値に対して...
・0 ならスキップ
・面積を横の数値で割った余りが０でないならスキップ
・面積を横の数値で割った値がハッシュテーブルになければスキップ
・カウントアップ
を繰り返せばいいだけだからO(n)
（要するに>>496なんだけど）
省1
504(1): 2019/12/30(月)20:46 ID:JZjS6BbQ(4/8) AAS
ハッシュテーブルの検索はオーダー1じゃないと思うんだ
505: 2019/12/30(月)21:43 ID:0ybHI6rZ(2/2) AAS
>>504
実装とかによるけど大抵の実装だとほぼO(1)だよ
506(1): 2019/12/30(月)22:39 ID:JZjS6BbQ(5/8) AAS
ほぼ1ってなんだよwww
オーダー1の実装だと
値の範囲という別のオーダーが生まれる
507: 2019/12/30(月)22:44 ID:fFRqMrLq(12/13) AAS
>>506
平均のことかと
508: 2019/12/30(月)22:53 ID:JZjS6BbQ(6/8) AAS
ああ平均か
最悪値は非常に悪いよね
509: 2019/12/30(月)22:55 ID:JZjS6BbQ(7/8) AAS
てっきり超巨大ハッシュテーブルを作るのかと思った
510: 2019/12/30(月)22:58 ID:fFRqMrLq(13/13) AAS
たしかにハッシュテーブルの最悪の計算量はO(n)だけれども
そうなることってマレだよ
むかしVBで使われてたScripting.Dictionaryはテーブルサイズが1万固定のようで
それ以上になると計算コストがバク上がりしてた
最近のライブラリだとテーブルサイズが可変になってるので問題ない
あとはWebサービスに対する攻撃としてキーが衝突するデータを大量に送りつけるってのが
数年前に話題になったかな
ハッシュ関数を予測してデータを作為的に作らない限り最悪の計算コストになることはないかと
ハッシュテーブル使うときはO(1)で考えて良いと思う
511: 2019/12/30(月)23:12 ID:p3QJuMJ/(1) AAS
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
省4
512: 2019/12/30(月)23:30 ID:JZjS6BbQ(8/8) AAS
最近は結構インテリジェントに作られてるんだね
unordered_set/map もたまには使ってみようかな
513(1): 2019/12/31(火)07:26 ID:kRQlhKMg(1) AAS
制約論理型言語だと変数の上限下限を自動的に切ってくれる。
514(6): 2019/12/31(火)09:03 ID:hkax3Wzu(1) AAS
お題
フィボナッチ数列のn番目をF(n)とした時
F(F(80))の下位8桁を求めよ
フィボナッチ数列は以下で定義される数列である
F(1)=1
F(2)=1
F(n)=F(n-2)+F(n-1)
515(2): 2019/12/31(火)10:24 ID:NKLtpqnc(1/2) AAS
>>514
21055810
あってるかな。
フィボナッチ数列は行列を使うアルゴリズムでO(log n)で計算できるもんね。外側の計算はmod100000000 で計算すればいい。
516(1): 2019/12/31(火)12:24 ID:5aZymNkm(1/3) AAS
>>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
省7
517: 2019/12/31(火)12:26 ID:5aZymNkm(2/3) AAS
>>515じゃなくて>>514だった。
518: 2019/12/31(火)13:18 ID:5aZymNkm(3/3) AAS
>>514
Rでも多桁計算パッケージgmpを使ったら、正しく計算できた。
外部ﾘﾝｸ:ideone.com
519: 2019/12/31(火)17:23 ID:NKLtpqnc(2/2) AAS
>>514
>>516
515です。コード上げてなかった。
外部ﾘﾝｸ:ideone.com
520: 513 2019/12/31(火)18:46 ID:H+c+1UtF(1/2) AAS
>>513
64ビットに収まるようにしたので簡単でしたかね
C++
外部ﾘﾝｸ:ideone.com
521: 2019/12/31(火)18:47 ID:H+c+1UtF(2/2) AAS
>>514でした
すみません
522(1): 2019/12/31(火)19:45 ID:5fWgt8Ro(1/2) AAS
>>449
外部ﾘﾝｸ:ideone.com
C++。問題勘違いして全探索かいたんだよ〜。
おわらねー。Orz
523(2): 2019/12/31(火)20:25 ID:W8YPZd1D(1) AAS
>>522
100億人に2020になる素数をプレゼント出来そうだ。
524: 2019/12/31(火)20:58 ID:5fWgt8Ro(2/2) AAS
>>523
100億！！？？？マジで？？
そら手に余るわ。教えてくれてありがとう。
プレゼントするときは、「あなたに特別な2020を！」って感じか。
525: 2020/01/01(水)07:48 ID:W9Zu1XGU(1) AAS
>>523
素数2個の2020は41人しかあげられない。
526: 【さん吉】 2020/01/01(水)12:10 ID:WIYGoppO(1/2) AAS
あけおめ
527(1): 2020/01/01(水)12:56 ID:WIYGoppO(2/2) AAS
お題
a^n + b^n + c^n = 2020
の整数解のうちnが最大の物を求めよ
528: 【大吉】 2020/01/01(水)15:06 ID:/JBKhr80(1) AAS
あけおめ〜
529: 2020/01/01(水)15:29 ID:qVK/11PV(1) AAS
A HAPPY NEW YEAR !!!
というコード。
530: 2020/01/02(木)04:45 ID:cCzcmPOa(1) AAS
>>451
531: 2020/01/02(木)14:00 ID:2eGsq/cP(1) AAS
(´；ω；｀)
532(5): 2020/01/03(金)03:43 ID:ct9N0pK8(1/2) AAS
お題
a^3 + b^3 + c^3 = 2020 * 2
の整数解を求めよ。
533(4): 2020/01/03(金)03:49 ID:ct9N0pK8(2/2) AAS
追加
a^3 + b^3 + c^3 = 2020 / 2･2
の整数解を求めよ。
534: 2020/01/03(金)03:54 ID:pVliia9g(1/3) AAS
>>486
Kotlin
外部ﾘﾝｸ:paiza.io
こんなので良いの？単に掛け算して一致するか比較しているだけなんだけど。
オマケとして重複しないようにはしているが。
535: 2020/01/03(金)04:17 ID:pVliia9g(2/3) AAS
>>532
C
外部ﾘﾝｸ:paiza.io
どう?
536(1): 2020/01/03(金)04:18 ID:pVliia9g(3/3) AAS
>>533
最後の 2･2 の部分って何? 2.2? こっちで文字化けしてちゃんと表示されてないだけ?
537: 2020/01/03(金)09:45 ID:+RiBlMC+(1) AAS
>>536
2020 / 2･2 = 2020 / 2 * 2 = 2020
538: 2020/01/03(金)12:48 ID:3k7MKqlh(1/3) AAS
>>532
200万以下だと38通り
(並び替えも数えるとその6倍)
>>533
2020は解無し
1010は100万までには解は無い
505は100万までに18個
539: 2020/01/03(金)12:51 ID:3k7MKqlh(2/3) AAS
>>527
n乗して64bitの範囲だとn=2しか発見出来なかった
540(2): 2020/01/03(金)20:05 ID:3k7MKqlh(3/3) AAS
>>532
C
外部ﾘﾝｸ:ideone.com
38個見つけるのに1時間くらいかかりました
38個目 (1661082, 440694, -1671358)
こういうのはC/C++が得意でしょう
他の言語で出来ます？ (挑戦)
541(1): 2020/01/04(土)17:22 ID:HJ66bOYq(1/2) AAS
お題
>>514に関連して、F(F(80))の桁数を求めよ。
計算式は簡単だが…
542(1): 2020/01/04(土)17:47 ID:6lKY6ugm(1) AAS
over flow周りはあってるんだかわからん
画像ﾘﾝｸ[png]:i.imgur.com
543: 2020/01/04(土)19:01 ID:hAlxX0tq(1) AAS
Mathematica ?
544(12): 2020/01/04(土)20:28 ID:rMjoeVI8(1/2) AAS
お題: 文字列を逆順にしてコピーするreverse関数を定義せよ（既存のライブラリを使ってはならない）
545: 2020/01/04(土)20:40 ID:YRTK1M0u(1) AAS
>>544 Ruby
puts 'ABCDEF'.chars.then{|a| a.size.times.map{a.pop}}.join
# => FEDCBA
546(1): 2020/01/04(土)20:46 ID:HJ66bOYq(2/2) AAS
>>544 PowerShell
function reverse($s) {-join $s[-1..-$s.length]}
reverse 文字列を逆順にしてコピーするreverse関数を定義せよ
-- 実行結果 --
よせ義定を数関esreverるすーピコてしに順逆を列字文
547: 2020/01/04(土)21:12 ID:AqMdau2S(1) AAS
>>544 Ruby
def reverse( s ); s.chars.inject(:prepend); end
548: 2020/01/04(土)21:13 ID:rMjoeVI8(2/2) AAS
>>544 C
外部ﾘﾝｸ:ideone.com
549: 2020/01/04(土)21:26 ID:e7dEja3I(1) AAS
>>544
Java
外部ﾘﾝｸ:paiza.io
550: 2020/01/05(日)00:51 ID:Y4p4/H36(1) AAS
>>544
Kotlin
外部ﾘﾝｸ:paiza.io
Kotlin の String には reversed() という文字列順序逆転のための拡張関数が最初からあって紛らわしいので rev() という名前で自作した。
551: 2020/01/05(日)08:25 ID:h+ccWvVu(1/3) AAS
>>532
{a, b, c} = {-12, -4, 18} {-4, 2, 16} など
>>533
{a, b, c} = {-6, -2, 9} {-2, 1, 8} など
552: 2020/01/05(日)08:35 ID:OU8kozEP(1) AAS
>>544 Ruby
def rev(s)
(1..s.size).map{|i|s[-i]}.join
end
上下前次1-新書関写板覧索設栞歴
あと 450 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.036s