19/12/24 19:47:21.14 cUFUrp77.net
動かせる枚数だけですがコードにしました
URLﾘﾝｸ(ideone.com)
436:デフォルトの名無しさん
2019/12/25
437:(水) 16:51:57.78 ID:eBvDhPt7.net
438:デフォルトの名無しさん
19/12/25 19:05:13.68 LrSoTBV6.net
2) 3) は瞬時だけど
1) は難しい
出題者は出来たんだよね？
439:426
19/12/25 19:20:25.05 eBvDhPt7.net
>>427
1)は二年前の大晦日に、part9で ほぼ既出問題。
とても大きな数字になるから、
全探索しないでね、って意味で1)においたのだが……
440:デフォルトの名無しさん
19/12/25 22:46:56.00 LrSoTBV6.net
URLﾘﾝｸ(ideone.com)
441:デフォルトの名無しさん
19/12/25 22:48:16.07 LrSoTBV6.net
合ってる？
442:デフォルトの名無しさん
19/12/25 22:57:35.89 LrSoTBV6.net
辞書順最後は
{ 53, 59, 61, 67, 71, 73, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151 }
443:426
19/12/25 23:33:28.28 eBvDhPt7.net
>>429, 431 当方とおなじです。
>>426
URLﾘﾝｸ(ideone.com)
数が程々なので、まとめて手抜きの"文字列DP"をやってます。
(pypyで1秒以内で回っているのだから、真面目にやる必要ないでしょう)
444:デフォルトの名無しさん
19/12/26 01:18:40.30 rIhsLdYp.net
がんばって速くしてみたけどあまり速くならなかった
URLﾘﾝｸ(ideone.com)
445:デフォルトの名無しさん
19/12/26 01:28:39.37 rIhsLdYp.net
C++だから速いはず
だけど大差無いって事は
アルゴリズムで負けてる？
446:デフォルトの名無しさん
19/12/26 04:04:05.93 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:デフォルトの名無しさん
19/12/26 07:13:27.63 rIhsLdYp.net
>>435
帰納法を使えば
具体的な手順は>>423の手順だけで
≧を示せる
と言ってるだけですよ
帰納法の仮定として
・>>422の式より円盤の枚数が少ない時は動かせる
・>>422の条件より置ける置ける枚数が少ない時は>>422が成り立つ
を使う
448:デフォルトの名無しさん
19/12/26 07:22:33.88 rIhsLdYp.net
>>371から>>423に進化して
本数も枚数も一般化出来た
( >>425 )
帰納法の仮定を使って
>>423の(n)は任意のn枚に出来る
これによって手順の記述が対称になり
非常に簡略化出来てます
最短手順を求めるのはまた別の話で
これは帰納的には求められないと思っています
449:デフォルトの名無しさん
19/12/26 07:28:47.21 rIhsLdYp.net
ちなみに >>371の式は最大枚数ではなくて
Cをn枚にすることで最大になります
動かせる最大枚数はわかったので
残る
450:課題は｢最短手順を求める｣のみ
451:蟻人間
19/12/26 15:19:10.12 Npbug+/w.net
お題: 半角英数からなるユーザーIDとパスワードで認証できるアカウントのシステムを以下の要件で作る。
1.新規登録を選んでユーザーIDとパスワードとメールアドレスを入力するとアカウント登録ができる。
2. 複数アカウント対応。ユーザーIDの重複はダメ。
3. アカウント一覧を選ぶとアカウントの一覧とログイン状態が見える。
4. ログインを選んでユーザーIDとパスワードの入力が一致すればログインできる。
5. ログアウトを選べばログアウトできる。
6. パスワードを忘れたとき、アカウントの回復を選んでメルアド入力すると、メールが来てパスワードがリセットされる。
452:デフォルトの名無しさん
19/12/26 19:06:46.63 ArA1I+l7.net
>>432
URLﾘﾝｸ(ideone.com)
よくある経路復元方式に変更。
(大量な文字列のコピーが減った)
453:デフォルトの名無しさん
19/12/26 19:20:20.20 nVG7mTn1.net
>>429を少し速くした
URLﾘﾝｸ(ideone.com)
454:デフォルトの名無しさん
19/12/26 21:44:10.91 nVG7mTn1.net
URLﾘﾝｸ(ideone.com)
vectorを使いまわしするようにしたら速くなった
455:デフォルトの名無しさん
19/12/27 00:16:14.43 N7T+QvJX.net
URLﾘﾝｸ(ideone.com)
まだ省くことができた
456:蟻人間
19/12/27 18:58:01.81 0l4cUgpw.net
Web系もプログラミングの一種なんだけど、日本のIT教育では軽視されてるみたいなんだ。
457:デフォルトの名無しさん
19/12/27 20:56:28.17 JVKHwIo7.net
<('o')>ﾌｰﾝ
458:
19/12/27 21:03:47.38 9iE1xeZJ.net
>>444
web 系をはじめるには、どういう環境で学べばいいですか？
459:デフォルトの名無しさん
19/12/27 21:12:37.24 IA42SgXa.net
URLﾘﾝｸ(ideone.com)
>>440のアルゴリズムの方が速いね
460:デフォルトの名無しさん
19/12/27 21:14:11.36 IA42SgXa.net
↑が100回
これが1回
URLﾘﾝｸ(ideone.com)
461:デフォルトの名無しさん
19/12/27 22:14:31.51 novkoLBo.net
>>426 類似問題
素数を20個使って、総合計で2020を作る。
(同じ素数を複数使ってよい）
何種類できるか(組合せで)。 -->?
(同じ数字は区別しない -> ソートして数列が異なるもので1種類)
ちなみに、辞書順最小が[ 2(* 18), 5, 1979] 、最大が[ 101(* 20)]になる。
※ 2020で20個なら、まだint64_tでおさまる
462:デフォルトの名無しさん
19/12/27 22:54:15.08 IA42SgXa.net
↑
>>429の+1を消すだけ
463:デフォルトの名無しさん
19/12/27 22:58:27.12 Wx5tgQ31.net
お題: 「Happy New Year!!」と出力するプログラムを2020年元日に投稿せよ
464:デフォルトの名無しさん
19/12/27 23:32:30.61 novkoLBo.net
>>450
やっぱり(既にできていて)、その程度なのだろう。
自分の方も、ユニーク時は更新が伝播しないように
逆順で処理していたのを、伝播するよう正順に戻すだけ。
>>449
URLﾘﾝｸ(ideone.com)
465:デフォルトの名無しさん
19/12/27 23:43:22.25 IA42SgXa.net
>>452
お題
同じ数は4個まで
466:デフォルトの名無しさん
19/12/28 01:41:03.72 HU/ZZyYG.net
>>447のだと
for (j = N - 1; j >= 0; j--) {
これを
for (j = 0; j < N; j++) {
こう逆にすると重複の計算ができるんだね
467:デフォルトの名無しさん
19/12/28 03:25:23 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:デフォルトの名無しさん
19/12/28 03:28:09 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:デフォルトの名無しさん
19/12/28 03:34:05 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:デフォルトの名無しさん
19/12/28 12:49:55.64 eBmyBfXD.net
いつまでハノイのメモ帳続けるんだよｗ
472:デフォルトの名無しさん
19/12/28 16:57:29.50 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:デフォルトの名無しさん
19/12/28 19:46:33.82 mH66EenF.net
>>426の1)はRで短く書ける(先頭・末尾行は正味の実行時間計測用)。
URLﾘﾝｸ(ideone.com)
Rでは整数は32ビットまでなので、浮動小数点型(double型)で計算しているが、
double型の有効桁数は15桁なので、小数部を非表示にすれば、答である13桁の
整数は正しく表示される。
64ビット整数を扱うbit64というパッケージも一応あるが、それを使うと
正味の実行時間が4.3倍もかかってしまう。
URLﾘﾝｸ(ideone.com)
474:デフォルトの名無しさん
19/12/28 21:25:10.79 4BOt7DVD.net
>>453
>>447を使って書いた
URLﾘﾝｸ(ideone.com)
メモリの使用を抑えたのも書いたけど遅くなった
475:デフォルトの名無しさん
19/12/28 22:48:40.84 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:デフォルトの名無しさん
19/12/28 23:28:52.09 mH66EenF.net
>>462
二分探索で答えてもらいたいんだろ。
URLﾘﾝｸ(ideone.com)
477:デフォルトの名無しさん
19/12/28 23:34:06.76 AtehPr/g.net
>>463
私が用意してた答えは二分探索ではありませんでした�
478:ｪ二分探索でできるんですねすごいです
479:デフォルトの名無しさん
19/12/28 23:38:08.54 mH66EenF.net
>>463 訂正。signが抜けていた。
URLﾘﾝｸ(ideone.com)
480:デフォルトの名無しさん
19/12/28 23:42:14.62 mH66EenF.net
再度訂正。1行目が消えていた。
URLﾘﾝｸ(ideone.com)
481:デフォルトの名無しさん
19/12/28 23:45:03.69 4BOt7DVD.net
最初に思いつくのが二分探索だからそれより速い方法があるんだろうなと思った
482:デフォルトの名無しさん
19/12/29 00:04:58.67 Jtzyjysr.net
URLﾘﾝｸ(ideone.com)
483:デフォルトの名無しさん
19/12/29 00:15:11.87 Jtzyjysr.net
URLﾘﾝｸ(ideone.com)
484:デフォルトの名無しさん
19/12/29 00:41:31.56 wJ/DeyFk.net
>>466 最小値が複数ある場合の条件分けが抜けていた。
URLﾘﾝｸ(ideone.com)
Rのbinsearch関数は値の返し方に癖があって、条件分けを見落としやすいな。
485:デフォルトの名無しさん
19/12/29 02:13:42.53 2ZGuf6bc.net
>>462
Java 三分探索で2/3に範囲を狭めてく
URLﾘﾝｸ(paiza.io)
1/2に減らせる二分探索には敵わない
傾きを二分探索するって発想はなかったわー
486:デフォルトの名無しさん
19/12/29 02:17:13.97 2ZGuf6bc.net
>>468
実装の効率はパないすね、効率はそういう意味でもありましたホントです
487:デフォルトの名無しさん
19/12/29 09:24:17.66 Y3W4ZjXN.net
いやいや
ただのリニア検索より遅いのはあり得ん
488:デフォルトの名無しさん
19/12/29 19:39:43.67 Jtzyjysr.net
でも出てる中で一番速いけど。
489:デフォルトの名無しさん
19/12/29 21:33:41.90 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)だから当たり前だが。
URLﾘﾝｸ(ideone.com)
C++の>>468に同じデータを与えると108ミリ秒かかり、何とRのsort関数より遅い。
Rの関数はCで書かれているものが多いから、この差はつまりはCとC++のSTLの
性能差によるものだろう。
URLﾘﾝｸ(ideone.com)
490:デフォルトの名無しさん
19/12/29 21:37:04.80 Jtzyjysr.net
>>475
>>469の場合だとどんな感じ？
491:デフォルトの名無しさん
19/12/29 21:41:48.80 2ZGuf6bc.net
なんかすまんなみんな、ワイのせいで・・・ワイのせいで・・・ワイは悪くない
492:デフォルトの名無しさん
19/12/29 22:06:29.15 Y3W4ZjXN.net
>>462くらい乱数に法則があれば2分検索より速いアルゴリズムを作れる
例としてはイマイチ
493:デフォルトの名無しさん
19/12/29 22:38:51.59 Byl7yBSZ.net
このスレだけマジで何言ってんのか理解できない
やっぱまずいよなあ、数学勉強し直さなきゃなあ
494:デフォルトの名無しさん
19/12/29 22:43:46.32 KptD7+e9.net
>>426
1)数百万規模でありそう。
495:デフォルトの名無しさん
19/12/30 08:49:27.55 1DW7Hzfm.net
>>475
最適化されたCとC++のSTLならCのほうが分があるということ？
496:デフォルトの名無しさん
19/12/30 09:13:40.00 W9rqQHA3.net
突き詰めた機械語にコンバートされるCと
汎用性のSTL
どちらに分があるのか
497:デフォルトの名無しさん
19/12/30 11:48:55.51 1DW7Hzfm.net
戦争になりそうだが、俺は膝にassertを受けちまってな
皆の力にはなれない、すまない
498:デフォルトの名無しさん
19/12/30 13:23:07.59 I3iMR+1
499:Y.net
500:デフォルトの名無しさん
19/12/30 15:32:52.11 fFRqMrLq.net
いいっすねー、新しいお題用意してるからちょっとまってて
501:デフォルトの名無しさん
19/12/30 15:44:13.04 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:デフォルトの名無しさん
19/12/30 15:45:24.75 fFRqMrLq.net
195の後ろの文字化けは無視してください
195と書きたかったのです
503:デフォルトの名無しさん
19/12/30 15:47:28.48 fFRqMrLq.net
入力の数列の長さが数万になってもちょっぱやで計算できるとなお良いです
504:デフォルトの名無しさん
19/12/30 16:18:52.49 pgNmBWor.net
四角形の縦の長さの定義は？
まさか四角形＝長方形じゃないでしょ
505:デフォルトの名無しさん
19/12/30 16:21:26.52 fFRqMrLq.net
>>489
ではそのまさかということで
四角形とは長方形のことです！
506:デフォルトの名無しさん
19/12/30 16:26:20.78 fFRqMrLq.net
問題を書いたときは長方形以外の四角形がこの世に存在するとは思いもよらなかったので四角形と書いたのです
507:デフォルトの名無しさん
19/12/30 18:39:14.57 JZjS6BbQ.net
オーダーは n log n
問題には
数列に同じ値が複数あった場合に1個とするのか別カウントするのかという曖昧性がある
508:デフォルトの名無しさん
19/12/30 18:41:24.69 fFRqMrLq.net
>>492
同じ値は別カウントで良いです
509:デフォルトの名無しさん
19/12/30 18:54:14.71 JZjS6BbQ.net
数列が整数限定
数列の数が大きい
面積が小さい
なら
素因数分解っていうアプローチもあるのかな？
510:デフォルトの名無しさん
19/12/30 19:25:46.59 fFRqMrLq.net
>>486
同じ値を別カウントにするとベラボーに難しいですね
同じ値は1個とカウントして良いです
511:デフォルトの名無しさん
19/12/30 19:25:50.71 2F+fuXCx.net
>>486
数万程度なら、Rで何の工夫もなしに素直に書いても瞬時に求められるな。
URLﾘﾝｸ(ideone.com)
512:デフォルトの名無しさん
19/12/30 19:28:13.92 fFRqMrLq.net
>>496
マジですか・・・すごいです
513:デフォルトの名無しさん
19/12/30 19:31:03.47 fFRqMrLq.net
>>462
そういえばこの問題って.NETのLINQとかJavaのStreamとか
使ってソートすればたぶんヒープが使われて逐次処理が行われるんで
全部の値をソートせずに答えが求められるんじゃないかと思った
ほぼ線形探索
514:デフォルトの名無しさん
19/12/30 19:34:34.59 2F+fuXCx.net
>>486
数列が重複要素可で、>>495の条件で求めるなら、>>496のdの右辺をunique()で囲めば良い。
515:デフォルトの名無しさん
19/12/30 19:38:11.16 JZjS6BbQ.net
>>495
アルゴリズム的にはどっちもかわらん
特定の言語で記述しにくいってことはあるかもしれないけど
516:デフォルトの名無しさん
19/12/30 19:39:21.71 fFRqMrLq.net
>>500
マジですか・・・
517:デフォルトの名無しさん
19/12/30 20:14:35.59 2F+fuXCx.net
>>484
Rのマニュアルを調べたら確かにそういう仕様だね。sort関数のmethod引数で
ソート方式を指定できるが、省略時は2^31要素未満の数値ベクトルに対しては
基数ソート、それ以外に対してはシェルソートが選択されると書かれている。
ということで、method引数を明示的に指定して実行時間を比較してみると、
基数、クイック、シェルソートがそれぞれ50.8, 45.2, 38.2ミリ秒で、基数ソートが
何故か一番遅いな。PCで実行したら基数<クイック<シェルの順だったのに。
RのクイックソートでもC++ STLのsortよりはまだ速い。URLﾘﾝｸ(ideone.com)
二分探索をCで書けば爆速で、実行時間は0.042マイクロ秒。Rの二分探索と3桁違う。
(キャッシュの影響があるのかも知れないが)。URLﾘﾝｸ(ideone.com)
Rの関数はCかFortranで書かれているものが多いが、binsearch関数はRで書かれているし、
戻り値のフラグ判定が文字列照合という非効率な処理だから、二分探索としては
あまり速くない。
518:デフォルトの名無しさん
19/12/30 20:30:55.63 0ybHI6rZ.net
>>492
重複なしなら
縦の数列をハッシュテーブルに入れる
横の数値に対して...
・0 ならスキップ
・面積を横の数値で割った余りが０でないならスキップ
・面積を横の数値で割った値がハッシュテーブルになければスキップ
・カウントアップ
を繰り返せばいいだけだからO(n)
（要するに>>496なんだけど）
重複ありで別カウントならハッシュテーブルの代わりにディクショナリにして値に個数を入れといてカウントアップ時に縦横の個数を掛けたものを加算すればいいだけ
519:デフォルトの名無しさん
19/12/30 20:46:19.63 JZjS6BbQ.net
ハッシュテーブルの検索はオーダー1じゃないと思うんだ
520:デフォルトの名無しさん
19/12/30 21:43:46.47 0ybHI6rZ.net
>>504
実装とかによるけど大抵の実装だとほぼO(1)だよ
521:デフォルトの名無しさん
19/12/30 22:39:47.32 JZjS6BbQ.net
ほぼ1ってなんだよwww
オーダー1の実装だと
値の範囲という別のオーダーが生まれる
522:デフォルトの名無しさん
19/12/30 22:44:20.79 fFRqMrLq.net
>>506
平均のことかと
523:デフォルトの名無しさん
19/12/30 22:53:03.82 JZjS6BbQ.net
ああ平均か
最悪値は非常に悪いよね
524:デフォルトの名無しさん
19/12/30 22:55:25.07 JZjS6BbQ.net
てっきり超巨大ハッシュテーブルを作るのかと思った
525:デフォルトの名無しさん
19/12/30 22:58:46.54 fFRqMrLq.net
たしかにハッシュテーブルの最悪の計算量はO(n)だけれども
そうなることってマレだよ
むかしVBで使われてたScripting.Dictionaryはテーブルサイズが1万固定のようで
それ以上になると計算コストがバク上がりしてた
最近のライブラリだとテーブルサイズが可変になってるので問題ない
あとはWebサービスに対する攻撃としてキーが衝突するデータを大量に送りつけるってのが
数年前に話題になったかな
ハッシュ関数を予測してデータを作為的に作らない限り最悪の計算コストになることはないかと
ハッシュテーブル使うときはO(1)で考えて良いと思う
526:デフォルトの名無しさん
19/12/30 23:12:19.04 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:デフォルトの名無しさん
19/12/30 23:30:39.44 JZjS6BbQ.net
最近は結構インテリジェントに作られてるんだね
unordered_set/map もたまには使ってみようかな
528:デフォルトの名無しさん
19/12/31 07:26:10.17 kRQlhKMg.net
制約論理型言語だと変数の上限下限を自動的に切ってくれる。
529:デフォルトの名無しさん
19/12/31 09:03:13.10 hkax3Wzu.net
お題
フィボナッチ数列のn番目をF(n)とした時
F(F(80))の下位8桁を求めよ
フィボナッチ数列は以下で定義される数列である
F(1)=1
F(2)=1
F(n)=F(n-2)+F(n-1)
530:デフォルトの名無しさん
19/12/31 10:24:38.95 NKLtpqnc.net
>>514
21055810
あってるかな。
フィボナッチ数列は行列を使うアルゴリズムで
531:O(log n)で計算できるもんね。外側の計算はmod100000000 で計算すればいい。
532:デフォルトの名無しさん
19/12/31 12:24:58.82 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:デフォルトの名無しさん
19/12/31 12:26:30.15 5aZymNkm.net
>>515じゃなくて>>514だった。
534:デフォルトの名無しさん
19/12/31 13:18:28.06 5aZymNkm.net
>>514
Rでも多桁計算パッケージgmpを使ったら、正しく計算できた。
URLﾘﾝｸ(ideone.com)
535:デフォルトの名無しさん
19/12/31 17:23:41.22 NKLtpqnc.net
>>514
>>516
515です。コード上げてなかった。
URLﾘﾝｸ(ideone.com)
536:513
19/12/31 18:46:25.67 H+c+1UtF.net
>>513
64ビットに収まるようにしたので簡単でしたかね
C++
URLﾘﾝｸ(ideone.com)
537:デフォルトの名無しさん
19/12/31 18:47:43.73 H+c+1UtF.net
>>514でした
すみません
538:デフォルトの名無しさん
19/12/31 19:45:18.11 5fWgt8Ro.net
>>449
URLﾘﾝｸ(ideone.com)
C++。問題勘違いして全探索かいたんだよ～。
おわらねー。Orz
539:デフォルトの名無しさん
19/12/31 20:25:50.73 W8YPZd1D.net
>>522
100億人に2020になる素数をプレゼント出来そうだ。
540:デフォルトの名無しさん
19/12/31 20:58:55.61 5fWgt8Ro.net
>>523
100億！！？？？マジで？？
そら手に余るわ。教えてくれてありがとう。
プレゼントするときは、「あなたに特別な2020を！」って感じか。
541:デフォルトの名無しさん
20/01/01 07:48:09.89 W9Zu1XGU.net
>>523
素数2個の2020は41人しかあげられない。
542:
20/01/01 12:10:34.36 WIYGoppO.net
あけおめ
543:デフォルトの名無しさん
20/01/01 12:56:41.11 WIYGoppO.net
お題
a^n + b^n + c^n = 2020
の整数解のうちnが最大の物を求めよ
544:
20/01/01 15:06:53.67 /JBKhr80.net
あけおめ～
545:デフォルトの名無しさん
20/01/01 15:29:53.46 qVK/11PV.net
A HAPPY NEW YEAR !!!
というコード。
546:デフォルトの名無しさん
20/01/02 04:45:53.28 cCzcmPOa.net
>>451
547:デフォルトの名無しさん
20/01/02 14:00:53.09 2eGsq/cP.net
(´；ω；｀)
548:デフォルトの名無しさん
20/01/03 03:43:04.42 ct9N0pK8.net
お題
a^3 + b^3 + c^3 = 2020 * 2
の整数解を求めよ。
549:デフォルトの名無しさん
20/01/03 03:49:51.76 ct9N0pK8.net
追加
a^3 + b^3 + c^3 = 2020 / 2･2
の整数解を求めよ。
550:デフォルトの名無しさん
20/01/03 03:54:35.20 pVliia9g.net
>>486
Kotlin
URLﾘﾝｸ(paiza.io)
こんなので良いの？単に掛け算して一致するか比較しているだけなんだけど。
オマケとして重複しないようにはしているが。
551:デフォルトの名無しさん
20/01/03 04:17:21.42 pVliia9g.net
>>532
C
URLﾘﾝｸ(paiza.io)
どう?
552:デフォルトの名無しさん
20/01/03 04:18:44.02 pVliia9g.net
>>533
最後の 2･2 の部分って何? 2.2? こっちで文字化けしてちゃんと表示されてないだけ?
553:デフォルトの名無しさん
20/01/03 09:45:42.54 +RiBlMC+.net
>>536
2020 / 2･2 = 2020 / 2 * 2 = 2020
554:デフォルトの名無しさん
20/01/03 12:48:37.25 3k7MKqlh.net
>>532
200万以下だと38通り
(並び替えも数えるとその6倍)
>>533
2020は解無し
1010は100万までには解は無い
505は100万までに18個
555:デフォルトの名無しさん
20/01/03 12:51:02.88 3k7MKqlh.net
>>527
n乗して64bitの範囲だとn=2しか発見出来なかった
556:デフォルトの名無しさん
20/01/03 20:05:33.33 3k7MKqlh.net
>>532
C
URLﾘﾝｸ(ideone.com)
38個見つけるのに1時間くらいかかりました
38個目 (1661082, 440694, -1671358)
こういうのはC/C++が得意でしょう
他の言語で出来ます？ (挑戦)
557:デフォルトの名無しさん
20/01/04 17:22:50.50 HJ66bOYq.net
お題
>>514に関連して、F(F(80))の桁数を求めよ。
計算式は簡単だが…
558:デフォルトの名無しさん
20/01/04 17:47:47.60 6lKY6ugm.net
over flow周りはあってるんだかわからん
URLﾘﾝｸ(i.imgur.com)
559:デフォルトの名無しさん
20/01/04 19:01:02.66 hAlxX0tq.net
Mathematica ?
560:デフォルトの名無しさん
20/01/04 20:28:18.17 rMjoeVI8.net
お題: 文字列を逆順にしてコピーするreverse関数を定義せよ（既存のライブラリを使ってはならない）
561:デフォルトの名無しさん
20/01/04 20:40:17.01 YRTK1M0u.net
>>544 Ruby
puts 'ABCDEF'.chars.then{|a| a.size.times.map{a.pop}}.join
# => FEDCBA
562:デフォルトの名無しさん
20/01/04 20:46:16.21 HJ66bOYq.net
>>544 PowerShell
function reverse($s) {-join $s[-1..-$s.length]}
reverse 文字列を逆順にしてコピーするreverse関数を定義せよ
-- 実行結果 --
よせ義定を数関esreverるすーピコてしに順逆を列字文
563:デフォルトの名無しさん
20/01/04 21:12:58.70 AqMdau2S.net
>>544 Ruby
def reverse( s ); s.chars.inject(:prepend); end
564:デフォルトの名無しさん
20/01/04 21:13:39.03 rMjoeVI8.net
>>544 C
URLﾘﾝｸ(ideone.com)
565:デフォルトの名無しさん
20/01/04 21:26:02.66 e7dEja3I.net
>>544
Java
URLﾘﾝｸ(paiza.io)
566:デフォルトの名無しさん
20/01/05 00:51:01.04 Y4p4/H36.net
>>544
Kotlin
URLﾘﾝｸ(paiza.io)
Kotlin の String には reversed() という文字列順序逆転のための拡張関数が最初からあって紛らわしいので rev() という名前で自作した。
567:デフォルトの名無しさん
20/01/05 08:25:52.70 h+ccWvVu.net
>>532
{a, b, c} = {-12, -4, 18} {-4, 2, 16} など
>>533
{a, b, c} = {-6, -2, 9} {-2, 1, 8} など
568:デフォルトの名無しさん
20/01/05 08:35:04.57 OU8kozEP.net
>>544 Ruby
def rev(s)
(1..s.size).map{|i|s[-i]}.join
end
569:デフォルトの名無しさん
20/01/05 11:04:36.67 Z8HxF2cT.net
>>544 Common Lisp
URLﾘﾝｸ(ideone.com)
URLﾘﾝｸ(ideone.com)
570:デフォルトの名無しさん
20/01/05 15:25:24.03 +tGOF19X.net
>>544 Python
def reverse(s):
return s[::-1]
571:デフォルトの名無しさん
20/01/05 16:01:41.83 8nvrboOv.net
>>540
こういうのを見ると我々は離散数学についてはほぼ無力と思う。
572:デフォルトの名無しさん
20/01/05 17:02:46.74 x729cdax.net
>>555
勉強しとけ
573:デフォルトの名無しさん
20/01/05 21:49:56.17 2Fq0AHrI.net
>>544 R
URLﾘﾝｸ(ideone.com)
>>546のPowerShellと違って、U+10000以上の文字が含まれていても正しく逆順にできる。
574:デフォルトの名無しさん
20/01/05 21:52:10.17 2Fq0AHrI.net
>>542
仮数部も指数部も間違っている。整数で1の位まで正確に求められるよ。
575:デフォルトの名無しさん
20/01/05 22:31:31.58 h+ccWvVu.net
>>540 ｻﾝｸｽ
>>532 の解
{13, 11, 8}
{15, 9, -4}
{8, 1, -2} * 2
{9, -2, -6} * 2
{16, -6, -15} * 2
{74, -23, -73}
{43, -27, -39} * 2
{171, -75, -166}
{169, 64, -172} * 2
{516, 93, -517}
{414, 385, -504} * 2
{530, 337, -572}
{1098, 939, -1291}
{1290, 171, -1291}
{1626, -957, -1507}
{2251, -712, -2227}
{3107, -587, -3100}
{3299, 1018, -3331}
{3509, -2525, -3004}
{4022, -3163, -3221}
{2673, 1114, -2736} * 2
{13571, -9259, -11948}
{15291, -8419, -14388}
{10102, 674, -10103} * 2
{43943, 28524, -47631}
{23689, -3382, -23666} * 2 など。
576:デフォルトの名無しさん
20/01/05 22:41:01.23 h+ccWvVu.net
>>533 の解
{8, 1, -2}
{9, -2, -6}
{16, -6, -15}
{43, -27, -39}
{169, 64, -172}
{414, 385, -504}
{530, 337, -572}
{2673, 1114, -2736}
{10102, 674, -10103}
{23689, -3382, -23666}
･･･ ･･･
{830541, 220347, -835679} など。
577:デフォルトの名無しさん
20/01/05 22:48:30.69 bLPoA6E7.net
>>541
C++
URLﾘﾝｸ(ideone.com.VJk9QA)
倍精度だと微妙に精度が足りないので
擬似4倍精度で計算してみた
4倍精度や多倍長が使える言語やライブラリを使えば一瞬で書けるんだけど
578:デフォルトの名無しさん
20/01/05 22:49:34.33 bLPoA6E7.net
↑
URLﾘﾝｸ(ideone.com)
でした
579:デフォルトの名無しさん
20/01/05 23:29:51.01 2Fq0AHrI.net
>>562
正解。
Rには多倍長浮動小数点パッケージRmpfrがあるので、120ビット精度での計算をさっと書ける。
多倍長整数パッケージgmpにはフィボナッチ数列の第n項を求める関数があるので、第80項を
自分で求める必要すらない。
URLﾘﾝｸ(ideone.com)
C/C++にもlong double型があるので楽勝!と思っていると罠に嵌まる。Visual C++では
long doubleは移植性（単にコンパイルが通るという意味で）のために定義されているだけで、
double精度しかないので使えない。GNU C++ではlong doubleが本当のlong doubleなので使える。
URLﾘﾝｸ(ideone.com)
これをVisual C++やGNU Cで実行すると、1の位が2大きい不正確な値が表示されてしまう。
URLﾘﾝｸ(ideone.com)
580:デフォルトの名無しさん
20/01/05 23:41:09.00 2Fq0AHrI.net
GNU C++にも罠があって、URLﾘﾝｸ(ideone.com) はideoneでは結果が正しく
表示されているが、Windows版でコンパイルすると「-0桁」になってしまう。
printfの%Lf書式指定子が何故か正常に機能しないようなので、long longに変換して
%lld書式指定子を使う必要がある。
581:デフォルトの名無しさん
20/01/05 23:58:45.24 Z3Lsb/Mg.net
>>562は擬似4倍精度の四則演算やルートがコンパクトにまとまっており参考になるかと思います
logは手抜きですが
582:デフォルトの名無しさん
20/01/06 00:24:13.90 MKFPBGLf.net
x87の80bit形式久々に聞いた
intelの失敗仕様
本当のlong doubleって言ったら128bitの事だと思う
583:デフォルトの名無しさん
20/01/07 12:16:08 lAASQTDH.net
本当の？
584:デフォルトの名無しさん
20/01/07 13:02:38.21 PuPIfAOU.net
大きさと精度が一致しないということでは。
例えば、16ビット整数の加算において255+1で桁あふれが発生するのは、勘弁してほしい。
16ビット整数であれば精度も16ビットあってほしい。
585:デフォルトの名無しさん
20/01/07 13:13:00.08 4oL1Xwrc.net
intelの拡張小数は箱も中身も80bitだぞ
隠れた1bitも隠さないから中身は79bitとも言えるかもしれないけど
586:デフォルトの名無しさん
20/01/07 13:43:12.96 PuPIfAOU.net
GCCのlong doubleは128ビットあるから。
587:デフォルトの名無しさん
20/01/07 22:24:41.07 Y9qs9jpB.net
ひさびさにx87命令を使ってみた
masm形式なのでideoneでは動作しませんが
URLﾘﾝｸ(ideone.com)
588:デフォルトの名無しさん
20/01/07 22:38:44.27 Y9qs9jpB.net
↑の出力結果
4893806799921043 (4893806799921042 + 0.855469)
丸める前の正確な値は
4893806799921042.8564973677594677....
なので小数第二位まで合っています
80bitでもギリギリって感じ
2進数だと
上位62bitまで正確、下位2bitが計算誤差
ということになります
589:デフォルトの名無しさん
20/01/07 23:09:32 Y9qs9jpB.net
URLﾘﾝｸ(pc.watch.impress.co.jp)
590:デフォルトの名無しさん
20/01/08 17:55:41.24 E2HYW9Z+.net
お題
フィボナッチ数列のn番目をF(n)とした時
F(F(F(80)))の下位4桁を求めよ
フィボナッチ数列は以下で定義される数列である
F(1)=1
F(2)=1
F(n)=F(n-2)+F(n-1)
591:デフォルトの名無しさん
20/01/08 18:47:53.52 bVQLyL/p.net
フィフィフィボナッチ数列はお腹いっぱい
592:
20/01/08 19:48:23.85 npJkZznC.net
>>571
x87 すごくいいです！私も 9801FA に i487SX をようやく搭載して準備完了です！
593:デフォルトの名無しさん
20/01/08 20:00:11.84 naqRCa+g.net
お前は昭和何年からタイムスリップしてきたんだ
594:デフォルトの名無しさん
20/01/08 20:33:31.36 DEoUiUkq.net
>>574
R
URLﾘﾝｸ(ideone.com)
595:デフォルトの名無しさん
20/01/08 21:16:17.44 E2HYW9Z+.net
正解
C++
URLﾘﾝｸ(ideone.com)
596:デフォルトの名無しさん
20/01/08 23:38:33.13 3Vg9kR1l.net
>>544 Perl5
use feature qw{say signatures};
sub reverse($s) {
map {substr $s, -$_, 1} 1..length $s;
}
say &reverse('reverse');
597:デフォルトの名無しさん
20/01/10 10:41:25.62 lJ/gG0sx.net
お題：自分用expm1()的なもの。底はe以外でも良い。不正な引数でのエラー処理は
考慮しなくても良い。
598:デフォルトの名無しさん
20/01/10 13:20:18.79 KXQq2+DU.net
目的が高精度なのかSIMDなのか単に出題者が勉強したいだけなのか
もしかしてx87命令を使わせたい？
599:デフォルトの名無しさん
20/01/10 20:53:23.97 1usNcOvE.net
>>581
expm1()って何？
600:デフォルトの名無しさん
20/01/10 21:01:53.36 jjOShzcG.net
エキスペディション・マグニチュードワンのことやろな
601:581
20/01/10 22:06:13.03 lJ/gG0sx.net
>>582
SIMDやx87命令は考えてませんでした。
四則演算とexpm1()以外のライブラリ関数は使用可って事で。
やっぱし無難にテイラー展開で求めるのが楽？
>>583
例えば
URLﾘﾝｸ(linuxjm.osdn.jp)
602:デフォルトの名無しさん
20/01/10 22:10:45.27 lApN4p1F.net
四則演算も使ったらダメなのかい
603:581
20/01/10 22:42:31.47 lJ/gG0sx.net
>>586
訂正：
四則演算と、「expm1()以外の」ライブラリ関数は使用可
604:デフォルトの名無しさん
20/01/11 06:32:12.11 wIXPHQcF.net
出題者が方法を知りたいだけだよね？
なら質問スレ/宿題スレの方が適切
605:デフォルトの名無しさん
20/01/11 09:22:26.15 R1f0qLP3.net
お題
素数番目の素数をスーパー素数と言う。
スーパー素数の最初の100個を求める。
606:デフォルトの名無しさん
20/01/11 10:27:02.77 LQrvWU7L.net
>>589 Ruby 2.7.0
require 'Prime'
p Prime.take(100).then{|p| Prime.take(p.last).select.with_index{p.include?(-~_2)}}
# => [3, 5, 7, [中略], 3761, 3911]
607:デフォルトの名無しさん
20/01/11 10:31:32.27 LQrvWU7L.net
typo
# => [3, 5, 11, 17, 31, [中略], 3733, 3761, 3911]
608:デフォルトの名無しさん
20/01/11 10:52:09.93 VG9fEjGe.net
お題
5の倍数の素数を5の倍数素数という
5の倍数素数を全て求めよ
609:デフォルトの名無しさん
20/01/11 11:10:43.29 V+Dyph4l.net
5の倍数の素数ってどういうことですか？
文字通りの意味なら5だけだと思うんですけど
610:デフォルトの名無しさん
20/01/11 13:10:43.10 JM9/51Sk.net
>>544 Perl4
use feature qw{say signatures};
sub rev($s) {
$s ne '' and substr ($s, -1, 1, '') . rev($s)
}
say rev('string
611:'); てす
612:デフォルトの名無しさん
20/01/11 13:14:26.71 JM9/51Sk.net
>>594 Perl5 だった…orz
しかし、このソースの「substr (」のrと(の間のスペース文字を省くと
スレへの書き込みで
HTTP/1.1 403 Forbidden
が起きて書き込めなかったのは謎…
613:デフォルトの名無しさん
20/01/11 14:01:21.01 M68szGrA.net
>>592
echo 5
614:デフォルトの名無しさん
20/01/11 20:08:39.02 go77StkR.net
お題
20200111の階乗を素因数分解したとき、すべての因数の積は20200111の階乗だが、
すべての因数の和は何か。
615:デフォルトの名無しさん
20/01/11 20:55:04.41 r5wulSj/.net
ナベアツ理論か。
616:デフォルトの名無しさん
20/01/12 00:39:46.42 PW2KE/yt.net
>>595
書き込めないコマンドは、一杯ある。
「ｌｓ －ｌ」とか
5ch は、特定の命令によって、表示の見た目を変えることができるから、
単に、表示する文字列に変換するだけじゃなくて、
投稿されたテキストから、命令を抽出したりしているから、
バグりそうなテキストを排除しているのだろう
617:デフォルトの名無しさん
20/01/12 10:30:24.93 Cuf7XVQy.net
>>597
C++
URLﾘﾝｸ(ideone.com)
618:デフォルトの名無しさん
20/01/12 16:28:53.41 Svv4a/Ag.net
お題: バイナリ―サーチを実装せよ（自分の記憶だけで書かなければならない）
619:デフォルトの名無しさん
20/01/12 16:52:57.01 qRMFtMw7.net
>>601
Java
URLﾘﾝｸ(paiza.io)
620:デフォルトの名無しさん
20/01/12 17:33:54.06 kqg5PnqA.net
>>601 Ruby
def bs(ary, &cond)
return ary[0] && cond.call(ary[0]) ? ary[0] : ary[1] && cond.call(ary[1]) ? ary[1] : nil if ary.size < 3
mid = ary.size / 2
bs(ary[cond.call(ary[mid]) ? 0..mid : mid + 1..-1], &cond)
end
p bs([1,3,5,7,9]){|i| i > 0} # => 1
p bs([1,3,5,7,9]){|i| i > 3} # => 5
p bs([1,3,5,7,9]){|i| i > 9} # => nil
621:
20/01/12 17:39:35.02 ZvwnN6DP.net
>>601
C++
ｽﾚﾘﾝｸ(tech板:33番)
std::set<int> の再実装にて、内部にバイナリーサーチを含んでいます
622:
20/01/12 17:41:03.57 ZvwnN6DP.net
>>601
＞（自分の記憶だけで書かなければならない）
これは重要かつ役に立つ訓練のしかたですね、この前は pthread の mutex と cond が理解できているかどうかを、この縛りのもとにコードを書いて試みました
623:デフォルトの名無しさん
20/01/12 18:20:53.87 Xff8C4Cf.net
>（自分の記憶だけで書かなければならない）
お題は全てそういうものだと思ってたが
みんなカンニングして回答してるの？
624:デフォルトの名無しさん
20/01/12 19:59:45.88 qRMFtMw7.net
お題1
10ビットの乱数を10個作成して
2進数に変換して出力してください
10ビットに満たない数は0埋めしてください
例)
1101101110
1000100011
0100111001
1110000001
1001001100
0010001111
1111001000
1010110111
1100001001
0100110111
お題2
縦方向、または、横方向に1が連続しているところを調べて
最も1が連続しているところの1の数を出力してください
ビット数や乱数の数が増えてもちょっぱやで処理できるとなお良いです
625:デフォルトの名無しさん
20/01/12 20:38:11.83 xWFTg64o.net
>>600
正解。あなたには簡単すぎただろうが。
Rで書いた解答例はPCでは2秒台で実行できたのに、ideoneでは制限時間5秒以内に
終わらなかったので、C++で書いた方を貼る。URLﾘﾝｸ(ideone.com)
>>600とほぼ同じだが、掛け算が減る分だけ速いな。
626:デフォルトの名無しさん
20/01/12 21:27:08.47 xWFTg64o.net
>>607
R
URLﾘﾝｸ(ideone.com)
627:デフォルトの名無しさん
20/01/12 21:44:57.86 qRMFtMw7.net
>>609
ありがとうございます、そして申し訳ないです
11
11
こうなってたら4と出力してほしくて
連続じゃないですね、隣接といえばよかったかもしれません
縦方向、横方向に1が隣接してる領域のうち最大の領域の1の数を出力して欲しいのです
628:デフォルトの名無しさん
20/01/12 21:45:02.91 xWFTg64o.net
>>607
ビット数と乱数の数を別々に指定できるように訂正
URLﾘﾝｸ(ideone.com)
629:デフォルトの名無しさん
20/01/12 21:48:51.97 qRMFtMw7.net
すみません・・・平にご容赦いただきたく
630:デフォルトの名無しさん
20/01/12 21:48:57.49 xWFTg64o.net
>>610
隣接している領域は矩形でなければいけないのか、そうでなくても良いのか。例えば、
1110
0110
0111
は前者なら6個で、後者なら8個になる。
631:デフォルトの名無しさん
20/01/12 21:52:58.77 qRMFtMw7.net
>>613
矩形じゃなくていいです8個パターンです！
632:デフォルトの名無しさん
20/01/13 04:22:53 5GjUS2iX.net
質問なら質問スレに
宿題なら宿題スレに
回答を用意してない出題は禁止
633:デフォルトの名無しさん
20/01/13 04:47:28.11 5GjUS2iX.net
昔ながらのPAINTアルゴリズム
検索すれば色々と出てくるよ
634:デフォルトの名無しさん
20/01/13 05:51:52.90 9cAJpR6a.net
>>589 J
smoutput 10 10 $ p: <: p: i.100
実行結果
3 5 11 17 31 41 59 67 83 109
127 157 179 191 211 241 277 283 331 353
367 401 431 461 509 547 563 587 599 617
709 739 773 797 859 877 919 967 991 1031
1063 1087 1153 1171 1201 1217 1297 1409 1433 1447
1471 1499 1523 1597 1621 1669 1723 1741 1787 1823
1847 1913 2027 2063 2081 2099 2221 2269 2341 2351
2381 2417 2477 2549 2609 2647 2683 2719 2749 2803
2897 2909 3001 3019 3067 3109 3169 3229 3259 3299
3319 3407 3469 3517 3559 3593 3637 3733 3761 3911
635:デフォルトの名無しさん
20/01/13 09:11:38.57 a0NWv3WS.net
>>607はAOJにあった島の数の問題じゃないの
そうじゃなくてもぷよぷよは大抵コレでしょ
636:デフォルトの名無しさん
20/01/13 12:20:35.97 AM9JqLhx.net
>>607
>>615だそうだが、既にほぼ書いてしまっていたから、完成させたのを載せる。
R
URLﾘﾝｸ(ideone.com)
637:デフォルトの名無しさん
20/01/13 14:02:08.92 7B3b+WrT.net
>>607
Java
URLﾘﾝｸ(paiza.io)
回答は一応用意してました
みんなUnionFind大好きだと思ったんだけど
638:デフォルトの名無しさん
20/01/13 18:55:55.99 7n+Qr/32.net
>>566
>>569
8087は、第3の実数フォーマット、一時実数を許している点でユニークである。
このフォーマットは、(符号が1ビット)、指数が15ビットで、有効数字が64ビットである。
このフォーマットで格納されている数値は、拡張精度数と言われている。
単精度および倍精度実数と異なり、一時実数は入力および出力値を表わすことを意図していない。
････(中略)･････
それでは、何故80ビットではなく4倍精度すなわち128ビットを一時実数に使わなかったのか。
1つの理由は、4倍精度は少なくとも性能(速度)が半分になることである。
他の理由は、4倍精度を基本フォーマットとして用いると、中間結果のためにより長いフォーマットが必要となることである。
(後略)
・出典
J.F.パーマー・S.P.モース(著)「8087入門」啓学出版 (1985/Feb) 御牧 義 (訳)
639:2900円 第2章 データフォーマット、p.19-20
640:デフォルトの名無しさん
20/01/13 19:02:27.52 7n+Qr/32.net
John F. Palmer, Ph.D. は8087の設計者、
Stephen P. Morse, Ph.D. は8086の設計者だそうな。
641:デフォルトの名無しさん
20/01/13 19:38:23.04 cBNIohlK.net
x87で遊んでた頃は
将来は4倍精度とか8倍精度とかが当たり前になると思ってたけど
まさか単精度や半精度の時代になるとは
642:デフォルトの名無しさん
20/01/14 21:06:38.50 vjAz2zAO.net
>>581
AVX2 & FMA で作ってみました
URLﾘﾝｸ(ideone.com)
範囲チェックはしてません
643:デフォルトの名無しさん
20/01/14 21:13:25.69 vjAz2zAO.net
20命令で4個のdoubleのexpm1の計算が出来ます
8パラにしてレイテンシを隠蔽すれば
1個あたり2.5クロックくらい
644:デフォルトの名無しさん
20/01/15 12:05:09.83 z1LU+PP1.net
将来、行列演算もFPU化されると、逆行列の桁落ちが問題になるだろうな････
それを見越して、入出力は64bitのまま内部演算だけ80bitにしたんぢゃね？
645:デフォルトの名無しさん
20/01/15 13:12:03.91 BnAK3ul/.net
思想がどんなに優れてても使われなきゃしょうがない
レジスタが8個しか無いから内部だけ80bitでもほとんど精度改善にならないし
メモリに80bit保存するのも使いにくい
互換性の問題もあって
コンパイラや最適化で値がかわってしまうのも都合が悪い
だから演算にx87命令を使ったとしても内部64bit精度がデフォ
x87全盛期に作られたSuperPIも64bit精度の演算を使ってる
80bit精度で計算すれば速度アップ出来るにも関わらず
646:デフォルトの名無しさん
20/01/15 17:38:16 xp2qVCg5.net
>>589 Ruby
require 'prime'
a=Prime.take(100)
p ([0]+Prime.take(a.last)).values_at(*a)
647:デフォルトの名無しさん
20/01/15 21:04:20.76 /kpg6gtq.net
お題:
9つの物がある。
重さが20以下で価値の合計が最大になる組み合わせを求めなさい。
(Part7から再出)
[重さ, 価値]
[
[3, 5],
[5, 6],
[6, 3],
[3, 5],
[5, 9],
[2, 1],
[7, 5],
[4, 6],
[8, 3],
]
648:デフォルトの名無しさん
20/01/15 21:18:06.99 1ZW9vAE3.net
ナップサック問題か
649:デフォルトの名無しさん
20/01/15 21:27:46 woCrNz65.net
重さ < 価値
となる物を集めると丁度重さが20だから
これが解
650:デフォルトの名無しさん
20/01/16 21:02:25 ZS18thyn.net
【お題】以下の31個の数の下6桁を求めよ。
20200101の1, 2, 3, ..., 20200101乗の総和
20200102の1, 2, 3, ..., 20200102乗の総和
20200103の1, 2, 3, ..., 20200103乗の総和
:
20200131の1, 2, 3, ..., 20200131乗の総和
651:デフォルトの名無しさん
20/01/17 06:54:23.06 bFwt3c1k.net
>>626
逆行列の計算は避けた方がいいってえらいひとがゆってた
URLﾘﾝｸ(www.kyoritsu-pub.co.jp)
652:デフォルトの名無しさん
20/01/17 12:14:19.25 onsz9c/m.net
>>629
16, 7: 0 0 1 0 0 1 0 0 1
17, 9: 0 0 0 0 0 1 1 0 1
18, 26: 1 1 0 1 1 1 0 0 0
19, 27: 1 1 0 0 1 1 0 1 0
20, 31: 1 1 0 1 1 0 0 1 0
653:デフォルトの名無しさん
20/01/17 18:26:22.50 KcAYJrW8.net
>>632
C++
URLﾘﾝｸ(ideone.com)
654:デフォルトの名無しさん
20/01/17 20:33:32 VgNyCBhj.net
>>635
正解。
Rによる2種類の解答例
(1) URLﾘﾝｸ(ideone.com)
(2) URLﾘﾝｸ(ideone.com)
(1)は等比数列の総和の公式を利用しているので分かりやすいが、途中計算の最大値が
(20200130 * 1000000 - 1) ^ 2 ≒ 2 ^ 88.4 になるかも知れず、64ビット整数の
範囲に収まらないため、Cでは手軽に書けない。Rでは多倍長整数パッケージgmpを
使って書ける。
(2)は部分和をちまちま足していく方式で、途中計算の最大値が (1000000 - 1) ^ 2
≒ 2 ^ 39.9 で済むため、Cでも64ビット整数で計算できる。Rでも多倍長計算が必要な
(1)より速い (正味の実行時間が(1)は0.016秒、(2)は0.004秒)。
655:デフォルトの名無しさん
20/01/17 21:12:46 KcAYJrW8.net
お題
f(n) = n^1 + n^2 + ... + n^n の時
f^20200117 (20200117) の下9桁を求めよ
※ f^n (x) = f(f(f(....f(x)))...) 【fがn個】
656:デフォルトの名無しさん
20/01/18 00:45:25.84 meR2Lc88.net
>>629
Java
URLﾘﾝｸ(paiza.io)
657:デフォルトの名無しさん
20/01/18 05:21:08 et7QELfi.net
>>589 octave
a=primes(5000);
a(a(1:100))
658:デフォルトの名無しさん
20/01/18 22:25:47 uIn7pF9I.net
>>637
URLﾘﾝｸ(ideone.com)
Rでは時間が掛かりすぎるのでコンパイラ言語を使うが、C/C++だと出題者と同じで
つまらないから、Fortranで書いてみた。nが奇数の場合にしか求められないし、
合っているかどうか分からない。
659:デフォルトの名無しさん
20/01/18 23:02:35 /9q/+LXn.net
>>640
正解
C++
URLﾘﾝｸ(ideone.com)
312500はどうやって求めました？
660:デフォルトの名無しさん
20/01/18 23:12:37.20 /9q/+LXn.net
>>641だと偶数でもOKです
661:デフォルトの名無しさん
20/01/18 23:31:05.83 uIn7pF9I.net
>>641
時間は掛かるがRで下9桁の値を順々にいくつか求めて配列rに記録してから、
プロンプトで any(duplicated(r)) や which(duplicated(r)) と入力して
周期性を見つけただけ。理論的な根拠はない。
662:デフォルトの名無しさん
20/01/18 23:34:38.18 /9q/+LXn.net
thx
周期が既知なら
mod(20200117, 312500) 回だけで済むのでは？
663:デフォルトの名無しさん
20/01/18 23:45:49 uIn7pF9I.net
>>644
まあそうだが、それではあまりにもマジックナンバーすぎるので、周期が本当に
312500であるかチェックするコードを31行目に念のため入れた。周期性が
確認できなければ、STOP Errorと表示してプログラムを中断する。
664:デフォルトの名無しさん
20/01/19 00:38:02.65 msO9WicL.net
【お題】
無向グラフGが入力として与えられ、Gがサイクルを持てば、
Gの中の最小サイクルの経路とそのコストを出力するプログラムをかけ
＊条件
・グラフサイズ(頂点数)は10頂点程度(任意でよい)
・各辺の重みはランダムとする
・入力は隣接行列表現とする
665:デフォルトの名無しさん
20/01/19 08:33:00.83 r8dbXOf2.net
お題: 文字列aの真ん中に文字列bを挿入する関数chopを定義しなさい
666:デフォルトの名無しさん
20/01/19 08:40:19 dOSa/ZjO.net
>>647 Ruby
def chop(str); str.tap{|s| s[s.size / 2, 0] = ?b}; end
puts chop('hogefuga') # => hogebfuga
667:デフォルトの名無しさん
20/01/19 08:42:44 dOSa/ZjO.net
問題誤読してた
def chop(a, b)
a.tap{|s| s[s.size / 2, 0] = b}
end
puts chop('hogehoge', 'HOGE') # => hogeHOGEhoge
668:デフォルトの名無しさん
20/01/19 10:33:55 9NcxNk8h.net
お題 (>>346)
1～1000 の整数の内、3の倍数または5の倍数であるものだけを選んで、その合計を求めよ。
669:デフォルトの名無しさん
20/01/19 10:37:40 9NcxNk8h.net
3の倍数
[1000/3] = 333個
S(3) = 3+6+9+････+999 = 333 * (3+999)/2 = 166833,
5の倍数
[1000/5] = 200個
S(5) = 5+10+15+････+1000 = 200 * (5+1000)/2 = 100500,
3の倍数かつ5の倍数 （15の倍数）
[1000/15] = 66個
S(15) = 15+30+45+････+990 = 66
670: * (15+990)/2 = 33165, ∴ S(3) ＋ S(5) - S(15) = 100500 + 166833 - 33165 = 234168.
671:デフォルトの名無しさん
20/01/19 13:04:07.51 CR4NZ4aH.net
15の倍数含めないんじゃないの？
URLﾘﾝｸ(paiza.io)
672:デフォルトの名無しさん
20/01/19 18:23:22 t01ujcAX.net
>>629 Perl5
use List::Util qw{max};
$W = 20;
$n = @wv = ([3, 5],[5, 6],[6, 3],[3, 5],[5, 9],[2, 1],[7, 5],[4, 6],[8, 3]);
@w = map{$$_[0]} @wv;
@v = map{$$_[1]} @wv;
$wt[$n][$_] = 0 for 0..$W;
for ($i = $n - 1; $i >= 0; $i--) {
for $j (0..$W) {
$ws = $wt[$i + 1][$j];
$ws = max($wt[$i + 1][$j - $w[$i]] + $v[$i], $ws) if $j >= $w[$i];
$wt[$i][$j] = $ws;
}
}
print "価値合計最大: $wt[0][$W]\n";
$j = $W;
for $i (0..$n-1) {
$ws = $wt[$i][$j];
if ($wt[$i + 1][$j] != $ws) {
print "[$w[$i], $v[$i]] ";
$ws -= $v[$i];
for (; 0 <= $j; $j--) { last if $wt[$i + 1][$j] == $ws; }
}
}
$ perl 16_629_nsp_dp.pl
価値合計最大: 31
[3, 5]
[5, 6]
[3, 5]
[5, 9]
[4, 6]
673:デフォルトの名無しさん
20/01/19 20:22:32 MJwntUeD.net
>>652
PowerShellには論理XOR演算子があるので簡潔に書けるな。
(1..1000 |? {$_ % 3 -xor $_ % 5} | measure -sum).sum
-- 実行結果 --
201003
674:デフォルトの名無しさん
20/01/19 21:28:24 RfLx+x9F.net
>>652
なぜそう思った？
675:デフォルトの名無しさん
20/01/19 21:32:35 CR4NZ4aH.net
>>655
だけ と強調してたから15を含めない意図があったのかと思った
676:デフォルトの名無しさん
20/01/19 21:35:30 RrNuywTU.net
「3の倍数または5の倍数であるものだけ」という文言をそう理解するのは宇宙でお前だけだと思う
677:デフォルトの名無しさん
20/01/19 22:24:05 RfLx+x9F.net
妊娠してるか体が不自由な人だけ使ってください
678:デフォルトの名無しさん
20/01/19 23:13:47.04 xkwic4JQ.net
>>658
妊娠してる障害者はすわれないやんけ！
679:デフォルトの名無しさん
20/01/20 07:26:08 MadDRkAO.net
日本語の選択が排他的かどうかは状況しだいだから難しいところだと思うけどね
レストランで「コーヒーか紅茶が付きます」と言えばどちらか一方でしょ
ケースバイケース
こう解釈したらこういうプログラムになるというふうに思考を広げることはできるっしょ
680:デフォルトの名無しさん
20/01/20 08:18:28 ItoFGwWk.net
それは選ぶ条件ではなく、選ぶ個数の問題
>>346は全て選ぶのが暗黙の了解
>>660は選ぶのが1個であるのが暗黙の了解
>>346も全てとは書いてないから
1個選ぶのか、任意の個数選ぶのか、全ての選び方の場合を求めるのか、などが考えられるのかも
誤解の可能性があるなら｢全て選ぶ｣と書かないとね
681:デフォルトの名無しさん
20/01/20 10:07:25.78 DzK/Jy6Q.net
０個選んで答えは０
コンピュータ言語読み書きしてたらこういう
発想が自然に感じられるが
日常言語の世界ではナンセンス杉
682:デフォルトの名無しさん
20/01/20 14:10:00.56 gT/yNp+O.net
>651 のようにした
common lisp
(loop for i from 1 to 1000 when (= (* (mod i 3) (mod i 5)) 0) sum i)
234168
683:デフォルトの名無しさん
20/01/20 15:41:16.18 /G9h8LiI.net
>>651 Ruby
def si(n,m); n.step(m,n).inject(:+); end
p n3 = si( 3, 1000 ) #=> 166833
p n5 = si( 5, 1000 ) #=> 100500
p n15 = si( 15, 1000 ) #=> 33165
p n3 + n5 - 2 * n15 #=> 201003
684:デフォルトの名無しさん
20/01/20 21:4
685:6:25.06 ID:eV9B9Eib.net
686:デフォルトの名無しさん
20/01/20 22:42:22 vyZs8dgX.net
>>665
問題の条件によって適した解法が変わる。
たとえば個数が高々十数個程度であっても、
個々の重さや価値の範囲が広く、詰め込める荷物のキャパが大きいとか、
整数でない場合は、動的計画法だと解けないが、ナイーブな解法なら解ける。
逆に個数が大きくて、個々の重さや価値、キャパがそれほど大きくない整数だと、
ナイーブな解法では時間がかかりすぎて解けないが、
動的計画法だと短時間で解ける。
条件によって適した解法を選択する。
>>653 は動的計画法の復習と最適解に至る経路を逆にたどる復習のつもりで書いのよん。
687:デフォルトの名無しさん
20/01/20 23:01:52 kEPXORSp.net
問題に適した解法なら>>631が最強
688:デフォルトの名無しさん
20/01/20 23:10:30 vyZs8dgX.net
(´･ω･`)「・・・・・」
689:デフォルトの名無しさん
20/01/21 14:48:52 /dftakVp.net
>>650
Kotlin script
KotlinもBooleanのxor使えたよ。こういう場合は優先順位の問題で括弧が必要になるけどね。
println((1..1000).filter { (it % 3 == 0) xor (it % 5 == 0) }.sum())
690:デフォルトの名無しさん
20/01/21 16:44:59 TMO7rdDn.net
!=でいんじゃ、、、
691:デフォルトの名無しさん
20/01/21 21:56:37.25 q8k+mYw1.net
["A -> B" , "A -> D", "B -> E", "D -> E"]
を
A
B
E
D
E
このようにツリー状に表現する際に計算量が少ない書き出し方ってどうなりますか。言語問いません。
692:デフォルトの名無しさん
20/01/21 21:57:01.85 q8k+mYw1.net
スペースきえた…
693:デフォルトの名無しさん
20/01/21 21:58:36.68 5H3OckH4.net
D -> B のようなループできるかもね
694:デフォルトの名無しさん
20/01/22 03:28:09 HNO/xGn/.net
>>670
それを言っちゃあおしめえよ
695:デフォルトの名無しさん
20/01/22 10:29:09 Oj6zQLXh.net
>>671
データ構造がツリーじゃないのにツリー形式で表示するのは効率悪くない？
同じデータを何度も表示しちゃう
696:デフォルトの名無しさん
20/01/22 11:00:25 8VKZzbv1.net
>>671
dot
697:デフォルトの名無しさん
20/01/22 19:16:47 0ayd3B3Q.net
お題
>>671 において
入力文字列が20個以内で出力の行数が最大となる
入力文字列(を1個)を求めよ
698:デフォルトの名無しさん
20/01/22 19:50:15 k+w34kNu.net
["A -> B" , "B -> A]
これで循環参照のチェックいれるコードがない再帰っぽい感じなら無限に出力だ
699:デフォルトの名無しさん
20/01/22 19:55:17 F1N+c+gr.net
閉路と多重辺は無しで
辺の無い点も表現出来ないので無し
700:デフォルトの名無しさん
20/01/22 20:19:19 3jquT0bn.net
>>677
20個ならループしない限りは内容が何だろうが20行にしかならないのでは？
701:デフォルトの名無しさん
20/01/22 20:23:02 1i745hKi.net
最大は21行だよ
702:デフォルトの名無しさん
20/01/22 20:40:06 3jquT0bn.net
あー。そうか。21だね。
703:デフォルトの名無しさん
20/01/22 20:43:02 F1N+c+gr.net
>>671に "E -> C" を加えると？
704:デフォルトの名無しさん
20/01/22 21:13:37 pXdYyKNl.net
>>671
Java
URLﾘﾝｸ(paiza.io)
705:デフォルトの名無しさん
20/01/23 01:12:44 LqZxq9h8.net
>>683
分岐か。そうすれば増えるね。
706:デフォルトの名無しさん
20/01/23 18:13:14 AdSJ3UeH.net
[] 0行
["A -> B"] 2行
["A -> C", "B -> C"] 4行
["A -> D", "B -> D", "C -> D"] 6行
["A -> D", "B -> D", "C -> D", "D -> E"] 9行
707:デフォルトの名無しさん
20/01/23 18:45:00 AdSJ3UeH.net
n≧12 の時、以下を四捨五入した行数になるかな
偶数
4 * exp(n*0.24060591252980172375)
奇数
4.0137530980362538594 * exp(n*0.24060591252980172375)
708:デフォルトの名無しさん
20/01/24 23:55:14 qxZ+oily.net
>>671 Perl5 (goto 関数を使っていますが、perl5ではこれはcontinuationです)
use feature qw{current_sub signatures};
no warnings 'experimental::signatures';
@sx = (A => B, A => D, B => E, D => E);
sub {
if (@_) {
($a, $b) = (shift, shift);
push @lx, $a unless $h{$a};
push @{$h{$a}}, $b;
$r{$b}{$a} = 1;
goto __SUB__;
}
}->(@sx);
@ax = grep{! $r{$_}} @lx;
sub ($a, $d) {
print "$d$a\n";
__SUB__->($b, "_$d") while $b = shift @{$h{$a}};
}->($_, '') for @ax;
実行結果
$ perl 16_671.pl
A
_B
__E
_D
__E
709:デフォルトの名無しさん
20/01/25 02:34:16 XZtTnZKV.net
>>646
サンプルデータも考えて、回答も作れと言われると
めんどくさすぎてスルーされるんじゃまいか
710:デフォルトの名無しさん
20/01/25 02:36:37 XZtTnZKV.net
つか、無向グラフの最小サイクル検出って
いいｱﾙｺﾞﾘｽﾞﾑあったっけ
711:デフォルトの名無しさん
20/01/25 06:09:52 Fgzm1LAC.net
最小サイクルとは？
コストが最小？通る辺の数が最小？
コストとは？
通る辺の重みの和？
点のコストはゼロ？
出題者しかわからない前提が色々とあるお題
712:デフォルトの名無しさん
20/01/25 06:22:55 Fgzm1LAC.net
>>688
gotoを使っちゃいけないローカルルールとかあるの？
713:デフォルトの名無しさん
20/01/25 08:11:44 O6wUvbi6.net
tsort(1) ?
714:デフォルトの名無しさん
20/01/25 10:35:48 ZrgQFiPc.net
>>692
そんなﾙｰﾙはないけれど、制御構造の構文の代わりに安直に
goto分岐を使ったﾍｯﾎﾟｺコードではなくて、perl5のgoto 関数名構文が持つ
continuationの機能を使って、動的環境を維持したまま末尾再帰的な
loopを表現したと言いたかったのよ
715:デフォルトの名無しさん
20/01/25 10:38:39 icKJvqvk.net
なるほど
お前はなかなかやるじゃねえか
716:デフォルトの名無しさん
20/01/25 11:05:32.17 mLh1vP4R.net
お題
.bash_history には、入力したコマンドが、1行ずつ追記されていくが、
同じコマンドが出てくると面倒なので、古い(上にある)方をすべて消してください
入力
5
3
1
4
2
5
3
4
5
出力
1
2
3
4
5
717:デフォルトの名無しさん
20/01/25 11:14:27.65 wxh/zNmo.net
>>696 Ruby
puts gets(p).split.reverse.uniq.reverse
# =>
1
2
3
4
5
718:デフォルトの名無しさん
20/01/25 12:48:36.66 dgvYVRBF.net
>>696
Java
URLﾘﾝｸ(paiza.io)
719:デフォルトの名無しさん
20/01/25 13:56:27.24 yjSryLut.net
>>696 Perl5
$h{$_} = $. while <>;
print for sort{$h{$a} <=> $h{$b}} keys %h;
実行結果
~ $ cat .bash_history
5
3
1
4
2
5
3
4
5
~ $ perl 16_696.pl .bash_history
1
2
3
4
5
720:デフォルトの名無しさん
20/01/25 18:59:55 xXb4DuHd.net
>>696
URLﾘﾝｸ(ideone.com)
RのuniqueにはfromLastオプションがあるので、revによる前後処理が不要。
721:デフォルトの名無しさん
20/01/25 19:19:17 i4ScOGkF.net
>>696 Ruby
a=STDIN.readlines
puts a.select.with_index{|v,i| i==a.rindex(v)}.join
722:デフォルトの名無しさん
20/01/25 19:26:44 eYyvJiZZ.net
>>696 .bashrc
HISTCONTROL=erasedups:ignorespace
ついでに
HISTIGNORE="history*"
723:デフォルトの名無しさん
20/01/25 20:22:19 J6xo1Vbp.net
>>696 Emacs Lisp
(with-temp-buffer-window #1="*odai-pt16-696*" nil nil
(switch-to-buffer #1#)
(insert-file-contents "~/.bash_history")
(delete-duplicate-lines (point-min) (point-max) t))
724:デフォルトの名無しさん
20/01/26 00:01:21 4S7WZkam.net
>>701 ナイス
725:デフォルトの名無しさん
20/01/26 00:02:23 4S7WZkam.net
>>704 ｱﾝｶｰしくった
>>702 ﾅｲｽはこっちだた
726:696
20/01/26 00:35:54.22 2jcz6vHU.net
>>702
スレ違いで、スマンが、
erasedups で、現在の行と一致する履歴を、保存前にすべて削除するけど、
WSL, Ubuntu 18.04, bash では、削除されなかった！
これは難しい
tmuxとかの仮想端末で複数の画面間で、Bashのコマンド履歴を共有すると、
同じ履歴が何度も記録されてしまう問題を解決する
URLﾘﾝｸ(piro.sa)＠kura.ne.jp/latest/blosxom/webtech/2018-03-04_history-nodup-with-tmux.htm
727:デフォルトの名無しさん
20/01/26 01:20:33.64 4S7WZkam.net
>>706
ﾓﾁﾂｹ
728:696
20/01/26 01:39:31.40 2jcz6vHU.net
history の仕組みが難しいから、
定期的に、ここのスクリプトで、履歴ファイルを上書きした方が良いかも
729:デフォルトの名無しさん
20/01/26 01:43:44.81 HPdacZve.net
rubyXLでエクセルいじってるが
印刷範囲を設定したいときは、どのようにすればよいのでしょうか？
いろいろ探しても見当たらず・・
730:デフォルトの名無しさん
20/01/26 02:08:32 4S7WZkam.net
>>709
ｽﾚﾁ
>>708
bashから.bash_profileの重複をなくすプログラムを実行しても
logoutするときにbashが記憶しているコマンド履歴を.bash_profileに
上書きしちゃって、元の木阿弥になるんｼﾞｬﾏｲｶ
731:696
20/01/26 05:19:41 2jcz6vHU.net
>>710
>>706
のサイトに書いてあるけど、
.bash_history から重複を排除して、上書きする
次に、history -c && history -r
-c で、メモリ上のコマンド履歴を削除して、
-r で、履歴ファイルからメモリへ、コマンド履歴を読み込む
まだ、試してないけど
732:696
20/01/26 06:05:44 2jcz6vHU.net
>>696
Ruby で作った。
コマンドは「ruby script.rb 入力ファイル名」
# ARGF とは、複数のファイルや標準入力を連結して、1つにした仮想ファイル
ary = ARGF.readlines # 1行ずつ配列に入れる
# ! が付く破壊的メソッドは、メソッドチェーンしない！
ary.reverse!
ary.uniq! # 連続していないものも削除する
ary.reverse! # 元に戻す
print ary.join
733:696
20/01/26 06:21:48 2jcz6vHU.net
>>711
の方
734:法で、.bash_history から重複を排除できました！
735:デフォルトの名無しさん
20/01/26 09:38:26 6CyPsFJq.net
お題: 入力された整数を因数分解し、因数の数だけ「どんだけぇ～♪」と表示せよ
in < 24
因数分解: 2 2 2 3
out > どんだけぇ～♪
どんだけぇ～♪
どんだけぇ～♪
どんだけぇ～♪
736:デフォルトの名無しさん
20/01/26 10:24:47.39 mBsLdcGX.net
>>709
121 名前：デフォルトの名無しさん (ﾜｯﾁｮｲ a763-gk0v)[] 投稿日：2020/01/25(土) 15:52:45.46 ID:WZ3Oswhu0
rubyXLでエクセルいじってるが
印刷範囲を設定したいときは、どのようにすればよいのでしょうか？
いろいろ探しても見当たらず・・
737:デフォルトの名無しさん
20/01/26 10:35:06.75 OyPCa8uu.net
>>714 Ruby
puts "どんだけぇ～♪\n"*~-`factor`.split.size
738:デフォルトの名無しさん
20/01/26 11:45:57 pipfilQo.net
>>714
Java
URLﾘﾝｸ(paiza.io)
739:蟻人間
20/01/26 15:31:19.81 QR2U0M8L.net
お題: どこかの国に競馬があった。そこの競馬場のルールでは馬券一枚に対して単勝の馬一頭しか選べない。
その日の各ゲームのそれぞれの出場馬について、名前と勝率とオッズが掲示されている。
【今日の競馬】
ゲーム1:
馬A, 0.5, 2.0
馬B, 0.8, 1.2
馬C, 0.9, 0.2
ゲーム2:
馬D, 0.3, 4.0
馬E, 0.5, 3.0
馬F, 0.8, 1.4
予算50,000円で獲得期待金額が最大になるように馬券を購入せよ。馬券の購入において、小数点以下は切り捨てとし、馬券には税金が掛からないものと仮定する。
740:デフォルトの名無しさん
20/01/26 15:44:50.09 uQg9mh+n.net
勝率の和が1を越えてるけど勝率って言うのは勝つ確率のことではなくて何かしらの競馬用語なのか？
741:蟻人間 ◆T6xkBnTXz7B0
20/01/26 15:46:20 TOQ25Lx5.net
ここでは、払戻金の倍率（賭けた金が何倍になって払い戻されるか）のことをオッズと呼ぶことにする。払戻金は小数点以下切り捨てとする。
742:デフォルトの名無しさん
20/01/26 15:47:57 uQg9mh+n.net
てよく見たらいつもの糞コテやん
解散
743:蟻人間 ◆T6xkBnTXz7B0
20/01/26 15:55:46 QR2U0M8L.net
>>719
馬の勝率はこれまでのレースで一着になった確率。
744:デフォルトの名無しさん
20/01/26 16:14:00 jQnb27FW.net
勝つ確率がわからないなら期待値もわからない
普通は買わないのが一番
745:デフォルトの名無しさん
20/01/26 16:45:22.64 jQnb27FW.net
オッズ0.2って何？
746:デフォルトの名無しさん
20/01/26 17:18:30.67 aRFw4TjA.net
杜撰なお題だなw
747:蟻人間
20/01/26 17:19:13.36 QR2U0M8L.net
>>724
勝つと20%戻ってくるという意味。
748:デフォルトの名無しさん
20/01/26 17:23:34.39 uQg9mh+n.net
100円の馬券が当たるとなんと20円に！
749:デフォルトの名無しさん
20/01/26 18:27:58.48 jQnb27FW.net
>>718
ちゃんとしたお題にするつもりが無いなら取り下げて
750:蟻人間
20/01/26 18:40:41.46 TOQ25Lx5.net
>>718 >>728
取り下げます。もっと良いお題を考えて下さい。
751:デフォルトの名無しさん
20/01/26 18:56:39.39 OTxXTlwF.net
>>714
初心者です
JavaScriptです
let n = 24;
const factors = [];
for(let i=2;i<=Math.floor(n/2);i++){
if(n % i !== 0) continue;
for(;;) {
n /= i;
factors.push(i);
if(n % i !== 0) break;
}
}
for(let i=0; i<factors.length; i++) {
console.log('どんだけぇ～♪')
}
って感じに書いたのですがどうも外側のループで i = 3 以上が実行されないらしく困っています
もしかしたら初学者の自分にもできるかもしれないと思い取り組んでみたのですが…
もしどなたかお知恵をお貸しくだされば嬉しいです
752:デフォルトの名無しさん
20/01/26 19:03:07.14 uQg9mh+n.net
>>730
for(let i=2;i<=Math.floor(n/2);i++){
を
const sup = Math.sqrt(n);
for(let i=2;i<=sup;i++){
753:デフォルトの名無しさん
20/01/26 19:09:59 OTxXTlwF.net
>>731
ありがとうございます！動きました
何かとんでもない思い違いをしていたみたいで恥ずかしい…
754:デフォルトの名無しさん
20/01/26 19:18:27 9QNAjmQu.net
n % i !== 0
755:デフォルトの名無しさん
20/01/26 19:23:55 pipfilQo.net
>>729
ビルの回数Nを引数として受け取って次の問題を解くプログラムを作ってください
N階建てのビルのある階から卵を落とします。
卵はある階よりも低ければ割れることはなく、ある階よりも高いと割れてしまう。
今、あなたは卵を2つ持っています。
卵が何階で割れるかを調べるもっとも効率のよい方法は何ですか？
そして、その方法で必要な卵を落とす回数は最大で何回ですか？
756:デフォルトの名無しさん
20/01/26 19:26:53 TCoNMy8F.net
2分探索じゃだめか？
757:デフォルトの名無しさん
20/01/26 19:40:43.12 yXTxN+fl.net
>>714
C++ イデオン揚げるの面倒なのでべた書きしておくわ。
半月ぶり位にコード書いたけど、やはり良いね。
#include <iostream>
#include <cstdint>
int main() {
std::uintmax_t N = 24;
while (std::cin >> N) {
for (std::uintmax_t i = 2; i <= N; i++) {
while (N % i == 0 && N != 0) {
N /= i;
std::cout <<i<< ":どんだけー。" << std::endl;
}
}
std::cout << std::endl;
}
return 0;
}