プログラミングのお題スレ Part22 (860ﾚｽ)
プログラミングのお題スレ Part22 http://mevius.5ch.net/test/read.cgi/tech/1691038333/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
ﾚｽ栞
685: デフォルトの名無しさん [] 2025/03/18(火) 21:39:06.90 ID:9hwr8+MV >>683 14桁と15桁には該当値がないので、そこに列挙された数に0を追加した72個が15桁以下の答で 結果的には合っているよ。 出題時に作ったC++プログラムはideoneで36桁以下を0.43秒で完了した。これをPowerShellに 移植したプログラムは15桁以下を0.5秒未満、36桁以下を数分で完了した。 その後、改良したC++プログラムではideoneで36桁以下を0.23秒に短縮できた。 http://mevius.5ch.net/test/read.cgi/tech/1691038333/685
687: 9 [sage] 2025/03/18(火) 21:42:49.00 ID:GYPHuJM6 >>685 あそうなんだ。じゃオレ様が一番乗りということでヨロ ﾉｼ http://mevius.5ch.net/test/read.cgi/tech/1691038333/687
699: デフォルトの名無しさん [] 2025/03/21(金) 20:49:29.98 ID:uwhksDTb >>697-698 Rustはよく知らないが、mainのforループ内をprintln!("{}", a);に置き換えれば解が表示されるんだよね? 実行結果を>>685で述べたC++プログラムのものと照合したら167個の解すべてが一致した。見事正解! 実行時間はC++プログラムの数倍かかるようだが、ideoneでの実行時間も見たいので載せて下さい。 http://mevius.5ch.net/test/read.cgi/tech/1691038333/699
700: デフォルトの名無しさん [] 2025/03/23(日) 23:00:51.13 ID:pi1bImlR >>680から1週間経ったので解答例を掲載 >>685を書いたときに作ってあった2つのC++プログラム https://ideone.com/KID2jR https://ideone.com/ysdd6b 1番目ではsolve関数の再帰呼び出しの対象とするx[p]の下限と上限を線形探索するが、 2番目では二分探索する。要素数10では二分探索の効果は薄いと思いきや、大分速くなった。 2番目を読み返していたらバグを発見してしまった。i = N - 1のとき63行目のa[i + 1]はa[N]となり 配列の添字範囲外アクセス。0との比較だけだし、if文の評価がどっちでも以降の処理は結局同じだから、 実害も解への影響もないが、厳格さが必要ならif ((i + 1 < N ? a[i + 1] : 0) >= 0) {と書き換えるべきだな。 実行時間への影響は無視できる。 それぞれのPowerShellへの移植版 https://ideone.com/vEGZ3D https://ideone.com/azzMa4 完全な逐語訳ではなく、PowerShellで書くと遅くなったり煩雑になったりする箇所は適宜改変した。 15桁以下の場合は64ビット整数でも桁溢れしないので、BigIntの代わりにInt64を使えば少し速くなる。 http://mevius.5ch.net/test/read.cgi/tech/1691038333/700
703: デフォルトの名無しさん [sage] 2025/03/25(火) 15:54:47.24 ID:GZ5kfx5g >>702 データ精度を揃えたアルゴリズム比較のために >>697-698をi128固定ではなくnum::BigIntにして計測して見ては？ あと出題者>>685は>>700の二つ目で(倍速以上に)短縮出来たと言っているよ http://mevius.5ch.net/test/read.cgi/tech/1691038333/703
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
1.349s*