Learning Algorithms

アルゴリズムの勉強メモ

Codeforces 458 E. Palindromes in a Tree

Problem - E - Codeforcespekempeyさんが書かれたコードから学びました。わかりやすすぎてありがたすぎます。 解法 まず、ある文字の集合を適切に並べると回文になるという条件は、出現回数が奇数である文字の種類が $1$ 個以下である、という条件に言い換え…

Hirschberg's Algorithmについて

はじめに $Hirschberg's\ Algorithm$ に関する解説を丁寧に書きました。 問題 まず次の問題をご覧くださいCS Academy概要:各マスに数字が書かれたグリッドが与えられ、そのグリッド上で左上のマスから右下のマスまで最短経路で移動することを考える。その通…

重心分解による分割統治法の一般形について

追記 2018/01/22 ・重心を求めるアルゴリズムを変更して高速化しました。 ・最後に実践的な例題を置きました。 はじめに アリ本に載っているものよりも、(個人的に)わかりやすく整理した重心分解による分割統治法の一般形について書きます(アリ本でばっち…

CS Academy 065 E. Classic Task

CSA

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

Atcoder Regular Contest 063 E. 木と整数 / Integers on a Tree

Atcoder Regular Contest 063 E. 木と整数 / Integers on a Tree E - 木と整数 / Integers on a Tree 感想 ふつうに木の上で計算しました。 解法 まず頂点 $0$ を根として考えることにします。明らかな性質として、深さが同じような頂点に書かれた値すべての…

Atcoder Regular Contest 088 F. Christmas Tree

Atcoder Regular Contest 088 F. Christmas Tree F - Christmas Tree 感想 木をいくつかのパスで被覆する、よくありそうな問題です。CSA Flip the Edgesに似ています。 解法 まずパスの両端の次数は奇数でそれ以外は偶数である(それはそう)という性質から…

第4回ドワンゴからの挑戦状予選 E. ニワンゴくんの家探し

第4回ドワンゴからの挑戦状予選 E. ニワンゴくんの家探し E - ニワンゴくんの家探しかなり好きな問題だったので、本番で通したかった。 解法 まず分割して考えていきたい気持ちになるので、重心に注目します。重心が二つある場合は、その重心の $2$ 頂点でク…