プログラミングのお題スレ Part22 (854レス)
上下前次1-新
抽出解除 必死チェッカー(本家) (べ) 自ID レス栞 あぼーん
リロード規制です。10分ほどで解除するので、他のブラウザへ避難してください。
700(4): デフォルトの名無しさん [] 2025/03/23(日) 23:00:51.13 ID:pi1bImlR(1) AAS
>>680680(5): デフォルトの名無しさん [] 2025/03/16(日) 23:01:39.52 ID:6JX6mCC/(1) AAS
お題:36桁以下の負でない整数で16進表記が10進表記の部分文字列であるものをすべて求めて下さい。
(例)
・1の16進表記1は10進表記1の部分文字列です
・123の16進表記7Bは10進表記123の部分文字列ではありません
・357440の16進表記57440は10進表記357440の部分文字列です
※遅い言語では15桁以下で解いても構いません
から1週間経ったので解答例を掲載
>>685685(4): デフォルトの名無しさん [] 2025/03/18(火) 21:39:06.90 ID:9hwr8+MV(1) AAS
>>683
14桁と15桁には該当値がないので、そこに列挙された数に0を追加した72個が15桁以下の答で
結果的には合っているよ。
出題時に作ったC++プログラムはideoneで36桁以下を0.43秒で完了した。これをPowerShellに
移植したプログラムは15桁以下を0.5秒未満、36桁以下を数分で完了した。
その後、改良したC++プログラムではideoneで36桁以下を0.23秒に短縮できた。
を書いたときに作ってあった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を使えば少し速くなる。
上下前次1-新書関写板覧索設栞歴
スレ情報 赤レス抽出 画像レス抽出 歴の未読スレ AAサムネイル
ぬこの手 ぬこTOP 0.050s