2017-02-09から1日間の記事一覧
とりあえず1を根とする根付き木として考える。 f[i][j][k] := 頂点iについて、頂点iの子孫のうち、iからその子孫までのパスの距離のjビット目がkであるような子孫の数 とする。これをメモ化再帰で解く。 ある頂点uについて uが最も根に近い頂点であるような…
等しい要素は、素集合データ構造でくっつけていく。 また、互いに素なAとBが反意語であることを示すのに an[A] = Bかつan[B] = A のような配列を使う。(unifon find木の各集合を代表する頂点を使えば単なる配列になる。) あとは問題文に従ってこれらを操作す…
解法 まず、[l,r)の部分文字列を作れるかどうか判定するのに 各文字のカウント部分和を計算しておき、 文字iについては cnt[i][r] - cnt[i][l] で数えられる。つまり[l,r)の範囲に文字iがあるかどうかわかる。 [l,r)の範囲にあるすべての文字iについて r-l >…