プログラミングのお題スレ Part22 (854ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
682(1): 9 [sage] 2025/03/18(火) 16:05:22.66 ID:GYPHuJM6(1/5) 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桁以下で解いても構いません
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";
683(2): 9 [sage] 2025/03/18(火) 16:07:07.28 ID:GYPHuJM6(2/5) AAS
>>682
実行結果 (改行数を減らすため適度につなげてます)
$ perl 22_680_hex_substr_1.pl
38d7ea4c67fff 999999999999999
1 .. 0x3897994967999
Tue Mar 18 09:15:31 2025
1, 0x1 2, 0x2 3, 0x3 4, 0x4 5, 0x5 6, 0x6 7, 0x7 8, 0x8 9, 0x9
357440, 0x57440 357441, 0x57441 357442, 0x57442 357443, 0x57443 357444, 0x57444
357445, 0x57445 357446, 0x57446 357447, 0x57447 357448, 0x57448 357449, 0x57449
1079653, 0x107965 1081713, 0x108171 1122966, 0x112296 1123079, 0x112307 1123080, 0x112308
2246166, 0x224616 3369253, 0x336925 3371313, 0x337131 3412566, 0x341256
4494393, 0x449439 4494400, 0x449440 4535653, 0x453565
5658739, 0x565873 5658740, 0x565874 5660793, 0x566079 5660800, 0x566080 5702166, 0x570216
6783879, 0x678387 6783880, 0x678388 6784000, 0x678400
6825253, 0x682525 7948339, 0x794833 7948340, 0x794834 7950393, 0x795039 7950400, 0x795040
2182104640, 0x82104640 2182104641, 0x82104641 2182104642, 0x82104642 2182104643, 0x82104643 2182104644, 0x82104644
2182104645, 0x82104645 2182104646, 0x82104646 2182104647, 0x82104647 2182104648, 0x82104648 2182104649, 0x82104649
1263629042727, 0x12636290427 1307655353654, 0x13076553536 2573583194436, 0x25735831944 2617616245848, 0x26176162458
3330782168640, 0x30782168640 3330782168641, 0x30782168641 3330782168642, 0x30782168642 3330782168643, 0x30782168643
3330782168644, 0x30782168644 3330782168645, 0x30782168645 3330782168646, 0x30782168646 3330782168647, 0x30782168647
3330782168648, 0x30782168648 3330782168649, 0x30782168649 3883544086630, 0x38835440866 3927569962533, 0x39275699625
3927570397557, 0x39275703975
Core i7-8559U で6時間ほど実行してここまで高々13桁。
やはり想定通り気の利いた高速解放が要りますﾃﾍﾍﾟﾛ。
686(2): 9 [sage] 2025/03/18(火) 21:41:48.53 ID:GYPHuJM6(3/5) AAS
>>683
>やはり想定通り気の利いた高速解放が要りますﾃﾍﾍﾟﾛ。
そのﾋﾝﾄになるかいな…？
・16進数を10進数に変換すると桁数は同じまたは高々1桁増えるのみ（だともう、証明略）
・桁数が同じ場合、16進数と10進数が同じということはあり得ない、自明
・一桁増える場合は先頭または末尾に一桁増える。残りが16進数と同じ部分文字列であるかが評価対象となる
687: 9 [sage] 2025/03/18(火) 21:42:49.00 ID:GYPHuJM6(4/5) AAS
>>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秒に短縮できた。
あそうなんだ。じゃオレ様が一番乗りということでヨロ
ﾉｼ
688: 9 [sage] 2025/03/18(火) 21:52:10.05 ID:GYPHuJM6(5/5) AAS
>>686
>・一桁増える場合は先頭または末尾に一桁増える。残りが16進数と同じ部分文字列であるかが評価対象となる
二桁増える場合があるのでこれは誤りでした
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.031s