読者です 読者をやめる 読者になる 読者になる

うにゅーん、って感じだ

SRM, CF, AtCoder黄. SRM highest:1746. C#を書きます.

三角形はいくつ? 雑記

これは
ひとり Advent Calendar 2016 - Adventar
の14日目の記事です。



アドベコン2016の12日目の問題を担当させていただきました。

www.adventar.org


問題はこちら
No.461 三角形はいくつ? - yukicoder


問題概要としてはパズル的なのでよくある、線をいっぱい引いた図形の中に三角形がいくつあるか数えるものです。




さて、解法としては、直線を3本取ってきたときにその3本で三角形が描けているか、を判定してあげればいいです。



判定方法についてですが、まず3本が1点で交わるとダメです。また、3本の互いの交点のうち一つでも最初の大きな三角形の外側にある場合、3本は最初の大きな三角形の中のみ伸びてる線分なのでこれも三角形となることができません(日本語が下手)。


実は、この2点をクリアすればその3本は必ず三角形を描けています。



次はこれを実際にどう判定するかですが、
{\displaystyle q_i = \frac{b_i}{a_i + b_i}}
という値に注目すると、
前者は3本の {q_i} の和が1であるかどうか、後者は3本のうち任意の2本に対して {q_i} の和が1より大きいかどうか、にそれぞれ対応しています。
(これはもちろん {\displaystyle \frac{a_i}{a_i + b_i}} という値に注目してもほぼ同じように解けます)


この判定を全組み合わせに対して調べれば、とりあえず {O(N^3)} で解けます。ただ、2本を確定させたとき、もう1本に対して3本の {q_i} の和が1になる線分があるかどうかと、任意の2本の {q_i} の和が1以下のものがいくつあるか、というのは {q_i} の値でソートしておけば両方 {O( \log N)} で解け、結果 {O(N^2 \log N)} となります。

(うまくしゃくとりとかすると {O(N^2)} になります)





これは最初 {O(N^3)} が通る制約で★2で出す予定でした。ただ、アドベコンの周囲の問題の難易度を眺めているとどうも★2が多そうだったので(ただこれは罠でその後みんな★3に昇格した{O(N^2 \log N)} に制約を変えて、ついでに誤差を {10^{-16}} 程度まで小さくして分数で足したりソートしたりしてもらうようにしたりとか、{N = 4000} にしてオーバーフローを誘ったりしました。


ただいくつか誤算があって、まず、long double は仮数部が 63bit あるので、long long の範囲では誤差が出ない、ということ。これは出題前に気づいていました。本当は浮動小数点数を使った解答を全て誤差死させたかったのですがまぁ致し方なし。double がほぼ全て落ちるだけでも僥倖みたいなところがある(ちなみに C# には double より精度の高い浮動小数点数型が存在しないので分数解しか通らない、はず)。


次に、変に {N = 4000} とかいうギリギリを攻めたせいで TL が少し厳しくなってしまったこと。これは kimiyuki さんにテスターをしていただいた際に明るみになりました。まず、Python ではナチュラルな {O(N^2)} が TLE するらしくもうびっくりという感じなんですけどまぁこれは置いといて。問題は、分数クラスがちゃんとしていて毎回約分するようなものだと毎回 {\log} がかかって 5sec でも TLE することがあるらしくにゃーんという感じでした。

それと相反して {O(N^3)} が通っていたりもして、それは本当にびっくりなんですけど。というのも、オーバーフローをさせる関係で今回ちゃんと最大ケースを作っていて。しかもそれの答えが 23億 とかで。でも一つ一つ数え上げて 4sec ちょいで通っていて。もうC言語ってなんなんだよ、という感じ。

それと★4に昇格したのも誤算の一つで。おそらく {N = 4000} のせいで解法が {O(N^3)} の全探索から一つ {\log} に落として高速化、というプロセスを辿りづらかったのかも? 部分点というか部分ケースがあってまずそっちが通るかどうか試す、みたいな方針でいったらもう少し楽に解かれたのかも。そもそも {O(N^2 \log N)} が通る制約に見えなくてずっと {O(N \log^2 N)} 解を考えてた、とかがあったらめっちゃ申し訳ない。



でもまぁストックのクソ問が思ったよりいい感じな問題になった(ほんまか?)のでまぁよかったかなぁ。とは言ってもストックのクソ問の中でもまだマシなほうなので残りのストックは本当に日の目を見ることがないかも……。