プログラミングのお題スレ 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/ 宿題は宿題スレがあるのでそちらへ。 321 名前：デフォルトの名無しさん mailto:sage [2017/07/02(日) 13:43:30.38 ID:bHJ33QxN.net] >>314 Perl5 ideone.com/YCw1OC 桁の多い数値の幅を反映して数値間の空白の数を決めれば 数値の位置がもう少し見やすくなるとおも… 322 名前：デフォルトの名無しさん mailto:sage [2017/07/03(月) 08:12:51.85 ID:EltE6GHS.net] お題：完全なヤング図ソルバー。 ideone.com/hkUkFM 書いてみたけど、不完全なのがやっとだった。 あってるかもわからん。 図の効率がいいほど評価が上がります。 323 名前：デフォルトの名無しさん mailto:sage [2017/07/04(火) 21:28:12.76 ID:QK6Kginy.net] >>296 >>299 Perl5 ideone.com/0yJ5U9 リスト処理ではなく、先ずは正規表現と文字列処理を使って書いてみた。 3１…の3のように、食べているうちに後続の数値皿が通り過ぎてしまうような、 取りこぼしを起こし得る皿では、その数値を食べるか、あるいはスルーするか、 再帰的に両方に分岐し、木構造で計算しているが、 逆に食べている間に飛び越しを起こさないところでは、分岐が不要なので 来た順に直ちに食べることによって、枝分かれの過剰な細分化を抑制した。 それでも全探査すると、サンプルデータの三つ目まではすぐ解けるが、 四つめ以降は時間がかかりいつ終わるか分からない。 そこで、検索された食事秒数の最小値の更新状況を記録し、 同じ最小値が一定回数以上連続して繰り返し検出されるようになったら 最短値に収束したと見なし、探索を打ち切ることによって短時間で 解を出力できるようにした。打ち切り上限は10をハードコードしてあるが 今回のサンプルデータについては4か5で十分そうだ。 なお、23_ のような、2を食べることによって飛び越しを起こすポイントの 一番最後のものは,食べずにスルーして先に2を食べた方が、 次の周で早く食べ終わることは明らかだ。 これを演繹的に繰り返して、遡ってゆけば、上記のように木構造に わたって動的に計算して探索しなくても、静的に求解できそうな気がしたが 難しそうなので、見送った。 324 名前：デフォルトの名無しさん mailto:sage [2017/07/04(火) 21:31:48.78 ID:QK6Kginy.net] >>318 書き忘れたけど、食事秒数を探索中に、それまでに見つかっている最小病数を超えたら 打ち切るという、簡単な枝刈りを取り入れてあります。 連投ｽﾏｿ 325 名前：デフォルトの名無しさん mailto:sage [2017/07/04(火) 23:51:29.56 ID:sQGcZTdy.net] >>318 枝刈りで最短を刈り取ってしまったら駄目じゃないか 例えば "3324" -> 15秒 にならないな 326 名前：318 mailto:sage [2017/07/06(木) 00:31:45.46 ID:iCfNzc8Y.net] >>320 誤解� 327 名前：ﾅす。 枝刈りは、ある探索中の枝において始点から既に経過した秒数が それまでの別の枝における探索で最後まで食べた最小秒数を超過したら、 現在の枝の探索はもうこれ以上進んでも秒数が増える一方なので打ち切って 別の枝の探索に移るというものなので大丈夫です。 "3324" の最短秒数を探索すると 15秒になります。 [] [ここ壊れてます] 328 名前：デフォルトの名無しさん mailto:sage [2017/07/06(木) 00:52:46.56 ID:ywrsmrRJ.net] >>321 あれ、変だな >>318のリンク先のコードで"3324"を計算すると 16 になるんだけどこっちの環境が変なのかな？ 同様に"3328"、"3364"は最短19秒だけど>>318だと20になった 329 名前：318 mailto:sage [2017/07/06(木) 01:20:52.00 ID:iCfNzc8Y.net] >>322 同じコードをideoneに張りなおして3324を入力して実行してみました。 ideone.com/vXrTp8 ソースを一箇所編集しています。 31 die if $hit >= 20; # 一定以上同じ最小値が繰り返し計算されたら収束と判定し脱出 の繰り返し回数上限判定地を10から20に増やしています。 3324は15になりますが、15が登場するのは11回目以降でそれまで16が出続けます。 3364も20が10回繰り返した後19が出て続きます。 お手数おかけしますが 一定以上同じ最小値が繰り返し計算されたかの判定値を10より多くして 評価してください。 330 名前：318 mailto:sage [2017/07/06(木) 01:35:51.32 ID:iCfNzc8Y.net] >>323 3324と3364の解を見ていて気が付いた点があります。 一定以上同じ最小値が繰り返し計算されたかの判定値を20にしていますが、 3324の15や3364の19は20ではなくて13回しか現れず、これが最小値のため 解として表示されています。 これは、3324の15や3364が4桁しかないので、 最小値が20回現れる前に全探査が完了し、その中で見つかった最小値を 解として表示していることによります。 >>318の一定回数繰り返したら収束とみなすという判定方法は、 ニュートン法のような数値計算では有効ですが、 >>296の問題の解の判定方法としては適切とは言えないかもしれませんね…orz 331 名前：デフォルトの名無しさん mailto:sage [2017/07/06(木) 01:53:08.89 ID:bBo7q2K6.net] 3324を拡張した887654329は閾値どれくらい増やせば対応できるんですかね 332 名前：318 mailto:sage [2017/07/06(木) 02:06:40.59 ID:iCfNzc8Y.net] >>325 延々探索を続けないと解に至らないかもしれない入力については 定数で打ち切りを決めるこの解法じゃ解に至りにくいかもしれない。 887654329がそういったカテゴリーに属する入力かというと ﾁｮｯﾄ分からない。 なので適切な閾値はこれだと断言しにくいです。 さーせん 333 名前：デフォルトの名無しさん mailto:sage [2017/07/06(木) 21:08:21.84 ID:ywrsmrRJ.net] >>326 結局>>321は大嘘だったし、閾値20の>>323にしたところで 例えば"14432"は最短にならないし 閾値が決められないならその解法はやはり駄目だな 334 名前：318 mailto:sage [2017/07/06(木) 22:03:39.91 ID:0agEc1HZ.net] >>327 閾値20で打ち切ると最小に至らない入力もあるのはそうだけど、 計算しても最小を更新しない枝に降りずに切り上げてくる>>321は嘘ではないよ。 335 名前：318 mailto:sage [2017/07/06(木) 22:08:34.07 ID:0agEc1HZ.net] 見込みの無い枝をもっと早めに切り上げらる方法がありそうだと気が付いた。 それによって20で打ち切るようなやり方を改善できればいいんだけれども… それでも計算量が増えていくと、真の解に至るまでにかかる時間が増大して とけなくなる 336 名前：デフォルトの名無しさん [2017/07/06(木) 23:01:53.78 ID:ywrsmrRJ.net] >>328 閾値20で打ち切るのは枝切りじゃないという主張のようだけど 打ち切るという動作は枝切り以外の何物でもない >>318は”3324”の最短に到達しないから>>321の > "3324" の最短秒数を探索すると 15秒になります。 というのも嘘 337 名前：318 mailto:sage [2017/07/06(木) 23:19:13.87 ID:0agEc1HZ.net] >>330 絡むね。そんな暇あったらコードでも書けばいいのにｗ 閾値20でその入力については解の探査を� 338 名前：~めて 別の枝に移らず次の入力データに移るのはどちらかといえば中断で、 枝かりではないでしょ。 >319 > >>318 > 書き忘れたけど、食事秒数を探索中に、それまでに見つかっている最小病数を超えたら > 打ち切るという、簡単な枝刈りを取り入れてあります。 にかいてあるでしょうに。 >>318は”3324”の最短に到達しないから>>321の > "3324" の最短秒数を探索すると 15秒になります。 >というのも嘘 これは10回の打ち切りの緩和を書きもらしたんだよ。 何が狙いで、こだわって絡んでくるやらねぇ。 [] [ここ壊れてます] 339 名前：318 mailto:sage [2017/07/06(木) 23:37:37.26 ID:0agEc1HZ.net] 「打ち切る」という言葉を >318 >… >同じ最小値が一定回数以上連続して繰り返し検出されるようになったら >最短値に収束したと見なし、探索を打ち切ることによって短時間で >解を出力できるようにした。打ち切り上限は10をハードコードしてあるが では「その入力に対する求解を中断する」ところで使い、 >319 > >>318 > 書き忘れたけど、食事秒数を探索中に、それまでに見つかっている最小病数を超えたら > 打ち切るという、簡単な枝刈りを取り入れてあります。 では「その枝の下の方への探索をせず、別の枝の探索に移る」枝刈りの ところで使ったのが誤解を招いてしまったのかな… 340 名前：デフォルトの名無しさん mailto:sage [2017/07/07(金) 04:22:27.25 ID:pbX9YCbr.net] 3次の動的計画法ってどんだけメモリ食うんや？ 341 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 03:20:24.48 ID:hDxZO8qP.net] お題：　自然数Nの平方根を整数部含めて(1000*N)桁求めたとき、出現する0の個数を数える たとえば、N = 4の時ルート4を4000桁（整数部1桁＋小数部3999桁）求めたとき、出現する0の個数は3999個 N = 3 => ? N = 5 => ? N = 7 => ? 342 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 03:22:50.68 ID:5gcIwgbE.net] ブロックチェインの新手のコイン発掘か？ 343 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 03:59:02.35 ID:kzKE4jeR.net] >>334 Ruby require 'bigdecimal' [3, 4, 5, 7].each{|i| n = 1000*i - 1 puts "N = %i => %i"%[i, ("%.#{n}f"%BigDecimal(i).sqrt(n)).count(?0)] } N = 3 => 2956 N = 4 => 3999 N = 5 => 4956 N = 7 => 6954 344 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 04:25:25.94 ID:kzKE4jeR.net] >>336はミス。0がこんなに多いわけがない require 'bigdecimal' [3, 5, 7].each{|i| n = 1000*i - 1 puts "N = %i => %i"%[i, BigDecimal(i).sqrt(n).floor(n).to_s(?F).count(?0)] } N = 3 => 309 N = 5 => 492 N = 7 => 738 345 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 07:13:48.73 ID:hDxZO8qP.net] >>337 N = 5の場合が間違ってると思う 多分、丸めモードの関係か、精度が足りてないと思われる 346 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 09:51:11.17 ID:3gkxwDpM.net] >>334 C++ #include <iostream> #include <string> #include "gmpxx.h" int main () {   int sq_me;   while( std::cin >> sq_me ){     int prec = 1000*sq_me, cnt = 0;     mpf_class sq_out = sqrt( mpf_class(sq_me, prec*4) );     mp_exp_t exp;     auto str = sq_out.get_str( exp,10,prec );     for( auto it=str.begin(); it!=str.end(); it++ ) if( *it=='0' ) ++cnt;     std::cout << "N = " << sq_me << " => " << cnt+prec-str.length() << '\n';   } } N = 3 => 309 N = 5 => 493 N = 7 => 738 N = 11 => 1079 N = 13 => 1305 N = 17 => 1664 N = 19 => 1875 N = 23 => 2265 N = 29 => 2911 N = 31 => 3113 N = 37 => 3795 N = 41 => 4095 N = 43 => 4312 N = 47 => 4798 N = 53 => 5340 347 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 11:54:07.74 ID:H5pSyGdF.net] >>334 Squeak/Pharo Smalltalk | sqrt | sqrt := [:n :m | 　"ref. https://xar.sh/post/67066374255/ " 　| a b | 　a := 5 * n. b := 5. 　[:exit | [ 　　a >= b ifTrue: [a := a - b. b := b + 10] ifFalse: [ 　　　b log > m ifTrue: [exit v 348 名前：alue] ifFalse: [ 　　　　a := a * 100. b := b // 10 * 100 + (b \\ 10) 　　　] 　　] 　] repeat] valueWithExit. 　b ]. #(3 5 7) collect: [:i | i -> (((sqrt value: i value: i*1000) asString first: i*1000) occurrencesOf: $0)] "=> {3->309 . 5->493 . 7->738}" [] [ここ壊れてます] 349 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 12:18:57.24 ID:hDxZO8qP.net] >>339 N = 29とN=41の場合が間違ってる可能性？　それ以外は正しい模様 N = 29 => 2912、N = 41 => 4094 じゃなかろうか >>340 合ってる 350 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 12:48:13.59 ID:1hnJaOYb.net] >>334 Perl5 ideone.com/fAyh2l 351 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 13:10:39.20 ID:1hnJaOYb.net] >>334 Perl5 ideone.com/cMBD8o >>342 をもう少しすっきり書けたので差し替え。 352 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 13:31:31.09 ID:3gkxwDpM.net] >>341 > N = 29 => 2912、N = 41 => 4094 じゃなかろうか それが正しいようです GNU MPだとどうしても最後の桁は四捨五入?されるようで 任意のNに対して正確な答えを出すのは面倒なので修正は断念 353 名前：デフォルトの名無しさん mailto:sage [2017/07/09(日) 10:26:36.71 ID:aJSGzdPS.net] 結局バイナリーツリーになっちゃったなぁ。むずかし。 354 名前：デフォルトの名無しさん mailto:sage [2017/07/09(日) 10:55:01.51 ID:xLkjNLhf.net] >>344 考え直したら面倒じゃなかった >>334 C++ codepad.org/k0Sq8Fqo N=10000くらいまでなら現実的な時間で計算出来そうだ 355 名前：デフォルトの名無しさん mailto:sage [2017/07/09(日) 11:25:12.20 ID:nhQrw0mT.net] N=100000, 1億桁のくらいなら現実的な時間で出来る 丸めは切り捨て？四捨五入？ 356 名前：デフォルトの名無しさん mailto:sage [2017/07/09(日) 11:33:40.13 ID:nhQrw0mT.net] ルートの計算は速い 整数のルートは特に速い 357 名前：346 mailto:sage [2017/07/09(日) 12:21:20.78 ID:4Kodr3MO.net] >>347 GNU MPだとget_str() とか gmp_sprintf() では四捨五入されるようなので floor() であらかじめ切り捨ててから get_str() した 358 名前：デフォルトの名無しさん [2017/07/09(日) 12:57:37.64 ID:DBjzEn12.net] ルートの問題で初めてきたが、これってゼロの個数に上限があるのか? 簡単に求まるのか? 連続するゼロの個数の最大だろ? 無理数は規則なく無限に続くから、ゼロの個数ももし1000個連続が見つかれば、1001個もいつかでるとおもうんだが。 359 名前：デフォルトの名無しさん mailto:sage [2017/07/09(日) 13:14:46.15 ID:df6kAKcY.net] 最大って何の話しとるんや 360 名前：デフォルトの名無しさん [2017/07/09(日) 13:28:51.97 ID:DBjzEn12.net] もとめる桁数のほうに上限があったのか、それを見逃してた。 361 名前：デフォルトの名無しさん mailto:sage [2017/07/09(日) 13:45:03.68 ID:NvRZfELm.net] 連続する個数でもないぞw 362 名前：デフォルトの名無しさん [2017/07/09(日) 13:51:59.10 ID:DBjzEn12.net] どっちも間違えたな、ゼロの総数だったか。 363 名前：デフォルトの名無しさん mailto:sage [2017/07/09(日) 19:14:37.92 ID:6MYOcrZ9.net] >>349 floorを行った後の結果に誤差は無い という検証は出来てるの？ 何もしてないなら、それはたまたま偶然当たったっていうだけだぞ ていうか、君には聞いてない 出題者の意図を聞いてる 364 名前：デフォルトの名無しさん [2017/07/11(火) 15:16:56.21 ID:1hL73PK3.net] √2でなるべく長い0の連続をみつけるは? 365 名前：デフォルトの名無しさん [2017/07/11(火) 15:49:47.43 ID:QxseLuPf.net] >>355 君には向いて無いよ 366 名前： ◆QZaw55cn4c mailto:sage [2017/07/11(火) 16:29:49.99 ID:ZfeFayuI.net] >>355 >floorを行った後の結果に誤差は無い >という検証は出来てるの？ ぱっとみ当然だと思うんだが >>356 何桁求めるか指定しないと意味がないのでは？ 367 名前： ◆QZaw55cn4c mailto:sage [2017/07/11(火) 16:35:18.57 ID:ZfeFayuI.net] >>358 ん、考え直した 10進に変換した結果にて 99999 とかが末尾にあるようでは、余分の計算はしないと 368 名前：いけないね [] [ここ壊れてます] 369 名前：デフォルトの名無しさん mailto:sage [2017/07/11(火) 18:55:08.87 ID:dSS1j36W.net] [][Tebla][] } 000-"Yob*RtStrike"[%Kil\]MO,fla>%$9999VLTS 001-GYORLith"0\R"/"ESUBA"%$% HADO-"EM","L","O","NU"###END 370 名前：デフォルトの名無しさん mailto:sage [2017/07/14(金) 06:57:35.22 ID:PYQ8V1MO.net] >>296 ideone.com/VzYVY9 C++。解けた気がする。 状態をメモ化してみた。 何で動いてるのか自分でもよくわからない。 暇だったので解いてみた。 371 名前：デフォルトの名無しさん mailto:sage [2017/07/14(金) 07:42:51.88 ID:PYQ8V1MO.net] あー多倍長精度演算ほしー。もちろん標準で。 372 名前： ◆QZaw55cn4c mailto:sage [2017/07/14(金) 07:55:58.80 ID:TDGI45F0.net] >>362 私も欲しかったので作ってしまった、今 >>334 を奮闘中 373 名前：デフォルトの名無しさん mailto:sage [2017/07/14(金) 07:56:52.78 ID:PYQ8V1MO.net] >>363 それはすごいな。 後々破棄するようなものを作るモチベーションが出てこないよ。 374 名前：デフォルトの名無しさん mailto:sage [2017/07/14(金) 07:57:44.37 ID:TDGI45F0.net] >>364 書き捨てに慣れてしまったんだ‥ 375 名前：デフォルトの名無しさん mailto:sage [2017/07/14(金) 07:59:21.83 ID:PYQ8V1MO.net] >>365 あはは・・・。 コード書き捨てるのは良いけど、道具書き捨てるのは俺には向いてないわ。 なので、標準待ち。 376 名前：デフォルトの名無しさん mailto:sage [2017/07/14(金) 09:33:33.04 ID:gEZu1299.net] boostという任意倍長の計算Libraryがあります。 C++では使えるそうです。 377 名前：デフォルトの名無しさん mailto:sage [2017/07/14(金) 09:38:45.73 ID:PYQ8V1MO.net] >>367 Boostも良いんだけどね。残念なことにあれは実験環境で準標準って扱いなんだよなぁ。 あれから取り入れられるライブラリも多いんだけど、標準じゃないからね。 残念なことに。 378 名前：デフォルトの名無しさん mailto:sage [2017/07/14(金) 12:49:16.12 ID:gnKUWanp.net] まあ標準ライブラリしか使わない縛りをしたければ好きにすればいいんじゃない？ 379 名前：デフォルトの名無しさん mailto:sage [2017/07/14(金) 14:27:07.19 ID:JyiCltLg.net] 車輪の再発明 380 名前：デフォルトの名無しさん mailto:sage [2017/07/14(金) 14:31:43.15 ID:DwybRUfK.net] 競プロみたいな相手方の環境使う物だと標準と準標準の差はでかい 自分の環境なら導入すればいいだけだが 381 名前： ◆QZaw55cn4c mailto:sage [2017/07/14(金) 18:52:31.62 ID:TDGI45F0.net] >>370 個体発生は系統発生を繰り返す 382 名前：デフォルトの名無しさん mailto:sage [2017/07/15(土) 12:42:06.98 ID:odVkuNfb.net] >>361 厳密解を出しているのなら、チャレンジ (わかって近似値解狙いなら気にしないで) "14432" と "887654329" 両方とも既出の"貪欲つぶし"(?)数列 "14432"は 20秒 (ゼロインデック順で02341) "887654329"は 80秒(同123456708)でいける。 383 名前：デフォルトの名無しさん mailto:sage [2017/07/15(土) 14:59:21.20 ID:OEoVgGO0.net] >>373 ideone.com/cBzPSj C++。それ解くとほかの問題が解けなくなる。 厳密解のつもりだったが、ちょっと自分の領分超えてるなぁ。 うまくいかないものだ。 真実が奥の方にあると貪欲法は弱いな。Orz 384 名前：デフォルトの名無しさん [2017/07/16(日) 16:33:07.01 ID:8ZBD9z9c.net] お題： 自分用多倍長整数演算関数 …って思ったけど、処理系の標準ではないとか、仕事でGNU MP使っては駄目とかの 制約で、簡易的なもの(乗算くらいまでとか)を書いた事ある人は少なくないと見た。 385 名前：デフォルトの名無しさん mailto:sage [2017/07/16(日) 18:30:49.57 ID:8+Akms5T.net] 多倍長整数演算がサポートされている言語を使う 終わり 386 名前： ◆QZaw55cn4c mailto:sage [2017/07/16(日) 18:54:09.85 ID:eA1jggM5.net] >>375 C++98 codepad.org/hUObVCsR オートボクシング等はなく便利にはできていない． 387 名前：デフォルトの名無しさん [2017/07/16(日) 2 ] [ここ壊れてます] 388 名前：0:34:05.63 ID:yctBkD01.net mailto: 掛け算の実装がキモだろう。 ここがボトルネックになるはず。 ここができると円周率とか、ルート計算も高速化できるはず。 [] [ここ壊れてます] 389 名前： ◆QZaw55cn4c mailto:sage [2017/07/16(日) 20:36:24.09 ID:eA1jggM5.net] >>378 うん，FFTを使うそうだが‥いまいちよくわからない 390 名前：375 mailto:sage [2017/07/16(日) 20:41:46.81 ID:8ZBD9z9c.net] >>376 仕事で言語を選べる立場になってみたいものだわ。 この言語でやってってののは多々あるけど…orz >>377 Karatsuba-Ofman法を目指してごーごー 391 名前：デフォルトの名無しさん mailto:sage [2017/07/17(月) 22:48:25.95 ID:5edeqhg+.net] >>296 手計算で計算出来るレベルにまで計算量を減らせた もちろん数学的な裏付け付きで ある条件を見たせば一瞬で求まる "123456789123456789" > 98秒 残念ながら、これだけはその条件を満たしてない 392 名前：デフォルトの名無しさん mailto:sage [2017/07/18(火) 06:37:17.84 ID:nFCFlf58.net] >>381 22とか2323もその条件を満たしてない感じ？ 393 名前：デフォルトの名無しさん mailto:sage [2017/07/18(火) 07:37:05.09 ID:Ew0RSScO.net] 22 は微妙 2323 は大丈夫 394 名前：デフォルトの名無しさん mailto:sage [2017/07/18(火) 07:41:44.22 ID:Ew0RSScO.net] まだコードになってないんで、 コードになったらアップします 寿司を食べる時間 < レーンの回転周期 という前提をつけちゃおうと思ったけど、 つけない方が良さそうですね 寿司を食べる時間がレーンの回転周期の整数倍の寿司は ちょっと特別な処理が必要 395 名前：デフォルトの名無しさん mailto:sage [2017/07/18(火) 08:01:32.43 ID:Ew0RSScO.net] 整数倍の寿司が無いもので 条件に当てはまらない最小は 2222 かな 396 名前：デフォルトの名無しさん mailto:sage [2017/07/18(火) 08:49:51.93 ID:YLlwVFMJ.net] >>334 SageMath ttps://sagecell.sagemath.org/?q=brdclf 普通に(？)多桁のisqrt()なので何の捻りも無し。 397 名前：386 mailto:sage [2017/07/18(火) 09:39:56.20 ID:YLlwVFMJ.net] >>339 つ mpz_sqrt() 398 名前：デフォルトの名無しさん mailto:sage [2017/07/19(水) 18:12:29.37 ID:Np9hKHT2.net] >>296 >>373 ideone.com/B9vl8l C++。結局、i7-6700のmem2G使って7分で解けた。 どうしようもない位遅いな。 でも一応題意には添えたと思う。 もう見たくない・・・。Orz 高速化するにはインラインアセンブリ使うか、スレッド分割できるようなアルゴリズムかんがえるか。 よくわからんけど、数学で頑張ってる人に期待だ。 399 名前：386 mailto:sage [2017/07/20(木) 01:57:16.81 ID:Q7XnESC/.net] 100のべき乗に変更 ttp://sagecell.sagemath.org/?q=mciykc 400 名前：デフォルトの名無しさん mailto:sage [2017/07/21(金) 15:21:18.13.net] >>296 ideone.com/mXPglY C++。試しに再起化してみたら処理速度倍になった。 自分の環境では3分ちょいで解ける。 相変わらずメモリ馬鹿食いするけど。 もう俺には無理。 俺の中では終了でーす。Orz 401 名前：デフォルトの名無しさん mailto:sage [2017/07/22(土) 08:54:36.28 ID:OQXA8cUK.net] >>388 数学で頑張ってる人だけど、 もうちょっとまって >>296の問題だけなら簡単だけど、 まだ全体を解明できてない というか、忙しくて>>381から進んでない 402 名前：デフォルトの名無しさん mailto:sage [2017/07/22(土) 08:55:28.19 ID:OQXA8cUK.net] このスレが無くならないうちに解明します 403 名前：デフォルトの名無しさん mailto:sage [2017/07/22(土) 10:43:30.03 ID:apsnR2Z0.net] >>391 wktkデス！ コード見るのが好きなのでぜひ完走していただけたらと思います。 404 名前：デフォルトの名無しさん mailto:sage [2017/07/23(日) 11:26:56.94 ID:ipiEUPYV.net] >>375 のほかの実装はでてこないねぇ‥ 405 名前：デフォルトの名無しさん mailto:sage [2017/07/23(日) 12:53:55.68 ID:7fREas1L.net] >>394 使えるコードにするためには、規模がでかくなりすぎるから 406 名前：デフォルトの名無しさん mailto:sage [2017/07/23(日) 14:15:20.13 ID:ipiEUPYV.net] C/C++ で最長1000行ぐらいとみて、2日ぐらいあれば、とりあ� 407 名前：ｦず動く 土日で仕上がってくるんじゃないかと期待してたんだが [] [ここ壊れてます] 408 名前：デフォルトの名無しさん mailto:sage [2017/07/23(日) 14:18:11.58 ID:7fREas1L.net] 速度が考えられてないコードなんて実用にはならないよ 409 名前：デフォルトの名無しさん mailto:sage [2017/07/23(日) 14:21:31.79 ID:7fREas1L.net] ていうか、 コードに対する条件とか サポートする機能とか 条件が無さすぎる 410 名前：デフォルトの名無しさん mailto:sage [2017/07/23(日) 14:24:57.75 ID:ipiEUPYV.net] 速度‥か‥ どうしてもローテートとかキャリーフラグとかを使いたいから、これはアセンブラの領域になるね よくみかけるアセンブラ中毒者が今頃爪を研いでいるのだろうか？ 411 名前：デフォルトの名無しさん mailto:sage [2017/07/23(日) 14:25:42.29 ID:ipiEUPYV.net] >>398 そこは「自分用」だから自由に決めていいんでないかい？ 412 名前：デフォルトの名無しさん [2017/07/23(日) 14:49:34.77 ID:TcY6qE9r.net] >>394 当日に >>305 で >>390 より10倍以上早いのがでているだろう。 しかも 計算量まで書いてある 413 名前：デフォルトの名無しさん mailto:sage [2017/07/23(日) 14:53:19.94 ID:ipiEUPYV.net] >>401 お題が違うのでは？ 414 名前：デフォルトの名無しさん [2017/07/23(日) 15:05:28.62 ID:TcY6qE9r.net] >>402 >>394 確かに違った、すいません。 c++多倍長なら、karatsubaにも対応して300行くらいの以下をパクって使うのも一案 sites.google.com/site/indy256/algo_cpp/bigint 415 名前：デフォルトの名無しさん mailto:sage [2017/07/23(日) 15:09:21.91 ID:ipiEUPYV.net] >>403 base 10進ならば、表示（operator<<) が楽でいいね、なるほど、それは思いつかなかった 416 名前：デフォルトの名無しさん mailto:sage [2017/07/23(日) 16:51:44.88 ID:7fREas1L.net] >>399 通常、 処理時間のほとんどが乗算 乗算のほとんどがFFT アセンブラの出番は当分先 417 名前：デフォルトの名無しさん mailto:sage [2017/07/23(日) 16:52:43.21 ID:7fREas1L.net] FFTのライブラリをどこからか持ってくるのでもいいけど、 それなら素直に多倍長ライブラリを持ってくれば ってことになる 418 名前：デフォルトの名無しさん mailto:sage [2017/07/23(日) 16:54:07.19 ID:7fREas1L.net] 今は浮動小数点演算が速いので、 カラツバの出番はあまりない 419 名前：デフォルトの名無しさん mailto:sage [2017/07/23(日) 18:50:17.74 ID:5CSy1R8t.net] 基数を10のべき乗にするとか(printf()的なものが簡単だから)、乗算はunsigned shortやintとの 乗算に限るとか、除算無しとかいうのは… プログラムの本体に組み込まれてしまって、再利用可能なライブラリの形で括りだされてる事の 方が少ないかｗ 420 名前：デフォルトの名無しさん mailto:sage [2017/07/24(月) 00:48:44.80 ID:XgJeE+LA.net] >>6-285 SageMath ttp://sagecell.sagemath.org/?q=veftjc 421 名前：デフォルトの名無しさん mailto:sage [2017/07/24(月) 18:24:00.06 ID:UuUAOyUA.net] >>408 裁定ラインとしては、乗算は Bigint×Bigint、および除算の実装ですかね、でも足し算の回数での乗算や引き算の回数での除算は嫌ですね

---

---

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

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