これもたぶんRust特有のはまり方
結論
Rustの減算には要注意。
問題
今回WAがとれずにハマった問題はこちら。
AGC047-A Integer Product
要約すると、長さ$N$の実数列$A$から2個を取り出す時、積が整数になる組み合わせの数を求める問題。
$A_i$の制約は $0<A_i<10^4$ であり、小数第9位まで与えられる。
提出
いつものようにRustで解いて下記のように提出したのだけれど、5つのケースでWAになった。
入力値の範囲などを何度チェックしなおしても原因がわからず、何時間も時間を浪費してしまった。
#![allow(non_snake_case, unused_mut, unused_assignments)]
use proconio::input;
use std::cmp::*;
fn main() {
input! {
N:usize, A:[String;N]
}
let N: usize = N;
let A: Vec<String> = A;
let mut cnt = vec![vec![0; 50]; 50];
let mut p2 = vec![0; N];
let mut p5 = vec![0; N];
for i in 0..N {
let s = A[i].clone();
let mut ip = 0usize;
let mut dp = 0usize;
if let Some(i) = s.find('.') {
// 入力値が小数の場合
ip = s[0..i].parse().unwrap();
let ss = s[(i + 1)..].to_string() + "0000000000";
dp = ss[0..9].parse::<usize>().unwrap()
} else {
// 入力値が整数の場合
ip = s.parse::<usize>().unwrap();
}
let mut x = ip * 1_000_000_000 + dp;
while x % 2 == 0 {
x /= 2;
p2[i] += 1;
}
while x % 5 == 0 {
x /= 5;
p5[i] += 1;
}
cnt[p2[i]][p5[i]] += 1;
}
let mut ans = 0usize;
for i in 0..N {
let remain2 = max(18 - p2[i], 0);
let remain5 = max(18 - p5[i], 0);
for j in remain2..50 {
for k in remain5..50 {
ans += cnt[j][k];
}
}
if p2[i] >= remain2 && p5[i] >= remain5 {
ans -= 1;
}
}
println!("{}", ans / 2);
}
原因
結論から言うと、今回の原因は計算途中で値が負になってしまったこと。
cntのindexとして使用するため、p2[i],p5[i]の型はusizeにしている。それを踏まえて下記の行を見てみる。
let remain2 = max(18 - p2[i], 0);
let remain5 = max(18 - p5[i], 0);
remain2とremain5が$0$以上になるよう、std::cmp::maxを使っている。……のだけれども、p2[i]がusizeであることから18 - p2[i] もusizeと型推論されるため、18 - p2[i]が$0$未満になった時点でpanicが発生する。つまりmax自体が無意味だったというオチ。
例えば入力値として1 0.000524288($2^{19} / 10^9$)を与えるとp2[0]が$19$になるため、下記のようにattempt to subtract with overflowが発生する。
runtime error: exit code: 101
stderr:
1 | thread 'main' panicked at 'attempt to subtract with overflow', src\bin\a.rs:41:23
2 | note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
このコードを活かすなら、下記のように、いったん符号付整数型に変換する必要がある。1
let remain2 = max(18 - p2[i] as i64, 0) as usize;
let remain5 = max(18 - p5[i] as i64, 0) as usize;
おまけ
std::cmp::maxではなく、if文で同じことをすると、無意味な比較だと教えてくれる。
let remain2 = if 18 - p2[i] >= 0 { 18 - p2[i] } else { 0 };
のように書くと、下記のようになる。
warning: comparison is useless due to type limits
--> src\bin\a.rs:41:22
|
41 | let remain2 = if 18 - p2[i] >= 0 { 18 - p2[i] } else { 0 };
| ^^^^^^^^^^^^^^^
|
= note: `#[warn(unused_comparisons)]` on by default
愚痴
というかこれ、WAじゃなくてREちゃうんか？
いろんな実行時エラーを試して、WAとREのどちらにジャッジされるか、見分けるケース一覧作ったら便利そう。