AtCoder Grand Contest 036 A

A - Triangle

問題

正整数 $S$ に対し、以下を満たす整数 $X_i, Y_i \, (i = 1, 2, 3)$ を 1 つ求めよ。

$0 \leq X_i, Y_i \leq 10^9$
3 点 $(X_i, Y_i)$ がなす三角形の面積は $S / 2$

制約

$1 \leq S \leq 10^{18}$

考察

自由変数が多い構築問題では、どれだけ都合の良いように自由変数を固定できるかが肝となる。

まず $X_1 = Y_1 = 0$ と固定する。すると、三角形の面積は外積で与えられるので $|X_2 Y_3 - X_3 Y_2| = S$ が必要十分条件となる¹。この絶対値は外しても問題ない。

ここで $X_3 = 0$ と簡略化してしまうと、 $S = X_2 Y_3$ となり、 $S$ が大きい素数の場合に構築不能になってしまう。そこで $X_3 = 1$ と固定し、 $X_2 Y_3 = S + Y_2$ を満たす $X_2, Y_2, X_3$ を探すことにする。

$S$ が最大のケースを考えると、 $X_2 = Y_3 = 10^9$ 以外に解は存在しない。このケースに対処するためには、 $S + Y_2$ を近くの平方数に近づけたら上手く行きそうである。すなわち、 $Z$ を $Z^2 \lt S$ を満たす最大の整数としたとき、

$$ X_2 = Y_3 = Z + 1, Y_2 = (Z + 1)^2 - S $$

とすれば良さそうである。しかし $S = Z^2 + 1$ のケースで $Y_2=2Z$ となり、制約を超えてしまう。

そこで $Z (Z + 1)$ を間に挟んで、 $S$ がこれ以下である場合には

$$ X_2 = Z, Y_3 = Z + 1, Y_2 = Z(Z + 1) - S $$

としてみる。これで $Y_2$ は高々 $Z$ となり²、制約を満たすことができる。

実装例

提出時には不要だが、以下のように assert をかけておくと予期しないバグに気づけて便利。

提出 #6512335 - AtCoder Grand Contest 036

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


using namespace std;
using lint = long long;

// Z * Z < Sを満たす最小のZを求める
lint sqrti(lint S) {
    lint ok = 0, ng = 1e9 + 1;
    while (ng - ok > 1) {
        lint mid = (ok + ng) / 2;
        (mid * mid < S ? ok : ng) = mid;
    }
    return ok;
}

int main() {
    lint S;
    cin >> S;
    lint Z = sqrti(S);

    vector<lint> X(3), Y(3);
    X[0] = Y[0] = 0, X[2] = 1;

    if (S <= Z * (Z + 1)) {
        Y[1] = Z * (Z + 1) - S;
        X[1] = Z, Y[2] = Z + 1;
    } else {
        Y[1] = (Z + 1) * (Z + 1) - S;
        X[1] = Y[2] = Z + 1;
    }

    assert(X[1] * Y[2] - X[2] * Y[1] == S);
    for (int i = 0; i < 3; ++i) {
        assert(X[i] <= 1e9);
        assert(Y[i] <= 1e9);
        cout << X[i] << " " << Y[i] << " ";
    }
    cout << endl;
    return 0;
}

作る三角形の面積が $S$ ではなく $S/2$ であることに注意。 ↩︎
$S \leq Z (Z + 1)$ の場合、 $Y_2 = Z(Z + 1) - S \lt Z (Z + 1) - Z^2 = Z$ 。
$S \gt Z (Z + 1)$ の場合、 $Y_2 = (Z + 1)^2 - S \lt (Z + 1)^2 - Z(Z + 1) = Z + 1$ 。 ↩︎