Dまで四完でした。
E - Count Descendants
深さごとにnodeを管理して二分探索、ということは思いつけていた。
ただ、オイラーツアーを利用する発想がなかったため、LCAを用いて祖先がどこに当たるかを調べよう、という煩雑な方法を取ってしまった。
一応、この方法でコンテスト後にACはできたので、ひどい方針だったという程ではないが、オイラーツアー（DFS順）の利用は見逃していることが多い気がする。
F - Integer Convex Hull
公式から飛べる公式解説、ユーザ解説、解説動画を見てなんとかAC。
典型090でAndrew's monotone chainを実装したことがあったため、公式解説の方法で実装した。（内部の点の個数の求め方はユーザ解説を読んで理解）
ただ、確かにmonotone chainの方法を元にDPしているのだけど、ただ凸包を作るのではなく、前の点を全て試して凸になるか調べている、というのを理解するのに手間取った。
・start地点を全探索
・i→jと進む辺が凸包に使えるか全探索
・iの直前の点kを全探索（k→i→jと進んだとき、凸包になっているものを選択）
するので四乗なのですね。
そして、DPテーブルには、i→jが上側/下側凸包になる場合の、「総数」を入れる。つまり、全てのk（iの直前の点）に対して、k→i→jが凸包になりうるときの個数の総和を求める。ここで累積和的な考え方を使っていることも理解に手間取った。
一応理解しACには辿り着けたけど、いや難しい……。
0 件のコメント:
コメントを投稿