Max of Pythagorean Triple

解説

この問題は一種の構築問題です。

$A$ , $B$ , $C$ の値を探索する方法では、時間内に答えを出力する事は出来ません。

そこで、 $K$ と一致する値が $A$ である場合について、以下の2つが成り立ちます。

• $B$ の値が大きいほど、 $C$ の値も大きい。
• $B$ の値が大きいほど、 $C-B$ の値は小さくなる。
• $C$ の値は $K$ よりも大きい。

これは $K$ と一致する値が $B$ である場合も同様です。

以上の事から、 $C=B+1$ と仮定し、 $A,B$の関係式を立式します。

$A^2+B^2=(B+1)^2$ となり、式変形をすると以下のようになります。

• $B= \frac{A^2-1}{2}$
• $C= \frac{A^2+1}{2}$

しかし $A$ が奇数の場合については、 $B,C$ ともに整数となりますが、$A$ が偶数の場合については整数となりません。

そこで同様に $C=B+2$ を仮定します。

• $B= \frac{A^2}{4}-1$
• $C= \frac{A^2}{4}+1$

となり、$A$ が偶数の時 $B,C$ は整数となります。

以上から、$K$ の偶奇によって処理を分ける事で $O(1)$ で答えを求める事が出来ます。

ただし、この問題には重要なコーナーケースが存在します。

$A=1,2,4$ の場合について考えましょう。

$A=1,2$ に関して、上記の式で計算すると $B=0$ となってしまいます。これは正整数という条件を満たしておらず、他の値でも条件を満たす事は出来ません。よって $No$ を出力します

$A=4$ に関して、上記の式で計算すると $B=3,C=5$ となります。$A \leq B$ である事から、答えは $3,4,5$ の順に出力する必要があります。

C++での実装例は以下の通りです。