Dを飛ばしてFまで五完。Dが分からず、頭が働いていないなぁと思い、AHCの途中だったこともあって途中で諦めてしまった。
D - M<=ab
解説AC。
aを√Mまで探索すれば良いという問題。
実は範囲が狭いため、何かを全探索できる……という系統だと思ったが、考察が進まなかった。
G - Polygon and Points
解説AC。コンテスト中は凸包を作って、その後どうしよう……などと考えていたが、元から反時計回りに頂点が与えられているので凸包は関係ないですね。
解説の通り、xでソートして平面走査した。
ただ、y軸に並行な直線に関する処理でWAを量産。結局、最初にy軸に並行な線分を列挙して例外処理することでACできた。
Ex - Unite
苦戦したが一応自力でAC。
この問題の類題で、Union-findの状態を持ってDPすれば良い。ただ、先に挙げた問題より制約が厳しく制限時間も厳しいため、自分の書き方だとなかなかTLEが取れなかった。
Union-findの配列をencodeするなど普通の工夫の他に、
・次の行を見る際、DPの値が（今までの最低値）+6以上だったら使わない
という正当性の怪しい枝狩りを入れたら通った。
0 件のコメント:
コメントを投稿