704(1): デフォルトの名無しさん [] 2025/03/25(火) 16:11:02.68 ID:Yc/egiP0(2/3) AAS
そこまでは興味ないや
「数倍」だったのはもしかして最適化オプション付けてなかったんじゃない?ってだけの話

699(2): デフォルトの名無しさん [] 2025/03/21(金) 20:49:29.98 ID:uwhksDTb(1) AAS
>>697-698
Rustはよく知らないが、mainのforループ内をprintln!("{}", a);に置き換えれば解が表示されるんだよね?
実行結果を>>685で述べたC++プログラムのものと照合したら167個の解すべてが一致した。見事正解!
実行時間はC++プログラムの数倍かかるようだが、ideoneでの実行時間も見たいので載せて下さい。

700(4): デフォルトの名無しさん [] 2025/03/23(日) 23:00:51.13 ID:pi1bImlR(1) AAS
>>680から1週間経ったので解答例を掲載

>>685を書いたときに作ってあった2つのC++プログラム
外部ﾘﾝｸ:ideone.com
外部ﾘﾝｸ:ideone.com

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への移植版
外部ﾘﾝｸ:ideone.com
外部ﾘﾝｸ:ideone.com

完全な逐語訳ではなく、PowerShellで書くと遅くなったり煩雑になったりする箇所は適宜改変した。
15桁以下の場合は64ビット整数でも桁溢れしないので、BigIntの代わりにInt64を使えば少し速くなる。