2017-02-09から1日間の記事一覧

Codeforces #396 Div. 2 E: Mahmoud and a xor trip

とりあえず1を根とする根付き木として考える。 f[i][j][k] := 頂点iについて、頂点iの子孫のうち、iからその子孫までのパスの距離のjビット目がkであるような子孫の数 とする。これをメモ化再帰で解く。 ある頂点uについて uが最も根に近い頂点であるような…

Codeforces #396 Div. 2 D: Mahmoud and a Dictionary

等しい要素は、素集合データ構造でくっつけていく。 また、互いに素なAとBが反意語であることを示すのに an[A] = Bかつan[B] = A のような配列を使う。(unifon find木の各集合を代表する頂点を使えば単なる配列になる。) あとは問題文に従ってこれらを操作す…

Codeforces #396 Div.2 C: Mahmoud and a Message

解法 まず、[l,r)の部分文字列を作れるかどうか判定するのに 各文字のカウント部分和を計算しておき、 文字iについては cnt[i][r] - cnt[i][l] で数えられる。つまり[l,r)の範囲に文字iがあるかどうかわかる。 [l,r)の範囲にあるすべての文字iについて r-l >…