はてなブックマーク

この記事について この記事では、一部で全方位木DP、Rerooting等と呼ばれているアルゴリズムの紹介/解説と、その実装についての簡単な説明を行います。 全方位木DPなどと物騒そうな名前がついていますが、発想自体は全く難しくありません。また、実装もそこまで難しいものではないです。 前提知識として、最低限のグラフ理論の知識(特に木構造について)を要求します。(有向木の根/部分木等…) 謝辞 この記事中に挿入されている図は、殆どを @259_Momone さんに提供して頂きました。素晴らしく美しい図を提供して頂き、この記事を分かりやすいものとして頂いたことに感謝いたします。 全方位木DPとは 各点から深さ優先探索を行って解くことができる問題のうち特定の条件(後述)を満たすものについて、全頂点についての答えを同等の計算量で求めることができるアルゴリズムです。 まず、全方位木DPで解くことができ

要約 ロリハ(RollingHash)のModを$2^{61}-1$にすると安全で爆速になってむちゃくちゃ幸せになれます。 前提知識 bit演算に関する基礎的な知識を要求します。 また、RollingHashについては以下で解説しますが、分からない場合は別の記事を読んだほうがいいかもしれません。 RollingHashとは? 開く 「文字列を一つの大きな整数として見る」というのがRollingHashのアイデアです。 まず、0-9のみの数字を含んだ文字列s = "1234567890"を考えてみます。 ここで、この文字列のHash値を文字列を10進数と解釈したときの数値と定義します。 また、$s$の$a$文字目から$b$文字目の前までの部分文字列を$s[a..b]$と書くことにします。 例えば、s = "1234567890"について、$s[1..3]$は1文字目から3文字目の前までの部分

はじめに この記事は、「bit列を用いたbit全探索」を前提知識としています。それ以外は基本的に記事中で説明するように心がけています。 もし不安がある場合は、この記事を読むと理解が進む可能性があります。 また、記事中のサンプルコードは基本的にC#で書かれていますが、できる限り平易な書き方を心がけています。 本記事で説明するテクニックで落ちる計算量は、現実的には高々$20$倍程度の改善にしかなりません。このオーダーだと定数倍レベルが大事になってくると感じているため、そこも意識した記事構成としています。ご了承ください。 bit全探索 突然ですが、bit全探索を用いて以下の問題を解いてみましょう。 問題 $A_1,A_2 \cdots A_N$という数列があります。この数列から数をいくつか選び、その総和が$M$に最も近くなるような選び方をします。そのときのMとの絶対値を求めて下さい。 【制約】