はまやんはまやんはまやん

hamayanhamayan's blog

面積Nの三角形 [yukicoder 1143]

https://yukicoder.me/problems/no/1143

前提知識

解説

https://yukicoder.me/submissions/523047

上に前提知識がもし書いてあれば、そちらを先に学習しましょう(ここではちゃんと解説しないです)

あまり見ないような問題。
自分の経験則から言うとあまり見ないような感じだと特殊な公式とか定理を要求しているかもを頭の片隅で考える。
でも、辺の長さとかで全探索するんだろうなぁ…と思いつつ、考えると、
辺の長さと面積といえばヘロンの公式であり、その辺から考えると浮かんでくる。

ヘロンの公式

これを使う問題は初めて見たかもしれない。
ルートは扱いにくいので二乗してみよう。

S2 = s(s-a)(s-b)(s-c)

s-a=x, s-b=y, s-c=zとして、変換してみると、

S2 = xyz(x+y+z)

とすることができ、きれいになる。

全探索

これでようやくAtCoderでよく見るような感じになってきた。
x,y,zの候補はS2の約数である。
これは最大1012で約数の最大個数は6720個なので、ギリギリ大丈夫かな?という感じ。
実行時間が短いのが気になるが、計算もとても軽いのでやってみる価値はある。

注意点

  • x,yを全探索するが、zは尺取り法で探索する必要がある。ちゃんとO(約数2)に収めないと厳しい
  • あと、ヘロンの公式をそのまま使うと、オーバーフローするので上限付きmulを使うか、何かしら工夫が必要
  • 時間が結構厳しい
    • 下手に時間設定するとO(N2)の賢い枝刈りとか通りそうだし、厳しいのはそのせいだろう
ll N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    N = N * N;
    auto v = enumdiv(N);
    int ans = 0;
    int n = v.size();
    rep(a, 0, n) {
        int c = n - 1;
        rep(b, a, n) {
            while (b < c && N < mul(v[a], v[b], v[c], v[a] + v[b] + v[c])) c--;
            if (mul(v[a], v[b], v[c], v[a] + v[b] + v[c]) == N && a <= b && b <= c) ans++;
        }
    }
    cout << ans << endl;
}