Bが分からなかった。
No.1623 三角形の制作
解説AC。
まず、$n \le 2 \times 10^5$なのに、$r_i, g_i, b_i \le 3 \times 10^3$というのがどういう意味なのか気付く必要がある。
言ってしまえば、実質$n \le 3 \times 10^3$なんですよね。そこに気付くのが重要。コンテスト中この制約は見ていたはずなのだけど、頭が回っていなかったのか理解できていなかった。
（緑色、青色）のペアを全列挙できるということに気付いたら、累積和を使うという発想はまあ自然ですね。
No.1624 三角形の反射
方針は自力で分かったが実装で非常に苦労した。
公式解説のように、平面上でたくさん折り返す方針ではなく、縦方向にだけ折り返して、その長方形の中を進んで行く方針で解いた。
後は場合分けするだけなのだが、同じ高さの場合を例外扱いする必要があることに気付かず、WAを出し続けた。
No.1626 三角形の構築
Ravi変換を使ってAC。タグを見たので思い出せたが、最近別の問題でも見たので、自力でも思い出したと思う。どの問題で見たんだろう？
三角不等式を扱いたいときはこの変換を使うと良いことが多いらしい。
S*S/Tの因数分解や約数列挙に若干困ったが、これは、SやTをそれぞれ因数分解すればOK。約数の個数が見積もれず計算量が不安だったが普通に通った。
0 件のコメント:
コメントを投稿