解けなかった問題の復習。C（300点）は何とかなったけどD（400点）はちょっと勉強しただけでは理解すらできないレベルなのでパス。もうちょい他の初歩的な問題でDFS理解してからまたトライする。
Cの解説を読むと、普通に計算すると誤差がでるので以下どちらかで解くよう書いてあります。
・計算機誤差を考慮する
・整数で比較できるよう
後者でトライしましたが、以下のコードだとWA。
#include <iostream> #include <cmath> using namespace std; int main() { int a,b,c; cin >> a >> b >> c; long long int d = c-a-b; if(d>0 && d*d > 4*a*b){ cout << "Yes" << endl; }else{ cout << "No" << endl; } return 0; }
恐らく、a,bが大きいときにif文内の (4*a*b) がオーバーフローしてる予感。入力のa,bを64bitにする事でACできました。多分、下の結果みたいな感じですかね。
int a, b, c; a = b = c = 1000000000; long long int la = a, lb = b, lc = c; printf("%ld\n", 4*a*b); // 2643460096 printf("%ld\n", 4*la*lb); // 4000000000000000000
しかし、int（32bit）同士の途中計算でオーバーフローするっていうのも何かコンパイラが上手くやってくれよって気持ちだけど。この辺詳しくないのできっと出来ない理由があると思うので、週明け会社でアセンブラ出力してみよう。
あとこの問題で一番難しいのは、最初の「普通に計算すると誤差がでる」って所だと思います。整数で32bit同士の足し算が32bitに入らない事があるのは分かりやすいけど、実数ってその辺が複雑だし、あと拡張倍精度なら精度足りるの？っていうのが明確に分からない気がする。ついでに、解説にもこの辺説明はない。（説明できるのですがしないです、というフェルマーみたいな事が書いてある）
ちょっと考えてみます。解説の例に限れば別にeps持ち出さなくても一度long double（80bit）に代入すれば正しい結果なんですが、サンプルにはそれだと通らないものもあるようでACしないです。
// 後者は一度long doubleに代入した場合。ちゃんとsqrt(999999998)より小さくなってる // 31622.776570061017991974949836730957 // 31622.776570061016172985546290874481
こっちの解法の説明してる人が全然いない（そりゃそうか）ので、ちょっと理解が深まってないけど、まぁ問題からは誤差が出そうって事が読み取れればいいですかね。
