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

1 名前：デフォルトの名無しさん mailto:sage [2016/12/01(木) 16:58:30.97 ID:gTkHDluD.net] プログラミングのお題スレです。 前スレ プログラミングのお題スレ Part8©2ch.net echo.2ch.net/test/read.cgi/tech/1444216746/ 【出題と回答例】 1 名前：デフォルトの名無しさん 　　お題：お題本文 2 名前：デフォルトの名無しさん 　　>>1 使用言語 　　回答本文 【ソースコードが長くなったら】 (オンラインでコードを実行できる) ideone.com/ codepad.org/ compileonline.com/ rextester.com/runcode runnable.com/ code.hackerearth.com/ melpon.org/wandbox https://paiza.io/ 宿題は宿題スレがあるのでそちらへ。 755 名前：デフォルトの名無しさん [2017/11/28(火) 19:45:30.22 ID:jzUFRHpN.net] これが収束速いようだ。 log(2) = 3log(81/80) + 5log(25/24) + 7log(16/15) log((x+1)/(x-1)) = log((1+1/x)/(1-1/x)) = 2 Σ 1/((2n+1)*x^(2n+1)) 756 名前：デフォルトの名無しさん mailto:sage [2017/11/28(火) 22:18:22.38 ID:7WoPw74F.net] >>728 1/log(2) ≒ 3.32 1/2log(161)+1/2log(49)+1/2log(31) ≒ 0.85 なので、計算に必要な項数は1/4程度 でも、1つの項の計算には時間がかかる log(1-x)のマクローリン展開に0.5を入れた物は 分母が i * 2^i だから速く計算できるのだ 757 名前：デフォルトの名無しさん mailto:sage [2017/11/28(火) 22:20:46.48 ID:7WoPw74F.net] >>727 残りの項を等比数列と見なせば 簡単に誤差の上限が出ます 758 名前：デフォルトの名無しさん mailto:sage [2017/11/28(火) 22:47:09.33 ID:7WoPw74F.net] >>724 Haswellで33.96秒に縮まりました シングルスレッドだと182.54秒で5.3倍 HTTが効くということは、 まだ多少改善の余地がありそう 一番内側のループは vmulpd vmulpd vroundpd vfmsub213pd vfmsub132pd vsubpd なんと浮動小数点で計算してます 759 名前：デフォルトの名無しさん mailto:sage [2017/11/28(火) 22:53:54.93 ID:7WoPw74F.net] n=10000000000の時は 0000010101 でした 出題者さま、合ってます？ また、たまたまですが n=10000000004では 0101010101 n=10000000005では 1010101010 になります 760 名前：デフォルトの名無しさん mailto:sage [2017/11/28(火) 23:30:15.70 ID:9HoDrqB3.net] 一番内側のループのコード fast-uploader.com/file/7067434368942/ PORT5がガラ空きで、処理のほとんどがPORT0,PORT1 こんなんでもHTTが効く やっぱり浮動小数点はレイテンシがデカい AVX512になれば レジスタの数が倍になるので 8パラにしてレイテンシを隠蔽出来るんだけど もちろんレジスタ長が倍になる方が大きい 761 名前：デフォルトの名無しさん [2017/11/29(水) 13:17:33.09 ID:mHyZby47.net] >>728は後半部分が間違ってるか。log((x+1)/x) = log(1+1/x) の展開を用いるのが正解で。 log(・)の中身を1に近づけた方が収束が早くなるが、 こういった分解　log(2) = 3log(81/80) + 5log(25/24) + 7log(16/15)はどうみつけるのか。 これは数値が(x+1)/x の形だけど、(x+1)/(x-1)の分解もあるのか。こっちだと計算するベキ項が一つ飛ばしにできる。>>728のように。 762 名前：デフォルトの名無しさん mailto:sage [2017/11/29(水) 13:34:57.75 ID:8/kTvoZy.net] 2 = (81/80)^3 * (25/24)^5 * (16/15)^7 3 と 5 の指数の合計が0になる組み合わせを検索すれば良い 763 名前：デフォルトの名無しさん mailto:sage [2017/11/29(水) 13:37:30.83 ID:8/kTvoZy.net] log(81/80) = log(162/160) = log((161+1)/(161-1)) わかってて書いてるんだと思ったが >>729のlogの中身はこの値 764 名前：デフォルトの名無しさん [2017/11/29(水) 13:42:05.17 ID:mHyZby47.net] >>728はそういうことか。みつけたやつのコピペで、そのとき考慮はしてなかった。 765 名前：デフォルトの名無しさん [2017/11/29(水) 13:45:31.51 ID:mHyZby47.net] 指数も固定でなくていいはずで、 16/15よりかはたとえば1001/1000のほうが1に近いからそういうのはいくらでも見つけられるのかとおもった。 766 名前：デフォルトの名無しさん mailto:sage [2017/11/29(水) 14:44:26.09 ID:8/kTvoZy.net] 分母分子の素因数の数と同じ項数が必要 例えば素因数が 2, 3, 5, 7 の4種類の場合、 1個差もしくは2個差のペアを4個探す 例えば 126/125 225/224 2401/2400 4375/4374 これらを適当に掛け算して2^nになるようにすると 項が4個の式がみつかる 767 名前：デフォルトの名無しさん mailto:sage [2017/11/30(木) 00:31:43.08 ID:H4qIjcIH.net] 分母、分子とも 2, 3, 5, 7, 11, 13, 17 のみしか素因数を持たない形の場合、 以下が一番計算する項の数が少ないようです log(2) = 72*log(126/125)+27*log(225/224)-19*log(2401/2400)+31*log(4375/4374) 768 名前：デフォルトの名無しさん [2017/11/30(木) 05:07:54.11 ID:fMs2N0Mh.net] >>740 その数値を検索すると、音楽のコンマというのが出てくる。関係あったり理論があったりするのか。 A.D. Fokker: Unison Vectors and Periodicity Blocks www.huygens-fokker.org/docs/fokkerpb.html List of 7-prime limit accidentals - The?Sagittal?forum forum.sagittal.org/viewtopic.php?f=6&t=252 769 名前：デフォルトの名無しさん [2017/11/30(木) 05:28:17.43 ID:fMs2N0Mh.net] log(2)とは無関係で、単に一個差のやつで適当な素因数分解できるやつに名前がついてるだけ? An Investigation into the Extraction of Melodic and Harmonic Features from Digital Audio unit interval name 4375/4374 Ragisma 2401/2400 Breedsma 225/224 Septimal Kleisma 145/144 Difference between 29:16 and 9:5 126/125 Small Septimal Semicomma 121/120 Undecimal Seconds Comma 81/80 Syntonic Comma scholar.sun.ac.za/handle/10019.1/100826 770 名前：デフォルトの名無しさん [2017/11/30(木) 11:02:35.16 ID:fMs2N0Mh.net] log2のほうは、分子・分母の素因数分解が似通ってないと成立しないってことで、 音楽のほうは小さい素数に限定して一個差ペアを求めたと理解。 log2のほうは、共通の素数で大きいやつを最初に固定すれば考えれば、よさげかと。 771 名前：片山博文MZ mailto:sage [2017/11/30(木) 12:12:48.85 ID:NsMGt5if.net] お題。横x[cm]、縦y[cm]の長方形のステンレスの１枚の板がある。この板からm枚の複数の長方形の部材を切り出す。 部材のサイズは配列で与えられる。 部材のサイズ(縦×横)はそれぞれだいたい決まっているが、1cm程度変わってもよい。 ただし、部材の縦または横が変わるとそれぞれ一点減点となる。 すべての部材を切り出すことができれば、減点がなるべく少ない方法の切り出し方法を出力せよ。 すべての部材を切り出すことができなければ、面積が広い順になるべくたくさん部材を切り出せ。 772 名前：片山博文MZ mailto:sage [2017/11/30(木) 12:19:33.84 ID:NsMGt5if.net] テストデータ。 x=10, y=10, { {5, 10}, {2, 2}, {2, 2}, {4, 3}, {6, 5} } x=5, y=12 { {2, 5}, {3, 3}, {2,9}, {3, 2}, {4,3} } 773 名前：片山博文MZ mailto:sage [2017/11/30(木) 12:28:07.36 ID:NsMGt5if.net] 部材の縦と横は入れ替わってもよい。 可能ならば、切り出し方法をSVG形式で出力せよ。 774 名前：片山博文MZ mailto:sage [2017/11/30(木) 12:51:59.04 ID:NsMGt5if.net] 切り出し方法は、 切り出す部材のx座標、y座標、幅、高さ のリストとして出力せよ。 775 名前：片山博文MZ mailto:sage [2017/11/30(木) 12:56:57.25 ID:NsMGt5if.net] 切り出しに余裕があるときは、なるべくx座標の大きい方、y座標の大きい方を残すようにせよ。 776 名前：デフォルトの名無しさん mailto:sage [2017/11/30(木) 13:08:21.37 ID:tkxPMdZc.net] 斜めもOK？ 777 名前：デフォルトの名無しさん mailto:sage [2017/11/30(木) 13:08:55.87 ID:tkxPMdZc.net] 人間用のパズルで、斜めにしないと解けないのとかありそう 778 名前：デフォルトの名無しさん [2017/11/30(木) 14:23:24.17 ID:SHLZLl2M.net] 問題文の条件が“だいたい”“なるべく”なんて あいまい表現だらけ これでプログラミングの問題かよ 779 名前：片山博文MZ mailto:sage [2017/11/30(木) 16:18:01.24 ID:NsMGt5if.net] 斜めは考えなくてもよい。 訂正。 すべての部材を切り出すことができれば、減点が最小である切り出し方法を出力せよ。 すべての部材を切り出すことができなければ、面積が広い順に切り出せる部材の面積が最大になるよう部材を切り出せ。 切り出しに余裕があるときは、x座標の大きい方、y座標の大きい方を残すようにせよ。 780 名前：680 mailto:sage [2017/11/30(木) 17:10:37.24 ID:8ZVWPbH7.net] >>732 そこにある3つとも正解です 当初は L = Σ1/(k*2^k) として 2^n * L の小数部分を愚直に求める方法を想定していました 781 名前：デフォルトの名無しさん mailto:sage [2017/11/30(木) 17:26:52.63 ID:r8WkgLop.net] 普通に多倍長で計算したら計算量的に終わらないですよね？ n=314159265を求めるのに 冪剰余は使ってますよね？ おそらく私も同じような方法と思います FMA3命令とOpenMPで高速化してるだけで 782 名前：デフォルトの名無しさん mailto:sage [2017/11/30(木) 22:49:50.18 ID:TklDiPhy.net] 愚直という言い方は良く割りませんでしたね 仰る通り冪剰余は用います 783 名前：片山博文MZ mailto:sage [2017/12/01(金) 14:26:32.50 ID:fw1UFg83.net] 再出題。横cx[cm]、縦cy[cm]の長方形または正方形のステンレスの１枚の板がある。この板からm枚の複数の長方形または正方形の部材を切り出す。 m枚の部材のサイズは(縦, 横)の配列で与えられる。 すべての部材を切り出すことができれば、切り出し方法を出力せよ。切り出しが不可能ならば「impossible」と出力せよ。 切り出し方法は、 (部材インデックス、部材の一番左のx座標、部材の一番上のy座標、幅、高さ) のリストとして出力せよ。斜めの方向の切り出しは考えなくてもよい。 切り出しに余裕があるときは、x座標の大きい方、y座標の大きい方を残すようにせよ。ただし、x軸は右の向き、y軸は下向きとする。 テストデータ。 cx=10, cy=10, m=5, {5, 10}, {2, 2}, {2, 2}, {4, 3}, {6, 5} cx=5, cy=12, m=5, {2, 5}, {3, 3}, {2, 8}, {3, 2}, {4, 3} 784 名前：デフォルトの名無しさん mailto:sage [2017/12/01(金) 17:01:28.13 ID:BqJQPTjH.net] 頭の悪そうな文章だな 正方形⊂長方形 ステンレスの板の座標上の位置指定が無い 余裕がある場合の条件の意味が曖昧 785 名前：片山博文MZ mailto:sage [2017/12/01(金) 18:41:36.20 ID:fw1UFg83.net] ステンレスの板の左上座標は原点にあるものとする。 切り出しは、可能な限り、座標の小さい方を優先する(「余裕」の意味)。 786 名前：デフォルトの名無しさん mailto:sage [2017/12/01(金) 20:32:10.86 ID:9YSaSAW0.net] >>758 相変わらず曖昧な表現 全ての長方形の上辺と左辺がどこかに接していれば良いのか？ そうじゃないのか？ このような条件のを1個だけ見つければ良いのか すべて見つけるのか 787 名前：片山博文MZ mailto:sage [2017/12/01(金) 20:41:14.79 ID:fw1UFg83.net] 全ての部材の上辺と左辺が別の部材の辺、もしくは、元の板の端に接していること。 このような条件のをすべて見つけること。 788 名前：片山博文MZ mailto:sage [2017/12/01(金) 20:43:57.24 ID:fw1UFg83.net] なんか、工学関係でこのような問題があるらしいが、まだ解決策があるかどうかわからん。これが解ければ、実用化待ったなし。 789 名前：デフォルトの名無しさん mailto:sage [2017/12/01(金) 21:15:23.73 ID:9YSaSAW0.net] お題じゃなくて依頼かよ 790 名前：デフォルトの名無しさん mailto:sage [2017/12/01(金) 21:19:54.38 ID:9YSaSAW0.net] 実用性なら 切り 791 名前：やすさとか余り素材の形状とか そういうのが重要だろうに 問題として中途半端過ぎる [] [ここ壊れてます] 792 名前：デフォルトの名無しさん [2017/12/01(金) 21:20:21.36 ID:qVeescqP.net] また片山博文MZ が乞食をやってるのか 793 名前：デフォルトの名無しさん mailto:sage [2017/12/01(金) 21:23:07.33 ID:9YSaSAW0.net] 普通に考えて、NP問題だろう 794 名前：デフォルトの名無しさん [2017/12/01(金) 21:48:16.44 ID:8H4JUlF5.net] なにやら揉めてますね そろそろうんざりなので次のお題どうぞ 795 名前：デフォルトの名無しさん [2017/12/01(金) 23:36:29.58 ID:N1IVcYDB.net] スポーツスケジューリング問題。 796 名前：デフォルトの名無しさん mailto:sage [2017/12/03(日) 02:47:12.16 ID:QazTjKaA.net] お題ってこういうのでもいいのかな a[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } このように10個の整数を要素に持つ配列がある（整数の値は不定） b = エントリーポイント c = 移動する数量 d = 移動する距離 を与えることにより、配列の要素を移動させるプログラムを作りなさい ただし配列の右端の要素を一つ移動させると、配列の左端に移動するものとする 例 a = 3, b = 1, c = 5, a = 0124567839 b = 1, c = 3, d = 1, a = 0412356789 b = 7, c = 1, d = 5, a = 1273456890 b = 0, c = 8, d = 1, a = 8012345679 b = 4, c = 5, d = 4, a = 6783901245 b = 9, c = 5, d = 4, a = 5679012384 b = 7, c = 3, d = 1, a = 9123456078 797 名前：デフォルトの名無しさん mailto:sage [2017/12/03(日) 02:49:08.83 ID:QazTjKaA.net] >>768 一番上の例は b = 3, c = 1, d = 5, a = 0124567839 の間違いです 798 名前：デフォルトの名無しさん mailto:sage [2017/12/03(日) 09:00:27.20 ID:ucQfMVKf.net] >>768 https://ideone.com/zZdIlU C++。なかなか素直な問題なのに邪悪な思念で見ていたため手間取った。 マニュアルを熟知していると簡単かもしれない。 799 名前：デフォルトの名無しさん mailto:sage [2017/12/03(日) 09:04:48.71 ID:b0AFqm0g.net] >>768 Ruby https://ideone.com/0l4cEo 800 名前：デフォルトの名無しさん mailto:sage [2017/12/03(日) 10:14:55.69 ID:ZeeZWfzn.net] >>768 @Mathematica https://ideone.com/z4q1Nk 801 名前：デフォルトの名無しさん mailto:sage [2017/12/03(日) 12:12:41.56 ID:jbLAlLAh.net] >>768 b + c が10を超えることはありますか？ 802 名前：デフォルトの名無しさん mailto:sage [2017/12/03(日) 12:55:22.10 ID:sC6phLBS.net] >>773訂正 b,c,dが10を越えることはありますか？ 803 名前：デフォルトの名無しさん mailto:sage [2017/12/03(日) 13:05:23.73 ID:b0AFqm0g.net] >>771はb,c,dが任意の自然数でも大丈夫なようにしておいた 804 名前：デフォルトの名無しさん mailto:sage [2017/12/03(日) 13:08:19.92 ID:QazTjKaA.net] みなさんプログラム作るの早いですね >>774 一応a、b、cの条件は、このようになると思います。 0 <= a <= 9 0 <= b <= 8 0 <= c <= 10 - b - 1 bとcは0では意味がないので、こっちのほうがいいのかな 0 <= a <= 9 1 <= b <= 8 1 <= c <= 10 - b - 1 805 名前：デフォルトの名無しさん mailto:sage [2017/12/03(日) 13:12:58.80 ID:QazTjKaA.net] >>776 すみません、間違えました、abcじゃなくてbcdですね 0 <= b <= 9 1 <= c <= 8 1 <= d <= 10 - b - 1 806 名前：デフォルトの名無しさん mailto:sage [2017/12/03(日) 13:34:35.32 ID:QazTjKaA.net] >>777 すみません、訂正の訂正です。dは10-c-1ですorz 0 <= b <= 9 1 <= c <= 8 1 <= d <= 10 - c - 1 807 名前：デフォルトの名無しさん [2017/12/03(日) 17:47:25.64 ID:Gq7SJlPX.net] Linked list 使うと楽そうな感じするな 808 名前：デフォルトの名無しさん mailto:sage [2017/12/03(日) 18:26:21.27 ID:QazTjKaA.net] >>770,771 せっかくなのでこのテストデータを作って検証してみましたが、全部合っていました、さすがですね それにしても他人のプログラムって動かすことはできても、理解するのは困難ですね >>772 Mathematicaは残念ながら持っていないので検証できませんでした b = 8 c = 6 d = 2 a = 8901236745 b = 4 c = 3 d = 2 a = 0123784569 b = 4 c = 5 d = 2 a = 8123904567 b = 2 c = 5 d = 2 a = 0178234569 b = 0 c = 5 d = 3 a = 5670123489 b = 9 c = 3 d = 4 a = 3459016782 b = 5 c = 1 d = 7 a = 1253467890 b = 4 c = 6 d = 2 a = 8923014567 b = 6 c = 7 d = 2 a = 8901253467 b = 7 c = 5 d = 4 a = 5789016234 b = 4 c = 2 d = 2 a = 0123674589 b = 6 c = 4 d = 5 a = 4678950123 b = 7 c = 4 d = 4 a = 4789056123 b = 4 c = 5 d = 4 a = 6783901245 b = 8 c = 1 d = 5 a = 1238456790 b = 0 c = 2 d = 6 a = 2345670189 b = 3 c = 7 d = 1 a = 9120345678 b = 9 c = 4 d = 2 a = 4901256783 b = 8 c = 3 d = 6 a = 3456890712 b = 2 c = 5 d = 3 a = 0178923456 809 名前：デフォルトの名無しさん mailto:sage [2017/12/03(日) 20:16:05.68 ID:hV+xPFYR.net] >>768 ruby ワンライナー https://ideone.com/sXGhCG 810 名前：デフォルトの名無しさん mailto:sage [2017/12/03(日) 20:37:58.61 ID:ucQfMVKf.net] >>780 お、あんた偉いな。 出題者でちゃんと答え合わせやってくれる人が稀でレスポンス薄いことが多いんだよ。 ちゃんと動いてよかったよ。 811 名前：デフォルトの名無しさん mailto:sage [2017/12/03(日) 20:51:48.60 ID:ucQfMVKf.net] >>774 自分は10超えてもらったら困るなぁ。 10っていうか、配列の要素数だな。 修正はそんなに難しくないけど。 812 名前：デフォルトの名無しさん mailto:sage [2017/12/03(日) 23:00:23.32 ID:QazTjKaA.net] >>781 1行プログラムすごいですね さすがスクリプト言語 >>782 そうなんですか、でもいろいろな言語で回答されるから、出題者も大変かもしれないですね 私は問題の意味すらよく分からないことが多いので、もっぱら見る専ですが 813 名前：デフォルトの名無しさん [2017/12/04(月) 02:36:11.06 ID:iGjrIGoV.net] >>768 これでいいのかなあ？ Perl で書いた。 https://paiza.io/projects/ncIY4LljeBahWZPJpd8ZPQ 814 名前：デフォルトの名無しさん mailto:sage [2017/12/04(月) 06:47:18.44 ID:Rc7ie/2s.net] >>785 b = 6、 c = 6、 d = 2 のときの動作がおかしいようです 8901452367 となるはずが 0167892345 となっており、移動する"678901"の並びが崩れてしまっています 815 名前：785 [2017/12/05(火) 02:32:35.27 ID:LDxS5CId.net] >>786 問題勘違いしてました。素直にぐるぐる回すように修正しました。 https://paiza.io/projects/ncIY4LljeBahWZPJpd8ZPQ 下の「入力」タブの方にスペース区切りで b, c, d の値を1行づつ並べて入れてから実行させると「出力」に結果が出ます。 とりあえず >>768 に書いてある値を入力にセットしたところ出力は同じになりました。 816 名前：デフォルトの名無しさん mailto:sage [2017/12/05(火) 20:55:13.95 ID:vy+ohhoY.net] >>787 入出力の確認をしただけですが、今回は問題ないようです paiza使うと簡単に確認できて便利ですね 817 名前：デフォルトの名無しさん mailto:sage [2017/12/05(火) 21:48:50.31 ID:32LsMTj+.net] >>768 僕の頭だとどうしても右端から左端に行くときの動きがイメージできないので、解答締め切ったあとでもいいのでちょろっと教えてもらえると嬉しいです 上3つまではわかるけどそこから先がそもそも答えにたどり着けない…… 818 名前：デフォルトの名無しさん mailto:sage [2017/12/05(火) 23:47:14.24 ID:ynbcQBXQ.net] >>789 ヒント。 (インデックス++)%配列の長さ を繰り返すとどうなりますか？%は余剰デス。 819 名前：デフォルトの名無しさん mailto:sage [2017/12/06(水) 00:25:49.49 ID:gvvJf1Ph.net] >>789 上の３つまでは分かるということなので、３つめのcの値を一つずつ増やしてみると、こんな感じになります "7"、"78"、"789"、"7890"と並ぶ数値が増えていっているのが分かると思います c+d の合計は9が最高なので、これ以上cを増やすにはdを減らさなくてはなりません b = 7 c = 1 d = 5 a = 1273456890 b = 7 c = 2 d = 5 a = 2378456901 b = 7 c = 3 d = 5 a = 3478956012 b = 7 c = 4 d = 5 a = 4578906123 今度はcを2に固定して、dの値を一つずつ増やすと、こんな感じになります "78"の並びが一つずつ右へずれていっているのが分かると思います c+d の合計は9が最高なので、これ以上dを増やすにはcを減らさなくてはなりません b = 7 c = 2 d = 1 a = 0123456978 b = 7 c = 2 d = 2 a = 8123456907 b = 7 c = 2 d = 3 a = 7823456901 b = 7 c = 2 d = 4 a = 2783456901 b = 7 c = 2 d = 5 a = 2378456901 b = 7 c = 2 d = 6 a = 2347856901 b = 7 c = 2 d = 7 a = 2345786901 こんな感じで分かるでしょうか？私も自分の頭で考えると混乱しますw 820 名前：デフォルトの名無しさん mailto:sage [2017/12/06(水) 00:31:57.65 ID:+0bHqE6f.net] � 821 名前：ｩ分の考え方は、配列の一部を切り取ってパッディングするんだけど、 まず配列を回転させて切り取る第0インデックスを配列の最初に持って来る。 すると、配列の後ろにはすでにパディングが終わった数列のができてる。 で切り取って削除して尻尾にくっつける。 で、さっき回した分を戻してやると完成。 という方法で、>>770を解いた。 [] [ここ壊れてます] 822 名前：デフォルトの名無しさん mailto:sage [2017/12/06(水) 00:32:05.18 ID:+0bHqE6f.net] 自分の考え方は、配列の一部を切り取ってパッディングするんだけど、 まず配列を回転させて切り取る第0インデックスを配列の最初に持って来る。 すると、配列の後ろにはすでにパディングが終わった数列のができてる。 で切り取って削除して尻尾にくっつける。 で、さっき回した分を戻してやると完成。 という方法で、>>770を解いた。 823 名前：デフォルトの名無しさん mailto:sage [2017/12/06(水) 00:32:32.42 ID:+0bHqE6f.net] あちゃー 二重投稿になったある。 そんなに大事でもないのだけど。 824 名前：デフォルトの名無しさん mailto:sage [2017/12/06(水) 00:38:22.54 ID:+0bHqE6f.net] C++は比較的不自由な言語なので頭使うのは鍛えられるよ。 パーツが少ないのでほとんど自作しないといけない。 825 名前：デフォルトの名無しさん [2017/12/06(水) 00:46:18.89 ID:DokUEpLm.net] コンパイルが必要とかでスクリプト系の言語より 使うことに不便があるかもしれないが、 できるアプリが自由で高速・軽量！ ライブラリもＳＴＬやboost以外にも、探せば便利なのがいっぱい。 826 名前：デフォルトの名無しさん mailto:sage [2017/12/06(水) 01:07:01.76 ID:+0bHqE6f.net] よそのライブラリ使うとイデオンで動かないからなぁ。 まぁ、業務ではライセンスに合ったものを使えばいいよ。 827 名前：デフォルトの名無しさん [2017/12/06(水) 02:01:03.49 ID:QVT4XBLu.net] >>789 塊が移動すると考えれば良い。 例えば 7, 4, 2 だとすると、 789 と先頭の 0 が移動する塊だ。 で、ちょっと分かり易くするためにこの塊を伏せて * で書くとするとこうなる。 *123456*** それでこの塊を右に一つずらす。その時に1は食われて尻尾から吐き出される。 **234561** 移動量2なのでもう一回右にずらす。すると2が食われて尻尾から吐き出される。 ***345612* それでは * から 7890 に戻してみよう。 8903456127 できあがり。 828 名前：デフォルトの名無しさん mailto:sage [2017/12/06(水) 02:58:25.26 ID:+0bHqE6f.net] >>793 これ間違ってるな。 最後尻尾にくっつけるんじゃなくて、適所にインサートだった。 で戻す。 書いた日から時間たってるからすまん。 829 名前：デフォルトの名無しさん mailto:sage [2017/12/06(水) 08:41:18.93 ID:obBhCrma.net] >>790 >>791 >>798 ありがとうございます やっと理解できました がんばって解いてみます 830 名前：デフォルトの名無しさん [2017/12/06(水) 17:48:37.81 ID:T95E7suL.net] log2だけど、これ使うといいらしいよ。分割統治法のBSA法というやつらしい。 2個ずつの積を繰り返すことで計算回数が減らせる。 {{1, a0}, {0, r}}*{{1, a1}, {0, r}}を[ [○,P], [○,Q] ]とおくと r*P/Qはa0 + a1/rであり、 {{1, a0}, {0, r}}*{{1, a1}, {0, r}}*{{1, a2}, {0, r}}を[ [○,P], [○,Q] ]とおくと r*P/Qはa0 + a1/r + a2/r^2。 上の式を実際に計算してみる。 www.wolframalpha.com/input/?i=%7B%7B1,+a0%7D,+%7B0,+r%7D%7D*%7B%7B1,+a1%7D,+%7B0,+r%7D%7D*%7B%7B1,+a2%7D,+%7B0,+r%7D%7D 831 名前：デフォルトの名無しさん mailto:sage [2017/12/06(水) 21:09:44.45 ID:N+lgs3o9.net] >>801 普通のlog 2の計算には使えても >>680 には使えないかと 832 名前：デフォルトの名無しさん mailto:sage [2017/12/07(木) 00:07:53.25 ID:YC8MWngg.net] >>731 から更に縮まりました もう誰も興味が無いかも知れませんが コードいる？ 833 名前：デフォルトの名無しさん [2017/12/07(木) 09:24:10.80 ID:XIHsqoOR.net] >>801でできるはずだ。やってみる 834 名前：デフォルトの名無しさん mailto:sage [2017/12/07(木) 10:09:03.65 ID:DjN/Fbox.net] n=10^10で19.28秒にまで縮めた n=10^13くらいまでなら� 835 名前：髏Qてる間に終わる >>804 期待してます！ [] [ここ壊れてます] 836 名前：デフォルトの名無しさん [2017/12/07(木) 15:54:52.13 ID:XIHsqoOR.net] 804だけど考えてみたら面倒なんだな。 有理数(整数)で完全に求めてから割り算するのは時間かかりそうだから、 展開も、割り算も、有限で打ち切って求める精度がでるようにするのが普通? 837 名前：デフォルトの名無しさん [2017/12/07(木) 18:15:20.36 ID:wGY0QmnN.net] お題 辺の長さが10,000以下の整数である直方体について すべての面の対角線も整数となるものを全て求める 838 名前：デフォルトの名無しさん mailto:sage [2017/12/07(木) 19:52:07.65 ID:5gbe7aWB.net] 対角線を出す式を忘れたのだ〜。 数学って難しい。 839 名前：デフォルトの名無しさん mailto:sage [2017/12/07(木) 20:10:49.23 ID:bwV7uU+3.net] >>807 答えは浮かんだけど、 手元にインタプリタがないので書けない。 840 名前：デフォルトの名無しさん mailto:sage [2017/12/07(木) 20:38:16.84 ID:fmQCcJGl.net] >>808 えーと、ほら、三角形の三角形のアレ 841 名前：デフォルトの名無しさん mailto:sage [2017/12/07(木) 21:23:21.04 ID:BdlZ1dXv.net] >>805 のソース一式とexeです。 >>680 の回答となります。 fast-uploader.com/file/7068204781334/ 実行ファイルは、拡張子をexe_からexeに変えてください。 OSはWindows 64bit Vista以降 CPUはHaswell以降 で動作します。 842 名前：デフォルトの名無しさん mailto:sage [2017/12/07(木) 21:26:37.34 ID:5gbe7aWB.net] 作ってみたけど、オッセ―。 なんか数学的にやらないとダメぽ。 >>810 検索したら出てきた。 ただのHYPODだった。 843 名前：デフォルトの名無しさん mailto:sage [2017/12/07(木) 21:34:41.35 ID:5gbe7aWB.net] あ〜ん。足し算10兆回かかるとかむりげーじゃ。 どうしようかこれ。 844 名前：デフォルトの名無しさん mailto:sage [2017/12/07(木) 21:40:02.60 ID:5gbe7aWB.net] >>807 https://ideone.com/5Tu6fx C++。ギブアップ。遅すぎだ。 デバッグ不完全だからそこを忘れないで。 多分1日かけても終わらないと思う。 845 名前：デフォルトの名無しさん mailto:sage [2017/12/07(木) 21:40:16.73 ID:BdlZ1dXv.net] >>807 特に大きな工夫もなく普通に3重ループで出来ましたよ 151個かな 846 名前：デフォルトの名無しさん mailto:sage [2017/12/07(木) 21:42:04.13 ID:BdlZ1dXv.net] https://ideone.com/09jmll 847 名前：デフォルトの名無しさん mailto:sage [2017/12/07(木) 21:44:43.70 ID:8KQwIEWy.net] >>807 Java https://ideone.com/iYsIgq こうでいいのけ？ 848 名前：デフォルトの名無しさん mailto:sage [2017/12/07(木) 21:48:20.51 ID:5gbe7aWB.net] ぶ。おれは・・・いったい・・・。 だめだなぁ。才能ないなぁ。 849 名前：デフォルトの名無しさん mailto:sage [2017/12/07(木) 22:07:39.64 ID:BdlZ1dXv.net] >>817の意味がわからん 解説よろしく！ 850 名前：デフォルトの名無しさん [2017/12/07(木) 22:27:00.87 ID:XIHsqoOR.net] >>801のように積へ変換した場合、どれ位の精度・桁数が必要なのか簡単にわからないな。 >>801でやると、誤差ありの巨大な数同士の掛け算になって、その結果誤差が拡大する。 和のままやると、適当に2ベキをかければ、各項の整数部分だけ計算すればよさそうだけど。 >>801は桁を十分にとったとしても、2進10桁以上の部分も計算途中で無視はできないか。 851 名前：デフォルトの名無しさん mailto:sage [2017/12/07(木) 22:32:10.24 ID:5gbe7aWB.net] グア。題意勘違いしてた。 直方体の対角線はいらんのか。うおー。 ばかばかー。 852 名前：デフォルトの名無しさん mailto:sage [2017/12/07(木) 22:57:05.97 ID:5gbe7aWB.net] >>807 https://ideone.com/Uipgvw C++。書き直したら、>>816のパクリ見たくなった。 そしてそれでも遅いとかあかんなー。 うーん。なんでなんだろう・・・。 853 名前：デフォルトの名無しさん mailto:sage [2017/12/07(木) 23:06:46.33 ID:BdlZ1dXv.net] >>820 普通に、求めたい精度＋α の精度を保てば十分かと 演算回数はlog(n)のオーダーなので 普通にlog(2)を求める時には使える手法 854 名前：デフォルトの名無しさん mailto:sage [2017/12/07(木) 23:06:47.69 ID:8KQwIEWy.net] >>819 https://ideone.com/ZCINKa 適当にコメント付けた 855 名前：デフォルトの名無しさん mailto:sage [2017/12/07(木) 23:18:28.32 ID:8ACt5G91.net] 物体は表面だけでなく無

---

---

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

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