ABC033 - C: 数式の書き換え（オーバーフローに関する追記あり）

問題
解答
コード
おわりに
追記：オーバーフローに関して

WAを取るのに苦労したので投稿．

※ オーバーフローに関して追記しました．

問題

ABC033 - C: 数式の書き換え

f:id:pytwbf201830:20190210105507p:plain

解答

公式解説

AtCoder Beginner Contest 033 解説 from AtCoder Inc.

www.slideshare.net

　*でつながれた数を一つの塊とみなし，+で各塊が分離される．そして，0 でない各塊の数を出力するという方針で考えた．公式解説とも一致．

提出してみると一つだけ WA だった．小さい方のコーナーケースから考えてみた．

文字数が 1 のときは数字が 0 なら 0, それ以外なら 1

と言うケースはすでに取り除いていた．続いて 3 文字の時を入力してみても特に問題はなかった（そもそも今回の場合，3文字はコーナーケースではない）．コードを見ていても気になるコーナケースは見つからなかった．

　探している途中に気になった点が一つ．*の塊の数字が全て 9 でその積がオーバーフローを起こしていたらどうなるんだろうかと思いついた（追記：結局オーバーフローという観点は間違っていなかったがその原理は違っていた）．一か八かでオーバーフローを起こさないようにしてみたら AC（下記コードの 40 行目に num という変数を導入し，各塊の要素の積を求めることなく 0 or それ以外で区別した．）．

積の計算のオーバーフローで 0 になるのはありえるのだろうか（追記を参照：積によるオーバーフローで計算結果は 0 になりうる）．今回に関しては各塊が 0 出なければ，カウント対象としていたので，各塊の積が 0 にならなければカウントし間違えると言うことは起きないはずである（オーバーフローで -999999 とかになっても問題ないのではという認識）．もやもやする点が残ったままの AC だった.（追記を参照）

コード

AC できたコードを載せておく．

ABC033 - C: 数式の書き換え

おわりに

WA になってしまう前には，オーバーフローが起きる可能性がある部分はあらかじめ除去しておくべきという知見を得た．原因はわからんけどもオーバーフローには気をつけましょうと言う話．オーバーフローに関する記事を過去に書いているので参考までに．

追記：競プロの問題を解く上での方針？考え方？的な話．オーバーフローが起こるような競プロの問題では，オーバーフローや（signed long long などの）未定義動作を避けられるような正解があると解釈すれば良い．解決できるに問題が作られているとも言える．オーバーフローにならないように工夫するのは競プロにおいては大事．

pyteyon.hatenablog.com

追記：オーバーフローに関して

Twitter にて，「なんでオーバーフローを解決すると AC になるんや」と質問を投げかけていたら，親切な方に拾っていただけたのでこの場で知識を共有します．ホスフィン（@mine691）さん，koba（@kobae964）さん，ありがとうございます．

ありがたいリプの数々：冪乗の計算結果が 0 になる？？

TwitterのFFの方々のリプのおかげで，WA になった原因がオーバーフローであると断定できました．以下のようなリプをいただきました．

kobaさんのリプライ

多分2を32個か64個以上掛けたのではないでしょうか？整数演算は常に2^32や2^64で余りをとって行われるので、それの倍数は0になります
— koba(競プロを熱心にしたいです) (@kobae964) 2019年2月10日

「C++ int オーバーフロー」とかで調べると色々出てくると思います。注意すべきなのは、signed long longのオーバーフローの挙動が実は未定義なので、何が起こっても文句は言えないということです。なのでこれについての解説も回りくどい書き方になっていると思います
— koba(競プロを熱心にしたいです) (@kobae964) 2019年2月10日

ホスフィンさんのリプライ

