プログラミングのお題スレ Part22 (863ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
697(6): デフォルトの名無しさん [sage] 03/21(金)12:56 ID:CgJbZEAu(1/2)
>>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
}
698(4): デフォルトの名無しさん [sage] 03/21(金)12:58 ID:CgJbZEAu(2/2)
>>697
// 略記
fn pow16(x: u32) -> i128 { 16_i128.pow(x) }
fn pow10(x: u32) -> i128 { 10_i128.pow(x) }
// 結果検証
fn main() {
let answer = odai_680();
assert_eq!(167, answer.len());
for &a in &answer {
assert!(a.to_string().contains(&format!("{a:x}")));
}
assert_eq!(0, answer[0]);
assert_eq!(1, answer[1]);
assert_eq!(357440, answer[10]);
assert_eq!(2182104649, answer[54]);
assert_eq!(3927570397557, answer[71]);
assert_eq!(38135630558262267902210, answer[99]);
assert_eq!(331052794565713975838768757043267, answer[152]);
assert_eq!(697786638998562641695629924526065234, answer[answer.len() - 1]);
}
699(2): デフォルトの名無しさん [] 03/21(金)20:49 ID:uwhksDTb(1)
>>697-698
Rustはよく知らないが、mainのforループ内をprintln!("{}", a);に置き換えれば解が表示されるんだよね?
実行結果を>>685で述べたC++プログラムのものと照合したら167個の解すべてが一致した。見事正解!
実行時間はC++プログラムの数倍かかるようだが、ideoneでの実行時間も見たいので載せて下さい。
703: デフォルトの名無しさん [sage] 03/25(火)15:54 ID:GZ5kfx5g(1)
>>702
データ精度を揃えたアルゴリズム比較のために
>>697-698をi128固定ではなくnum::BigIntにして計測して見ては？
あと出題者>>685は>>700の二つ目で(倍速以上に)短縮出来たと言っているよ
705(1): デフォルトの名無しさん [] 03/25(火)17:30 ID:Yc/egiP0(3/3)
>>697-698をBigIntに変えるのはどうしたらいいのか分かんなかったので
>>700の方を boost::multiprecision::cpp_int から boost::multiprecision::int128_t に変えてみた
改変版 | オリジナル
https://ideone.com/Ie0HhO 0.12s | https://ideone.com/KID2jR 0.43s
https://ideone.com/np3p5h 0.11s | https://ideone.com/ysdd6b 0.23s
706: デフォルトの名無しさん [sage] 03/25(火)20:18 ID:oTGl9wWX(1)
>>705
感心した、出題者回答C++コードはほんの少し変更するだけで簡単にBigInt/i128切り替え出来るのか
>>697-698
Rustはどうなのかな？
708: デフォルトの名無しさん [sage] 03/27(木)11:39 ID:vU3T1Sq/(1)
>>697
crateのnumを使う
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.026s