Learning Algorithms

アルゴリズムの勉強メモ

CSA

CS Academy 069 D. Cover the Tree

CSA

CS Academy 解法 木を最小個数のパスで被覆する問題。選ぶパスは重複して良いことに注意します(もし重複を許さないなら、それはオイラー閉路を適切に構築してそれを出力する問題です)。とりあえず、葉は必ずパスの端点として選ぶ必要がありそうです。よっ…

CS Academy 065 E. Classic Task

CSA

問題 CS Academy 感想 変わった問題でおもしろいです。 解法 自明 $DP$ 解を書くと、やばいくらい $MLE$ します。$O(nm)$ のグリッドを用意するだけで $MLE$ するので注意です。空間計算量を落としたいので、$Hirschberg's\ algorithm$ (参考)という最高のア…

CS Academy 062 E. Trees Partition

CSA

CS Academy 062 E. Tree Partition CS Academy 解法 なんらかの方法によって、各部分木の頂点集合とその補集合が即座にわかればよさそうです。しかし各ノードに部分木の頂点集合のsetを持たせるのはさすがに厳しいです。そこで、各頂点に乱数を割り振って、…

CS Academy 061 F. Xor the Graph

CSA

CS Academy 061 F. Xor the Graph CS Academy 解法 これを読んでいるとこの解法がかなり自然に見えます。まず明らかに同じ辺を3回以上使うメリットはありません。そのような構造は、パスの個数を増やすことなく、パスの長さを小さくできるからです。すべての…

CS Academy 060 E. Flip the Edges

CSA

CS Academy 060 E. Flip the Edges CS Academy 感想 DPの書き方がよくわからなかったので、pekempeyさんより解説をいただきました。 解法 まず二度以上選ぶ辺は存在しないことが言えます。なぜなら、もし仮にそのような部分があるとき、そのような部分は反転…

CS Academy 058 E. Path Inversions

CSA

CS Academy 058 E. Path Inversions CS Academy 解法 ある長さ $k$ のパスを固定して考えると、このパス上の転倒数の個数とこのパスを逆に進むようなパス上の転倒数の個数の和は、書かれている数に関わらず常に、${}_{k + 1} C _2$ となることがわかる。これ…

CS Academy 050 Div.2 E. Min Swaps

CSA

CS Academy 050 Div.2 E. Min Swaps CS Academy 感想 見掛け倒しな感じがある。 解法 まず値が大きいものと小さいものが順に現れるように順列を作れば、なんとなく条件を満たしそうなことから、そのように並べてみる。その数列が小さいものからスタートする…

CS Academy 050 Div. 2 Check Square

CSA

CS Academy 050 Div.2 Check Square CS Academy 感想 色々やり方がありそうだけど、頂点を見る順番で全探索した。 解法 4点の位置関係がわからないので、その関係を全探索する。順番に点をずらしながら辺を4本とって、その長さがすべて等しくなるような場合…

CS Academy 048 D. Dominant Free Sets

CSA

CS Academy 048 D. Dominant Free Sets CS Academy 感想 アルゴリズムの正当性を証明していたにも$\ AC\ $できず......。結局FenwickTreeのクエリ処理時にMODをとっていなかっただけだった。 解法 まず$\ x\ $に関してソートしておき、その列の上で順に$\ y\…

CS Academy 46 Div. 1.5 C. Set Subtraction

CSA

CS Academy 46 Div. 1.5 C. Set Subtraction CS Academy 感想 ちょっと応用できそう。 解法 まず数列はソートしておく。そして$\ X\ $について全探索する。全探索といっても$\ X \leq A_{n - 1}\ $ですべて試していると間に合わないので、$\ X\ $の候補とし…