Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

AGC002-A 「Range Product」 (200)

いかに効率良く、漏れなく分岐を書けるか。

問題リンク

概要

 a \times (a + 1) \times \dots \times (b - 1) \times bが正か負か0か判定せよ。

制約

  •  -10^9 \leq a \leq b \leq 10^9

解説

制約からして、実際に積を計算するのはオーバーフローするし計算量多すぎるしでアウト。

知りたいのは符号だけなので、どういったケースに積が各符号になるかを考えてみる。

  •  0 \Leftrightarrow [a, b]に0が含まれる
  •  - \Leftrightarrow 上を満たさず、かつ [a, b]に負数が奇数個含まれる
  •  + \Leftrightarrow 上2つをどちらも満たさない

まず「 [a, b]に0が含まれる」は「 a \leq 0かつ 0 \leq b」と言い換えられる。数直線上で0を覆うような区間を考えれば分かる。

次に負の判定だが、まず上を満たさない時点で 0 \lt a \leq b a \leq b \lt 0のどちらかが確定している。前者はそもそも負数を含まないので、負数のみを含む後者に的を絞る。

後者は負数しか含まず、かつその要素数 b - a + 1で求まる。つまりこれが奇数なら負であることが分かる。

最後に正の判定だが、これは上2つを満たさないものは全て該当するので特別な処理は不要。

実装例

以下では「 b - a + 1が奇数」を「 b - aが偶数」に言い換えている。

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;

    if (a <= 0 && 0 <= b) {
        cout << "Zero" << endl;
    } else if (b < 0 && (b - a) % 2 == 0) {
        cout << "Negative" << endl;
    } else {
        cout << "Positive" << endl;
    }
    return 0;
}

多分これが一番場合分けが少ないと思います。

感想

  • 下手にスマートにやろうとすると条件漏れが出たり、その辺の意識が難しい。
  • 慣れないうちは多少冗長でも確実なコードを書こう。