プログラミングのお題スレ Part22 (854ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
680(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桁以下で解いても構いません
682(1): 9 [sage] 2025/03/18(火) 16:05:22.66 ID:GYPHuJM6(1/5) AAS
>>680 Perl5、ナイーブな処理方式だと時間がかかり過ぎで最後まで解けないおそれがあるが、なかなかほかに回答者が現れないし、
出現傾向を見るだけでも…と思って、16進数の桁にa-fの現れる値をskipするナイーブな処理方法で。
$m = sprintf '%x', 9 x 15; # 10進で15桁まで
print $m . ' '. hex($m)."\n";
$m =~ s/[a-f]/9/g;
print "1 .. 0x$m\n";
print "".localtime."\n";
for (1 .. $m) {
$d = hex($_);
if (0 <= index($d, $_)) {
$n++;
print "$d, 0x$_\n";
}
}
print "".localtime."\n";
print "$n count found";
684(1): デフォルトの名無しさん [sage] 2025/03/18(火) 16:35:06.57 ID:lVLkTjWA(1) AAS
>>680
ruby
(0..10**16-1).each{|e| puts "#{e},0x#{e.to_s(16)}" if %r|[a-f]|!~e.to_s(16)}
690: デフォルトの名無しさん [sage] 2025/03/19(水) 08:44:27.79 ID:khMnA4jS(2/2) AAS
>>680
ruby 遅いけど
i=0
while i<10**16
if %r|[a-f]|=~i.to_s(16)
i=i.to_s(16).gsub(%r|[a-f].*|){|e| e.gsub(%r|.|,"f")}.hex
else
puts "#{i},0x#{i.to_s(16)}" if %r|#{i.to_s(16)}|=~i.to_s
end
i+=1
end
697(6): デフォルトの名無しさん [sage] 2025/03/21(金) 12:56:29.73 ID:CgJbZEAu(1/2) AAS
>>680 Rust
fn odai_680() -> Vec<i128> {
let mut answer = vec![0];
let n_max = (0..).find(|&n| pow16(n + 1) > pow10(36)).unwrap();
for s in (0..).take_while(|&s| pow16(n_max) >= pow10(n_max + s + 1)) {
let c = (0..=n_max).map(|i| pow16(i) - pow10(i + s)).collect::<Vec<_>>();
let rmax = c.iter().scan(0, |s, &c| { *s += if c > 0 { c * 9 } else { 0 }; Some(*s) }).collect::<Vec<_>>();
let rmin = c.iter().scan(0, |s, &c| { *s += if c < 0 { c * 9 } else { 0 }; Some(*s) }).collect::<Vec<_>>();
let (mut i, mut n, mut d, mut ct) = (0, 1, vec![0; c.len()], vec![0; c.len() + 1]);
loop {
d[i] += 1;
if d[i] < 10 {
let m = pow10(n as u32 + s); ct[i] = c[i] * d[i] + ct[i+1];
if i == 0 {
if ct[0] >= 0 && ct[0] % m < pow10(s) { answer.push(d.iter().take(n).rev().fold(0, |sum, &d| sum * 16 + d)) }
} else {
let (max, min) = (ct[i] + rmax[i-1], ct[i] + rmin[i-1]);
if max >= 0 && (max - min > m || pow10(s) > min % m || min % m > max % m) { i -= 1; }
}
} else { d[i] = -1; i += 1; if i == n { if n == d.len() { break; } n += 1; } }
}
}
answer.sort(); answer
}
700(4): デフォルトの名無しさん [] 2025/03/23(日) 23:00:51.13 ID:pi1bImlR(1) AAS
>>680から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.037s