疑問

RustでAtCoderに参加しているのですが、たまに数値が範囲外になってWAになる目に遭遇します。panicが発生していた場合はREになりそうなもので、不思議に思っていたのですが、最近原因に気が付きました。

結論

Rustのリリースビルドでは、(オプションにもよるようですが)overflowを検知しないから、というのが理由のようです。

気が付いたきっかけ

ABC164のD問題にて、人のACコードを参考にしていたところ、妙なコードを発見しました。
分かりやすいように改造していますが、こんな感じです。

fn main(){
    let mut a = vec![0;5];
    let x = 2usize;
    for p in [!1, !0, 0, 1, 2].iter(){
        let y = x + *p;
        a[y] += 1;
    }
}

まず!0という見慣れない表記に混乱しましたが、よく考えるとビット反転ですね。!0は全bitが1になるので、usize型の場合、std::usize::MAXと同じ値になります。(型がi32など符号付整数の場合は-1)
しかしここで疑問が。
「let x = x + *p;の部分でオーバーフローするのでは……？」
そう思ってローカルで試してみると、予想通り、thread 'main' panicked at 'attempt to add with overflow'が発生します。

しかしこれはACしているコードです。ローカルでの実行はデバッグビルドですが、提出されたコードはリリースビルドされますので、何か違うのかもしれません。というわけで、コードにprintln!をつけ、AtCoder上のコードテストに放り込んでみて気が付きました。

fn main(){
    let mut a = vec![0;5];
    let x = 2usize;
    for p in [!1, !0, 0, 1, 2].iter(){
        let y = x + *p;
        a[y] += 1;
        println!("x={}, y={}, p={}", x,y,*p);
    }
}

を実行すると、こうなります。

x=2, y=0, p=18446744073709551614
x=2, y=1, p=18446744073709551615
x=2, y=2, p=0
x=2, y=3, p=1
x=2, y=4, p=2

x、yの値を見るとわかるように、最初の2行では、pがp=-2,p=-1として扱われているように見えます。
これを見て漸く「リリースビルドではoverflowが無視される」ことに気が付いたのでした。
内部で何が起こっているかについては、付録に考察を書いています。

余談 (ABC176参戦記)

関係ないですが、ABC176のD問題で、2か所ほどはまって間に合いませんでした。

課題1

1つ目は関数じゃなくてクロージャを使ったところ、コンパイルが通らなかったこと。下記のような感じで、定義済みの型なのに型推論できないと怒られてしまいました。
結局クロージャのままでの解決方法は分からなかったため、main()の外に関数として書き出すことで回避。

fn main() {
    // 略
    let mut kabe: Vec<Vec<bool>> = vec![vec![false;H+4;W+4];
    // 略
    let walk = |x, y| {
        if !kabe[x][y] {
            // 略
        }
    };
    // 略
}

error[E0282]: type annotations needed                                                         
  --> src\bin\d.rs:53:9
   |
53 |     if !kabe[x][y] {
   |         ^^^^^^^ cannot infer type
   |
   = note: type must be known at this point

error: aborting due to previous error

~~クロージャには二重ベクタを持ち込めないんですかね？　解決したら、別途記事を書きます。~~

(追記)
コメント欄での指摘により解決しました。
kabe[x]に下線が引かれていますが、本当に型推論できていなかったのは添え字のxとyだったようです。
言われてみれば確かに、kabe[0..1]などと書けば、sliceになってしまいますね。0..1のような部分もRange<usize>型の変数で表せたとは……。
ただ、!演算子を付けているんだからkabe[x][y]はbool型でなければならないわけで、そこから型推論できそうな気も……？
(追記ここまで)

課題2

2つ目はBinaryHeapの仕様を勘違いしていたこと。最初の提出でTLEを食らった際、小さいほうからpop()すると思い込んでいたため、アリズム自体の工夫どころを探して時間切れ…。
時間切れ直前に気が付いてcost部分にReverseをつけたのですが、間に合いませんでした。あと6分…!

付録

おそらく内部的には下記のようなことが起こったと考えられます。
2+18446744073709551615を16進数で表記すると、下記のようになります。

                  2
+  FFFFFFFFFFFFFFFF
-------------------
  10000000000000001

ところが、確保されているのは64bit変数ですので、繰り上がりによって発生した最上位桁の1は、無視されます。

というわけで、overflowの検知を無視して加算を行うと、$mod (2^{64})$の世界での加算として、成立してしまうようです。¹

~~でも桁あふれを起こした1が、他のメモリ領域を破壊してしまう可能性もあるような…？~~ (追記)桁あふれを起こしてもメモリ破壊は起こさないようです。さすがRust。(追記ここまで) 初心者が手を出してよいテクニックじゃなさそう。 ↩