AtCoder Grand Contest 036 - 今日から始める競プロ日記
はじめに
AtCoder Grand Contest (AGC) 036 に参加 (2019/07/21)。
今日はA問題と160分戦って解けずに終わった。
「Aが解けなきゃ他の問題も解けないだろう」と思い込んでずっとAに取り組んでいたけど、 30分経っても分からなかったら、とりあえず他の問題に移ったほうがいいかも(結果論)。
他の問題を考えているうちに良さげな解法が浮かぶかもしれない。
結果
- パフォーマンス:378
- レート:715 → 683 (-32)
A - Triangle
三角形の面積S
が与えられるので、
条件を満たす三角形の3つの頂点の座標を求める問題。
条件は以下。
1 <= S <= 10^18 0 <= X1, Y1, X2, Y2, X3, Y3 <= 10^9
三角形の面積の求め方といえば底辺×高さ/2
だけど、
面積が素数だと条件内では求められないと思った。
他の方法を調べたらヘロンの公式が出てきたけど、 ヘロンの公式も結局掛け算だからダメだよなーとか思って、 じゃあヘロンの公式をいじったら良い感じの数式出てくるかなとか思ったけどそんなことなかった(それはそう)。
そのまま時間を溶かしてコンテストが終わった。
コンテスト終了後、解説動画を見ると、
ベクトルの外積を使えば積と積の引き算の計算ができて、
1~10^18
を好きなように作れるということが分かってすげーってなった。
面積と言えば掛け算で求めるのが一般的みたいな考え方で問題解こうとしていたけど、 そんなことはないよなっていうことを知った。
引き算か~(言われてみればそう)。
おわりに
昨日上がったレートがきれいになくなってしまった。