2014-01-27から1日間の記事一覧
(辺の数が奇数の頂点数)/2本の線は最低でも存在する事がすぐ分かります。 また、どのような線と円の置き方をしても、そこから線を結合(a~bという直線とb~cという直線をa~cという直線で置き換える)するという動作だけでその本数まで直線を減らせる事がわかり…
解法としては平方分割です。 本来ならadd,count共にO(√n)ですが、countにはラッキーナンバーの数、30個程度が定数として掛かります。 よって最悪ケース、つまりすべてcount(2, n)ならば √n*m*30で約100000000、平方分割の定数もあって危ないです。 僕は絶望…