Mister雑記

競プロやります。

AGC036-A 「Triangle」 (400)

atcoder.jp

問題

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

  •  1 \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必要十分条件となる1。この絶対値は外しても問題ない。

ここで X_3 = 0として後者を無視したくなるが、 Sが大きい素数の場合に構築不能なので X_3 = 1とする。すると条件は X_2 Y_3 = S + Y_2となる。

 Sが最大のケースを考えると、 X_2 = Y_3 = 10^9以外に解は存在しない。ここから「 Sを近くの平方数に近づけたら上手く行きそうだな」となる。

 Z Z^2 \lt Sを満たす最大の整数とする。このとき

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

とすれば良さそうだが、 S = (10^9 - 1)^2 + 1のようなケースで Y_2が制約の2倍弱になってしまう。

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

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

とすれば、 Y_2が大きくなりすぎるのを防ぐことができる2.3

実装例

atcoder.jp

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

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;
}

反省

  • そこそこ時間を食ったが、まぁ妥当な気がする。
  •  Y_2 = 1, Y_3 = 10^9で固定する方法の方が楽らしい。

  1. 作る三角形の面積が Sではなく S/2であることに注意。

  2.  S \leq Z (Z + 1)の場合、 Y_2 = Z(Z + 1) - S \lt Z (Z + 1) - Z^2 = Z \leq 10^9

  3.  S \gt Z (Z + 1)の場合、 Y_2 = (Z + 1)^2 - S \lt (Z + 1)^2 - Z(Z + 1) = Z + 1 \leq 10^9 + 1