A を読む 解けない B を読む 解けない C を読む セグ木で丁寧だけど L/2 付近の挙動が良く分からなかったので放置 D を読む 解けない E を読む パターンマッチング系なのでどうせ S か T で Trie 作って、Aho Corasick すると終わり ひいひい言いながらライ…

概要 数列 に対し、その gcd 畳み込み*1 を以下のように定めます この畳み込みの計算方法と、応用として AGC038-C を解く手順を示します。 数列の変換で要素毎の乗算に変換 数列から数列への関数 を導入します。 は倍数の和を取る変換で、以下のように定義し…

概要 シンプルなアルゴリズムですが、Level Ancestor Problem 自体の知名度が低そうなので宣伝を兼ねて紹介します。 Level Ancestor Level Ancestor とは、根付き木について定義される概念です。 の祖先であって、深さが であるもの ( の深さ ) の深さが分か…

概要 最もシンプルなポインタによる二分木の実装は、各ノードが左子と右子を保持することでしょう。 一方でこの実装では親方向へ遡ることが出来ません。すると例えば平衡二分探索木のイテレータを実装するときなどに問題になります。 親へのポインタを保持す…