Scoreboard
A - Flea travel
直覺是當 t>N 就不會再去一些未去過的 node, 因此用O(N)頹做就submit了
後來再check, 發現只有 N 是 2 的 power 時才會行哂所有 node
B - Smallest number
應該有一些 greedy 方法, 不過由於懶加上只有4個數字, 就用vector 暴力枚舉
後來看到別人一些「正解」的方法: 加則加最大的兩個數, 乘則乘最小的兩個數
C - Pie or die
在紙上畫畫下, 發現/覺得只要考慮最接近邊界的一個點
第一次submit時是判斷距離<=3, 過不到pretest, 才發現應該是距離<=5
(其實這個錯頗幸運的, 因為如果寫距離<=4 是過到pretest 的)
E - Very simple problem
由於 D 是看似很難的數論, 又發現E 是geom, 便覺得可以一試
E 是 given 一個 convex polygon 和一點 p (保證不在 polygon 任意兩頂點連成的線上), 問有多少種方法選 polygon 的三點形成一個三角形使得 p 在三角形內
做法: 先預處理每一個頂點連到該點的線左邊有甚麼點 (如圖, Right(E) = {A,B,F})
我用binary search 做, 但其實可以一度做一度 rotate
然後, 枚舉三角形其中一點
假設其中一個包含 p 的三角形 XYZ, 必有 Y in Right(X) 和 Z in Right(Y)
這個可以用類似 partial sum 的方法做 (方便起見, 我寫得時侯是由 1 到 2n 的)
但也會數了像 EFA 的三角形, 所以最後要減去 C(|Right(x)|,2)
由於做到 E, 使得排名很幸運地入到頭 20, 開心了好一會
No comments:
Post a Comment