私：WA（オーバーフロー？）の謎が解けないが，それを記憶の片隅に置いておく．この記事を見て WA の原因がわかりそうであればご教授願います．
ホ：2 が 35 個掛けられたらオーバーフローしませんか？
私： $2^{35}$ でオーバーフローしても 0 にならなければその塊を 0 にする必要があると考えました（-99999999... とかなっても）.どうなんでしょうか?（この質問の仕方最悪ですね...）
私：（連投）ホスフィンさんの仰ていることの知識が私にありませんでした... 2 の累乗でオーバーフロー起こすと 0 になることあるんですね
ホ：多分なんですけど、2 の冪乗以外でもオーバーフローで0になることがあると思います。(未定義動作なので、どうなるのか予想が付きません)
私：なるほどです，自分が思っていたより大事なことっぽいですね... 未定義動作に関して，オーバーフローが起こるような競プロの問題では，未定義動作を避けられるような正解があると解釈するのが良いのでしょうか？
ホ：はい、その解釈でいいと思います。(オーバーフローしないように工夫するのも競プロにおいては大事なので)

最後のオーバーフローしないように工夫して問題を解くというのは心に留めておきたいところ...

初めはなんのこっちゃよく分からなかったのですが，丁寧なリプによってだんだん分かるようになっていきました．

今回解いた問題のWA に対する「積でオーバーフローが起こるときに（0 が因子になくとも） 0 になりうるのか」という私の問いへの答えは「なりうる」でした．厳密に言うと，

2 の（倍数の）冪乗，または他の数の冪乗でオーバーフローが起こり，（0 が因子になくとも）演算の結果が 0 になりうる

ということだと分かりました．すぐさま手元で動かしてみたところ， 2 の冪乗によるオーバーフローで演算の結果が 0 になることが確認できました．

#include <iostream>
using namespace std;

int main() {
    ll num = 2;
    cout << num << "\n";
    for (ll i = 0; i < 64; ++i) {
        num *= 2;
        cout << num << "\n";
    }
    return 0;
}

出力

2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536

# 中略

576460752303423488
1152921504606846976
2305843009213693952
4611686018427387904
-9223372036854775808
0
0

他にも 4, 8, 16 ... などの 2 の冪乗（2 のときよりも早い段階で 0 になる）でオーバーフローした途端に 0 になりました．6, 10 でもこの現象が確認できました．3, 5, 7 の冪乗では 0 にはなりませんでした．このように，2 の冪乗（2 の倍数）を使った演算によるオーバーフローで，演算結果が 0 になるようです．

0 になってしまう理由は， koba さんのリプの，「整数演算は常に $2^{32}$ や $2^{64}$ で余りをとって行われるので、それの倍数は 0 になります」という部分です．これについて以下で説明を加えてみたいと思います．

2 の冪乗に関する整数演算でのオーバーフロー：演算結果が 0 になるのはなぜか

以下の記事が探していた内容とドンピシャでした．

www7b.biglobe.ne.jp

この記事によると，

int 型で計算すると，計算結果が 32 ビットで表現できないときは，下位 32 ビットのみを残して上位ビットは切り捨ててしまう（long long 型だと 64ビット）．この切り捨てられてる部分が出る現象のことをオーバーフロー（桁あふれ）という．これは $2^{32}$ の余りを求めることと同じになります．いちいち割り算をしなくても常に勝手に $2^{32}$ で割った余りを求めてくれているというわけです．

これで私が WA になった原因が完全にはっきりしました．上記の記述は，どのような演算でも，例えば単純な二つの数の和でも，

$(a+b)$ mod $2^{32}$ or ( $2^{64}$ )

のように，mod が暗黙のうちに計算されているのです．これを踏まえた上で，先程の例同様，unsigned int 型（符号付だと説明がめんどいので）の変数で $2^{32}$ を行い，オーバーフローを起こしてみます．

#include <iostream>
using namespace std;

int main() {
    int num = 2, count = 1;
    cout << "2^" << count << ": " << num << "\n";

    for (int i = 0; i < 31; ++i) {
        num *= 2;
        count++;
        cout << "2^" << count << ": " << num << "\n";
    }
    return 0;
}

出力

