betrue12 https://blog.hatena.ne.jp/betrue12/ ARMERIA https://betrue12.hateblo.jp/ AtCoder プログラミング 競技プログラミング D - Three Colors 解法 三角形の成立条件は、3辺すべてについて「その辺の長さが、他の2辺の長さの合計より小さい」ことです。ただこれをそのまま扱おうとすると3辺全部の長さを管理しながらDPなどをする必要があり、難しそうです。 逆に三角形が成立しない条件を考えます。それはある辺について「その辺の長さが、他の2辺の長さの合計以上である」ことです。こうするとずっと考えやすくなります。 仮に条件を満たさない辺を としましょう。3辺の長さの合計は与えられた の合計になるので、この値を と置くと です。辺 について三角形が成立しない条件は と書けるので、これは となります。これで の長さだけ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbetrue12.hateblo.jp%2Fentry%2F2019%2F04%2F21%2F150214" title="Tenka1 Programmer Contest 2019 D - Three Colors - ARMERIA" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2019-04-21 15:02:14 rich https://betrue12.hateblo.jp/entry/2019/04/21/150214 1.0 100%