プログラミングのお題スレ Part22 (854ﾚｽ)
プログラミングのお題スレ Part22 http://mevius.5ch.net/test/read.cgi/tech/1691038333/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
ﾚｽ栞
ﾘﾛｰﾄﾞ規制
です｡10分ほどで解除するので､
他のﾌﾞﾗｳｻﾞ
へ避難してください｡
282: ◆QZaw55cn4c [sage] 2024/02/24(土) 14:25:41.40 ID:NZEL8Kud 異なる自然数 a, b (a > b) における a^3 - b^3 を「a, b の三乗差」と呼ぶことにする。 異なる5通りの組(a, b) (c, d) ... (j, k) について三乗差がすべて相等しいとき その組(a, b)...(j, k) および三乗差自体を求めよ 異なる6通りの組で三乗差が相等しい場合があるかも検討せよ http://mevius.5ch.net/test/read.cgi/tech/1691038333/282
283: デフォルトの名無しさん [] 2024/02/24(土) 16:47:38.19 ID:KRWvIUHe >>282 [(1134, 357), (1155, 504), (1246, 805), (2115, 2004), (4746, 4725)] a^3 - b^3 == 1412774811 http://mevius.5ch.net/test/read.cgi/tech/1691038333/283
285: デフォルトの名無しさん [sage] 2024/02/24(土) 18:16:29.01 ID:O6Cw1j13 >>282 ruby https://ideone.com/wBX9Rs ・そのまま版 ・5秒じゃ? http://mevius.5ch.net/test/read.cgi/tech/1691038333/285
287: デフォルトの名無しさん [] 2024/02/24(土) 22:30:55.28 ID:mNVJyIZh >>282 aが5000以下限定で>>283の解はRで5秒以内に求められた。8〜9行目は下三角行列の要素番号から 行番号と列番号を求めているだけで、>>282を解く特別なアルゴリズムというわけではない。 https://ideone.com/w4X3DC http://mevius.5ch.net/test/read.cgi/tech/1691038333/287
288: 285 [sage] 2024/02/25(日) 08:52:58.18 ID:M1xmyD2F >>282 ruby 2.5.5 https://ideone.com/4GdMaO ・285の無駄なループ回数を削減 ・でも5秒じゃ? http://mevius.5ch.net/test/read.cgi/tech/1691038333/288
289: デフォルトの名無しさん [] 2024/02/25(日) 21:06:57.77 ID:CUQUyFSy >>282 >>287は下三角行列の要素番号から列番号を求めるのに2次方程式を解くのが分かりにくかったから、 各列の最下行の要素番号を計算しておいてそれを二分探索するように変更した。 https://ideone.com/Tefgkh n = 25000で実行してみても、n = 5000ときの解のa, bを両方とも2, 3, 4, 5倍した解しか別に 見つからなかった。 http://mevius.5ch.net/test/read.cgi/tech/1691038333/289
290: デフォルトの名無しさん [] 2024/02/26(月) 22:18:39.21 ID:CjcYgBx5 >>282 >>289と似た手順でC++ https://ideone.com/nFRsrK Rではソートする前に重複値だけを抽出しているが、C++のunique関数はソート済みデータにしか 使えないので使っていない。 http://mevius.5ch.net/test/read.cgi/tech/1691038333/290
291: 288 [sage] 2024/02/27(火) 21:45:30.42 ID:nu8aoj+0 >>282 c https://ideone.com/eM18H1 ・288の移植 http://mevius.5ch.net/test/read.cgi/tech/1691038333/291
292: デフォルトの名無しさん [] 2024/02/27(火) 22:30:42.88 ID:BJV11H6M >>282 下三角行列の各列内の要素は昇順で既に並んでいるのに、>>290は下三角行列の全要素を ソートして無駄なので、列のマージに変更（要するにマージソートを途中段階から開始） したら少し速くなった。 https://ideone.com/EZSvB3 n = 10000でも5秒以内に終わった。 https://ideone.com/huQiBe http://mevius.5ch.net/test/read.cgi/tech/1691038333/292
293: 288 [sage] 2024/02/28(水) 22:00:05.18 ID:7ZY4TL6q >>282 c++ https://ideone.com/teo5Mm ・288の移植 >>282 rust https://ideone.com/G94aN3 ・288の移植 http://mevius.5ch.net/test/read.cgi/tech/1691038333/293
294: デフォルトの名無しさん [] 2024/02/28(水) 23:21:09.16 ID:FCtvUtiC >>282 >>292とは別の方法で>>290を高速化 https://ideone.com/QxjmyT 1³, 2³, 3³, …, 5000³をD = 5001で割った余りはすべて異なる値になるから、d = a³ − b³を Dで割った余りはどれか1つの値に偏ることなく均等に分布する。dをDで割った余りによりdを 区分すれば、各区分に入る個数はどれも多すぎないのでソートに時間が余りかからない。 Dの値はconstexpr関数によりコンパイラに計算させている。n = 10000, 15000のときは それぞれD = 10002, 15009になる。 http://mevius.5ch.net/test/read.cgi/tech/1691038333/294
295: 291 [sage] 2024/02/29(木) 22:20:45.85 ID:HlaTo1dC >>282 c https://ideone.com/JnJpJW ・291から省メモリ化 旧：unsigned int values[10]; 新：unsinged short values[4]; http://mevius.5ch.net/test/read.cgi/tech/1691038333/295
296: デフォルトの名無しさん [] 2024/03/01(金) 22:22:26.10 ID:6k2oCbjk >>282 C++ https://ideone.com/1c4s5I >>294はa, bの二重ループ内でa³ − b³をD = 5001で割った余りrにより区分していたが、 rのループ内でa, bを変化させるように変更したら、2次元配列がなくなってすっきりした。 その結果、メモリ使用量が激減し、nが大きい場合でも実行できるようになった。 http://mevius.5ch.net/test/read.cgi/tech/1691038333/296
298: デフォルトの名無しさん [] 2024/03/01(金) 22:24:42.81 ID:6k2oCbjk >>282 C++ https://ideone.com/tM1cuo >>296のrのループ内でa³ − b³をD2 = 5003で割った余りr2により区分し、それぞれの区分ごとに 解を探すようにしたら速くなった。ただし、nが大きい場合にはかえって遅くなる。 http://mevius.5ch.net/test/read.cgi/tech/1691038333/298
300: デフォルトの名無しさん [] 2024/03/03(日) 22:19:54.92 ID:ZEDvt9uH >>282 C++ https://ideone.com/LEU7EV >>298でnを大きくするにつれ>>296に対する高速化効果が薄れていくのは、ABをvectorでなく 配列にしたらある程度改善された。n = 5000のときの実行時間は>>296の半分以下になった。 ただし、n = 1000000まで大きくすると、296よりやっぱり遅くなる。 >>299 どんなプログラムを書いたのか見せて。 http://mevius.5ch.net/test/read.cgi/tech/1691038333/300
301: デフォルトの名無しさん [] 2024/03/06(水) 22:35:52.23 ID:lIZep5aT >>282 C++ https://ideone.com/PG6UiY >>300の実行時間を分析すると、最も時間が掛かっているのは46〜と47行目だと判明した。 そこで配列ABの第1次元と第2次元を入れ替えてみると、n = 5000では変わらないが、 1万, 2万, 5万, 10万, 20万では35%前後高速になった。これは、改良前には第2次元の添字が 小さい要素に書き込みが集中しているため、改良後のように第1次元に入れ替えた方が 纏まったメモリ領域に書き込みが集中しキャッシュの効きが良くなるからだと考えられる。 一方、n = 100万で高速化しないのは、書き込み集中領域が大きすぎるからだろう。 https://ideone.com/6RzW0n n = 100万の場合にはr2の値によってデータを多数の列へ振り分けるのをやめ、列を1つにして、 その内部でr2の値により2種類に区分し、それぞれの内部で2種類にさらに区分し、…と再帰的に 区分していけば（要するにクイックソートの変形版）、1つの配列内での要素のスワップだけで済み、 キャッシュの効きが改善されるとの予想通り、n = 100万で実行速度は>>296より25%速くなった。 (原理的には>>300より非効率なのでn = 5000では>>300より当然遅い) http://mevius.5ch.net/test/read.cgi/tech/1691038333/301
303: デフォルトの名無しさん [] 2024/03/09(土) 22:13:47.64 ID:C74EWG6S >>282 C++ https://ideone.com/xQD1W8 関数mainのループで配列A, B, Pに書き込まずdにだけ書き込むようにし、関数FindDuplicatesで dの添字Pではなくdそのものをソートするように変えて、n = 1000000の場合に>>301より10%高速化。 関数PrintSolutionでa, bをmainでと同じ方法で再計算するのは非効率だが、PrintSolutionは僅か12回しか 呼ばれないため、全体の実行時間への影響は無視できる。 http://mevius.5ch.net/test/read.cgi/tech/1691038333/303
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.035s