2023-09-01から1ヶ月間の記事一覧
judge.yosupo.jp こちらです。これを解くアルゴリズムの一つとして下記があります。 Kolpakov, Roman, and Gregory Kucherov. "Finding maximal repetitions in a word in linear time." In 40th Annual Symposium on Foundations of Computer Science (Cat.…
背景としては、こちらの記事です。 rsk0315.hatenablog.com 1431655766, 1717986920, 1431655782, 1431655768, 1840700272, 1431655966, -1431655056 などさまざまなマジックナンバーが登場します。 「$x$ が $3$ の倍数であることがわかっているとき、$1431…
Clang が $\sum_{i=0}^n i$ を $n(n+1)/2$ にしてくれることは有名です*1。 また、$\sum_{i=0}^n i^2$ も $n(n+1)(2n+1)/6$ にしてくれます。 その過程では、 unsigned v1 = n * (n - 1) * (n - 2) / 2 * 1431655766u; unsigned v2 = n * (n - 1) / 2; retur…
タイトル欄やカテゴリ欄で ⌃M を押すと、何らかの力がはたらいて記事が投稿されてしまう、あぶない(一敗)。 右下が「下書きを更新する」や(投稿後編集中の)「更新する」であってもそうなる。
競プロ er はよく計算量の見積もりをします。「これこれの計算量は $O(\dots)$ なので十分高速である」といった具合で上から抑えることが多いです。 また、「これこれの計算量は $\Omega(\dots)$ なので TLE しそう」といった具合で下から抑えることもしばし…
↓ ここが hello になっていれば勝ち zzz ↓ 擬似コードが render されていれば勝ち function $\textsc{Identity}(x)\colon$ return $x$
先日、下記の記事でナップサック問題の DP を愚直に眺めました。 rsk0315.hatenablog.com 今回は、ナップサック問題に限らず様々な DP を愚直に眺める回です。 「○○(何らかの集合)の最大値」のように計算せず、○○の部分について考えていきます。 もちろん …
典型的な DP の実装の属性の一つとして、配る DP・もらう DP と呼ばれているものがあります。 もらう DP を集める DP と呼ぶ派閥もあった気がしますが、ここでは名称についての議論はしません。 導入 主張 例 ナップサック問題 Eratosthenes の篩 回数の期待…