hotpepsiの練習帳

TCO16 Algorithm R2B

01:18

https://competitiveprogramming.info/topcoder/srm/round/16739/div/1

Easy (300) TriangleTriples

問題

• 三角形の辺の長さになりうる3つの数を三角形数とする
• 1以上A以下のa、1以上B以下のb、1以上C以下のcの三つの組み合わせの三角形数の総数を求める

方針

• (終了後)
• pekempeyさんのを写経
• 1辺が2辺の合計より長くなる領域は三角錐(を削った形)になる
• 直方体から3つの三角錐を引く
• ただし、1辺がすごく長いときは二重に削るので、その分は戻す
• https://github.com/firewood/topcoder/blob/master/tco_2016/TriangleTriples.cpp

結果

--- 139th/693 0pt 1543 -> 1523 (-20)

これは難しかったので座ってるだけだった。

C >= Aの領域がよくわからなくなったのでRで図を描いた。

三角錐は天地逆の感じ。

縦がC、横がAで、AがCより小さいときは、カットされた形になる。

http://togetter.com/li/979836