与えられたデータの文字列についてTrie木を構築しますそのTrie木をEuler-TourしてBITを構築します Trie木の頂点ごとに、BITで対応する範囲[l, r]がどこなのかも一緒に計算しておきますその後、文字列ごとに、もう一度Trie木を潜ってその文字列の最後の頂点が…

今日の典型データ構造です。N個のpairが与えられます ただしstringの長さは合計して10^6以下ですQ個の以下のクエリが与えられる k(int), x(int) が与えられる k番目のデータのintを+xする s(string) が与えられる s をprefixに持つ文字列を持つデータのintの…

わっけわかんねえほど沢山の制約ドパァな問題を解く一般的なテクとして、なんかいい感じのグラフを作ったらなんかそれの最小カットが答えというのがあります最小カットで解ける問題はどんなのなのか考えてみました 頂点がたくさんあって、それを赤と青に塗り…

今日の典型データ構造 - よすぽの日記yosupo.hatenablog.com長さNの、bool列(全部の要素が0 or 1)に対して以下のクエリがQ個飛んでくるl, rが与えられるから, l番目~r番目の数列を切り出した時、それの転倒数を求める l, rが与えられるから, l番目~r番目の要…

uwiさんから 長さNの、整数列(全部の要素が1 ~ N, 全部の要素はdistinct)に対して以下のクエリがQ個飛んでくる l, rが与えられるから, l番目~r番目の数列を切り出した時、それの転倒数を求める N = Q = 100,000 TLE2s 重要事項 僕はまだ解法を考えてないです…

長さNの、bool列(全部の要素が0 or 1)に対して以下のクエリがQ個飛んでくる l, rが与えられるから, l番目~r番目の数列を切り出した時、それの転倒数を求める l, rが与えられるから, l番目~r番目の要素を全部反転させる(0だったら1に, 1だったら0に) N = Q = …

RBSTは万能かつ簡潔な平衡二分木として有名ですね Q.でもこれって計算量どうなんやろ A.なんかいい感じやねんのままだとよくないかなぁと思ってちょっと考えてみました注意点として今回の記事では全部i番目というのは0-indexedです あと、スピリチュアルです…

T: フィボナッチ - Typical DP Contest | AtCoder僕はこれの解法の理解に非常に時間がかかりました。なので他の人もきっと時間がかかるよね？ということでメモを残しますまず数列 について となるが与えられているここでf(n) = {}となる関数f(x)を定義する(…

子から異なる2つを選ぶ感じの木DPを解くアレを解くテクニックを紹介します。D: Longest Path - Indeedなう（オープンコンテスト） | AtCoderとかが簡単に解けたりします頂点0を根とする根付き木について 頂点iはa[i]を持つ(a[i] >= 0) 頂点iそれぞれについて…

RUPCに参加しました。1日目は立命館セットで、evimaさんとNOxさんと出ましたがーっと時系列で書くとBをevimaさんがコーディング AはNOxさんがコーディング Aが♨️したためDをevimaさんがコーディング 僕とNOxさんでAをデバッグしたら日本語読解に失敗している…

総評 お疲れ様でした。 問題タイトルが全部英語なのはデレマスの影響です 問題解説 C,D,Eの想定解は長いので後ろにまとめます A問題 Trouble Busters (面倒)100なA問題もいいかなって思った。 next_permutationを使うのが多分一番楽です。 一人ぐらい六重ル…