7月18日のPKU
今日：5問
今日までの合計：8問
PKU 2583 Series Determination
問題
関数 f(x) = Ax2 + Bx + C について、f(0), f(1), f(2)の値が与えられるので、f(3), f(4), f(5)の値を求める問題。
ただしA, B, Cは整数で -103 <= A,B,C <= 103 を満たす。
また、-103 <= f(0), f(1), f(2) <= 103 であり、 -104 <= f(3), f(4), f(5) <= 104 である。
解法
やるだけ。
- c = f(0)
- a = (f(2)-2f(1)+c)/2
- b = f(1)-a-c
PKU 2041 Unreliable Message
解法
頑張ってコード書きましょう。
PKU 3625 Building Roads
解法
幅優先で連結成分に分解してると時間が足りないので、元から道があるふたつの農場間の距離を0とみなすことで時間を省く。あとは最小全域木。
PKU 1912 A highway and the seven dwarfs
問題
点がN個ある。直線の情報がいくつか与えられるので、それぞれの直線について、その直線が点の集合を分断するかどうか調べる問題。
点の集合が分断されるのは、N個の点のうちのある点a, bが直線Lから見て違う向きに位置するときである。
点の個数Nは0以上100000以下。
解法
問題文中に直線の個数が書かれていないが、ここではとりあえず直線の数をMとしておく。
まず最初に思いつくのは普通に調べる方法。それぞれの直線について、N個の点の位置を調べて、直線から見て両方に点があったら分断されていると判断する。これは直線ひとつについてN回の調査が必要になるから、計算量は O(NM) になる。これはTLE。
次に考えられるのは凸包を使う方法。全ての点ではなく、凸包上の点のみについて考える。これだと、直線ひとつについて、凸包上の点の数ぶんの調査で済む。凸包上の点の数をHとすると計算量は O*1 である。これでAcceptされる。
PKU 2805 Pegs
問題
5x5のマス目に、一個以上の釘、一個以上の空のマス、四個以上の使えないマスがある。
隣にある釘をジャンプして飛び越えることで、通過された釘はなくなる。という操作を繰り返したとき、最後に残る釘の数を一番少なくしたい。最適な戦略をとったときにいくつの釘が残るか求める問題。
解法
使えないマスが4個以上あるから探索空間は最高でも 221 なのでDFSで余裕。
*1:N log N) + MH) になる。これでもTLE。 ここである角度の線について考える。この線を凸包の右上から左下にスライドさせてきたときに、最初にぶつかる点がひとつある。同じように左下から右上にスライドさせてきたときにも、最初にぶつかる点がひとつある。もしこの線が、この二つの点の間にあれば、点集合が分断されていると判断できる。二つの点の間に線があるというのは、線から見て二つの点が違う向きにあるということである。 ある角度の線について、最初にぶつかる二点が分かれば、その線が点集合を分断するかどうかはO(1)で判断できる。どうすればこの二点を高速に求められるか。 まずある角度Aの線があると仮定する。この線をスライドさせて点Pにぶつけたとする。ここからこの線を回転させていく。するとある角度Bになったときに凸包上の次の点Qにぶつかる。このことから、角度がAからBまでの線が最初にぶつかるのは点Pであることがわかる。さらにこの後も回転させていって角度Cのときに点Rにぶつかれば、角度がBからCまでの線が最初にぶつかるのは点Qということが分かる。これを凸包上の点すべてについて行うと、角度の範囲と点の対のリストができあがる。 後は直線ひとつひとつについて、その角度を求めて、先のリストに対して二分探索を行えば最初にぶつかる点がわかる。二分探索には O(log H) かかる。よって計算量は O( (N log N) + (M log H
