off-by-one エラーとか呼ばれるやつです。「1 ズレてたせいでこわれた」というやつですね。
バグらせやすい書き方をするのがよくないです。書き方を改めるのがよいでしょう。
ここでは、えびちゃんがよくやっている書き方を紹介しますが、別にこれが絶対というわけではないです。 「私の今の書き方が私にとっては世界一書きやすい。私はもう真理に達した」という人はすきにしてください。
バグらせにくい書き方をまだわかっていないとか、コンテスト中にそこでバグらせて不本意な結果になったとか、そういう人は考え直すのをおすすめします。
(追記:2021/01/05)あと、何も考えずに AC するまで [i]
[i+1]
[i-1]
などを適当に書き換えるような癖はつけない方がいいと思います。
累積和
配列 \(A = [a_0, a_1, \dots, a_{n-1}]\) に対して \(\sum_i a_i\) たちを並べた配列 \(S\) ですね。
よくないと思う実装
\(S = [s_0, s_1, \dots, s_{n-1}] = [a_0, (a_0+a_1), \dots, (a_0+a_1+\dots+a_{n-1})]\) とするのはおすすめしません。
以下に理由を示します。 よく使う例として、\(a_l+\dots+a_{r-1}\) を求めたい局面を考えてみましょう。 これは \(S_{r -1} - S_{l -1}\) でいいですか? いいえ、\(l = 0\) のときにこわれてしまいますね。 \(S_{-1}\) は定義されていないからです。
和を求めようとするたびに、一々場合分けをするのは面倒ですね。 面倒なことは忘れがちで、バグの原因になりがちです。
いいと思う実装
\(S = [s_0, s_1, \dots, s_n] = [0, a_0, (a_0+a_1), \dots, (a_0+a_1+\dots+a_{n-1})]\) とするのがおすすめです。 上の例では、\(S_r -S_l\) とするだけでよいです。
これを「累積和のときだけは 1-indexed にして、\(s_1 = a_1, s_2 = (a_1+a_2), \dots\) だ」と捉える人がいますが、そう解釈するのは余計に混乱します。
むしろ、0-indexed の \(a\) において、半開区間 \([0, i)\) の和が \(s_i\) と考える方がよいです。 \(s_0\) は \([0, 0) = \emptyset\) の和で \(0\)、\(s_n\) は \([0, n)\) の和、つまり全体の総和です。
先頭に \(0\) を挿入してから累積させるように書いています*1。
std::vector<int64_t> a(n); for (auto& ai: a) std::cin >> ai; a.insert(a.begin(), 0); for (size_t i = 1; i <= n; ++i) a[i] += a[i-1];
両側からの累積和
これも半開区間で考えます。 後ろからの累積和を \(T = [t_0, \dots, t_{n-1}, t_n] = [(a_0+\dots+a_{n-1}), \dots, a_{n-1}, 0]\) とします。 つまり、\(t_i\) は半開区間 \([i, n)\) における和です。
よくある使い方として「\(a_i\) だけを \(x\) にしたときの和」がありますね*2。 半開区間 \([0, i)\) の和と \([i+1, n)\) の和がほしいわけですから、\(s_i + x + t_{i+1}\) を求めればよいです*3。
配列の両端の \(0\) と \(n\) は固定されているので添字には持ってこず、動ける端(上の例での \(i\))を添字に持ってきているわけです。
二分探索
よくない気がする実装
下の方にあるめぐるちゃんのツイートを見てください。 どうしても閉区間で管理せざるを得ない状況などでは、これを強制される場合があるかもしれません。
64-bit 整数すべての値が探索範囲の場合とか? いや、最大値だけ別で判定してから、必要に応じて半開区間で処理するべきでしょうね。
よい気がする実装
次のようなテンプレを使っています。
int64_t ok = OK_INIT, bad = BAD_INIT; // ok < bad を考える while (bad-ok > 1) { auto mid = (ok+bad) / 2; // f(mid) は、mid で大丈夫のときに true を返すとする (f(mid)? ok: bad) = mid; }
ループの後、ok
には f(x)
が true
であるような x
の最大値が入っています。
bad == ok+1
です。
さて、これは考えれば当然なのですが、f(BAD_INIT)
は false
である必要があります*4。
f(BAD_INIT)
が true
なら、得られた値 ok
(== bad-1
)が最大値ではなくなってしまうためです。
また、ループ継続条件を考えると、bad == OK_INIT+1
の場合や ok == BAD_INIT-1
の場合はループが回りませんから、mid
の引数の範囲は OK_INIT+1
以上 BAD_INIT-1
以下とわかります。
f
の引数の範囲としては、ここだけを想定すればよいということです(逆に言えば、この範囲外だと判定が行われてくれないということです)。
特に、0
でも ok か bad か判定したいのに下限が -1
ではなく 0
になっていると、失敗しそうです。
探索範囲を雑にやるとこわれる話
判定関数の中で乗算をする場合や除算をする場合は、雑にやるとこわれる場合があります。 前者はオーバーフロー、後者はゼロ除算が発生しうるためです。
他にも、配列外参照などが発生する場合も考えられますね。
こういうところは無思考で押し進めようとするとこわしやすいので、ちゃんと気にするようにしましょう。 多くの場合はすぐ済みますし、済まなかった場合は考えるに値するはずなので。
「常に下限は -1e18 で上限は 1e18 にしておけば絶対問題ない」のような思考停止の仕方はよくないと思っています。
(追記:2021/01/05)
めぐる式
- 半開区間であること
- 探索区間を
hi
やlo
ではなくok
やbad
のように判定結果で命名すること bad-ok > 1
ではなくabs(bad-ok) > 1
と判定すること- 大小関係がどうであれ書き換えなくてよい
半開だけを以って「めぐる式」と言っている人をよく見かけますが、めぐるちゃんに怒られないか心配です。
【めぐるのアルゴリズム講座】
— 因幡めぐる@競技プログラミング (@meguru_comp) 2016年2月9日
二分探索(整数)の書き方
難しさ:4 pic.twitter.com/LGLbkS0D7l
実数の場合
(追記:2021/01/05)
これは添字とかは関係ないのですが、関連する話題な気がするので。
ここに 書いてます。
尺取り法
落ちついて書けば、特にバグらせる要素はなさそうに思いますが、なぜかバグらせる人は多いですね。
条件を満たす最長の区間を求めていきたいです。
右に伸ばしていく方が自然*5に思えるので、そうします。
左端を固定したとき、ある条件 f(nya)
が true
になる区間の右端はどこまで伸ばせるかを知りたいです。
neko nya; // [il, ir) における値を管理する。 for (size_t il = 0, ir = 0; il < n; ++il) { if (il > ir) ir = il; while (ir < n && f(nya + a[ir])) { nya += a[ir++]; // 右に一つ追加する } ... // [il, ir) は valid な区間なので、所望のことをする if (il < ir) nya -= a[il]; // 空区間でなければ左側を一つ捨てる }
逆元を仮定したような書き方をしましたが、捨てられる要素は追加した要素だけなので、SWAG を使う場合でも同じ書き方でできます。
要するに、「il > ir
だけど [il, ir)
の区間の値として辻褄が合う値」のようなものを仮定しなくてよいということです。
ポイントは、左端を固定したいので、for
の各ループで il
が固定されるようにして考えるということです。
while
を使って一度に二つの変数を気にしようとするより、for
の方が「固定されている感」を感じやすいです(主観かもしれません)。
逆に、ある条件を満たす最短の区間を知りたいときはどうしましょうか。 条件を満たさない最長の区間がわかれば(適当な足し引きによって)求められますから、判定の真偽を反転させて、上のテンプレを使うのがよいでしょう(たぶん)。
リンク先の記事で最初に出てくるのが「辻褄が合う値」を仮定するやつで、最後の方に出てくるのが仮定しないやつです。
DP の添字
これも累積和のときと似ています。というか累積和は実質 DP みたいなところがあるので。
\(\mathrm{dp}[i]\) を「\(a_i\) を \(i\) 番目まで見たときのなにか」と思うと、\(a_i\) の indexing によって意味不明になったり、処理前(初期状態)をどこに入れるべきかわからなくなるので、避ける方がよさそうです。
\(a_i\) の添字として考えるのではなく、「前から \(i\) 個処理した」とするとよいです。 初期状態 \(\mathrm{dp}[0]\) は \(0\) 個処理された状態で、最終状態 \(\mathrm{dp}[n]\) は \(n\) 個処理された状態です。
\(i\) 個処理した状態である \(\mathrm{dp}[i]\) と、0-indexed で \(i\) 番目の \(a_i\) から、\(i+1\) 個処理した状態である \(\mathrm{dp}[i+1]\) を計算できます。 そもそも、0-indexed での \(i\) 番目というのは、自分より前に \(i\) 個の要素があることと同じですね。
混乱しそうになったら、\(i\) が \(0\) や \(1\) の場合などを考えるとすぐわかります。
使わない値について
使わない値を保持しておくのがバグ(を発見しにくくする原因)につながることもありますが、適切に使うとむしろ実装が簡単になります。 どういうときはどうするのがいいか、暇なときに一度考えてみてもよいでしょう。
たとえば、セグ木において [0]
の要素は使わない方が演算数が減って簡単に書けますね。
他にも、Eratosthenes の篩を書くときに [0]
や [1]
を参照することはほぼないですが、ここを詰めて \(i\) が素数かどうかを表す値を [i-2]
に入れようとすると、見通しが悪くなって添字のバグにつながりそうです。
より一般的な方針の話
これは特定のトピックではなく、低難易度帯のよくある実装モノです。
「ループを回したあと、答えの変数に一回ぶん余分に足されているはずなので、一回ぶん戻すことで辻褄を合わせる」みたいな実装方針は避けた方が無難だと思います。 条件の考慮漏れなどで余分に足されていなかったり、デバッグの際に気にする箇所が増えたりするためです。
ループ中で条件をちゃんと気にしながら作る方が見通しがよさそうです(うまくいっていない状態のものより、うまくいっている状態のものの方が想像しやすいため)。
(この話題についてなんですが、具体例が思い出せなかったので、思い出したら追記します。)
尺取り法でバグらせる人はそういう実装をしているかも? どうでしょう。 右端を伸ばしていって、一度条件を満たさなくしてから一つ戻すみたいなことを書く人はいる気がします。
より厳密に従うなら、上で紹介した例も il <= ir
を常に満たすべきでしょうが、必要以上に冗長になりそうだったので避けました。
おわり
にゃんこ。 バグらせてつらそうにやつあたりしている人を見るとつらくなるので、そういう人が減ったらいいにゃぁ*6。
自分に合った方法をきちんと考えておくことで、本番に {焦って, 無思考で, 考慮漏れで} バグらせることが減るんじゃないかなぁと期待しています。
*1:ところで、この例では可換を仮定して書いているので、そうできない場合は適宜書き換えましょう。
*2:ここでは和と言っていますが、最小値とか GCD とかのように、モノイドの演算を指します。逆元が仮定できないということですね。積と呼ぶこともあるっぽいです。
*3:この式が、\(0\le i\lt n\) のどれにおいても有効であることを確かめてください。
*4:実際には呼び出す必要はないです。(考察の上で)false が返ってきてほしい値であればよいです。呼び出すと未定義動作になるとかを気にせずに設計してよいということです。
*5:これは我々の文字体系が左から右なのと関係していますか? 気になります。
*6:添字でバグらせる奴は競プロをやめてしまえ、という意味ではありません。