2^1: 2
2^2: 4
2^3: 8
2^4: 16
2^5: 32
2^6: 64
2^7: 128
2^8: 256
2^9: 512
2^10: 1024
2^11: 2048
2^12: 4096
2^13: 8192
2^14: 16384
2^15: 32768
2^16: 65536
2^17: 131072
2^18: 262144
2^19: 524288
2^20: 1048576
2^21: 2097152
2^22: 4194304
2^23: 8388608
2^24: 16777216
2^25: 33554432
2^26: 67108864
2^27: 134217728
2^28: 268435456
2^29: 536870912
2^30: 1073741824
2^31: 2147483648
2^32: 0
# 2^33: 0
# ...

$2^{32}$ が 0 になっているところが大事なところです．unsigned int 型は $0 ~ 4294967295(2^{32} - 1)$ を表すことができるので， $2^{32}$ （4294967296）という数字はオーバーフローしてしまうのは自明のことだと思います．しかしなぜ 0 になるのでしょうか．

先ほどの「常に mod が計算されている」という記述から， int 型だと常に mod $2^{32}$ が計算されていることがわかります．なので，それを表してみると，

2^1 mod 2^32: 2
2^2 mod 2^32: 4
2^3 mod 2^32: 8
2^4 mod 2^32: 16
2^5 mod 2^32: 32
2^6 mod 2^32: 64
2^7 mod 2^32: 128
2^8 mod 2^32: 256
2^9 mod 2^32: 512
2^10 mod 2^32: 1024
2^11 mod 2^32: 2048
2^12 mod 2^32: 4096
2^13 mod 2^32: 8192
2^14 mod 2^32: 16384
2^15 mod 2^32: 32768
2^16 mod 2^32: 65536
2^17 mod 2^32: 131072
2^18 mod 2^32: 262144
2^19 mod 2^32: 524288
2^20 mod 2^32: 1048576
2^21 mod 2^32: 2097152
2^22 mod 2^32: 4194304
2^23 mod 2^32: 8388608
2^24 mod 2^32: 16777216
2^25 mod 2^32: 33554432
2^26 mod 2^32: 67108864
2^27 mod 2^32: 134217728
2^28 mod 2^32: 268435456
2^29 mod 2^32: 536870912
2^30 mod 2^32: 1073741824
2^31 mod 2^32: 2147483648
2^32 mod 2^32: 0

という計算が内部で行われていることになります．こう見てみると $2^{32}$ が 0 であることも納得がいきますね．それ以降の演算は続けても当然 0 になってしまいます（0 に何を掛けても 0）．

本記事で解いた ABC の問題では，最大で $2^{50000}$ 程度の計算になる場合（全ての数字が 2 で，記号が *）があるため，0 ではない塊も上記のオーバーフローによって 0 になってしまい，WA になってしまったのだと思います．「 $2^{64}$ × hoge」となるような数は，わざわざ問題で与えられたどうりに積を計算してしまうと 0 になってしまいます．やっとスッキリしました．WA の原因は，

暗黙に行われている mod 演算により現れる 0 のせい

でした．

念の為確認しておきますと，この $2^{32}$ という数字の 32 は unsigned int 型（もしくは int 型）が 32 ビット分のメモリを確保しているところから来ています．そのため，long long 型では，32 が 64 に置きかわります．基礎的な部分はこちらの記事をお読みください．（オーバーフローの解説記事を書いていた本人が今回のWAの仕組みが分かっていないなんて，とは言わないでください．）

pyteyon.hatenablog.com

また上のリプライにて挙がっていた「未定義動作」に関しては，少し難しそうでまだ十分に理解できていません．以下の記事が参考になりそうです．

qiita.com

追記まとめ

以上，オーバーフローに関する（自分の中では）新たな知見が得られました．オーバーフローは，「扱える範囲を超えたら桁が溢れて一番小さい数に戻ってしまう」というイメージしかなく，暗黙に行われている mod 演算の存在を知る由もありませんでした（この演算により溢れてしまった桁によるメモリリークを防げてるのか？）．ホスフィンさん，kobaさん，本当にありがとうございました．一人で悩んでいたら一生分からなかりませんでした．いつも私のツイートに反応してさまざまなことをご教授してくださる皆様にこの場を借りてお礼を申し上げます．

pyてよn日記

一寸先は闇が人生