H - Generalized Insertion Sort 解法 まず制約に注目すると、$25000 \geq n \log n$ にしか見えないので、そのような計算回数を実現するアルゴリズムを考えたい気持ちになります。木に関するアルゴリズムであって、計算量に $\log$ が現れるものは僕は現時…

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

E - Frequency他の人の実装を見るとなんだかあっさり実装されているので、より簡単な解法がありそうです。 解法 数列に出現する数 $x$ について、数列全体に $x$ 以上の数が何個あって、その一番左の数の $index$ が何であるのかがわかれば答えがわかりそう…

E - Prefix-free Game 解法 まず文字列は $0$ と $1$ しか含まないので、完全二分木で考えました（この考え方は、一般的な文字列においても使えるらしく $Trie$木と呼ばれているらしいです）。すると、木の頂点を順に塗りつぶしていく問題に変わります。ある…

F - XOR Tree 解法 $XOR$ の性質を使ってかなりきれいに解けます。まず、パスに関する操作が非常に扱いにくいため、なんとかしたい気持ちになります。$XOR$ の性質で重要なものとして、任意の数について、それ自身との $XOR$ は$0$ になるというものがありま…

I - Simple APSP Problem$2000$ 点の問題ですが、以下のアルゴリズムで使う発想ができれば、解くことができます。Hirschberg's Algorithmについて - Learning AlgorithmsEnglish version is available here. 解法 グリッドを適当に二つに分割することを考え…