最近気づいたので書きます（有名かも？） 有名な等式として （ は正整数）があります。これを証明します。 整数 と実数 に対して であることを利用します。 を整数として ですが、 の後でだけ を適用すると が得られ、 の両方の後で を適用すると が得られま…

間違っている部分やもっと簡単にできる部分などがあれば教えていただけると助かります。 この記事での記法など XOR 演算子は で書く。 非負整数の（有限）集合 に対して全体の XOR を とも書く。 非負整数の（有限）集合 に対して （何個か選んで作れる XOR …

書いた動機 range chmin でググるとなぜか beats の話しかヒットしないので 区間 chmin 一点取得 だけならもっと簡単にできます。（当たり前ですが chmin を chmax に替えても可） ACL の遅延セグ木を使う ABC179 解法 • knshnbのブログ の F のようにすれば…

競プロにもありそうな教育的な問題だと思いました。 問題 問題リンク の並べ替え について、 となる の個数を とする。すべての並べ替え について を足し合わせた値を求めよ。 解答 を、 であるような の順列 の個数とします。 のときは撹乱順列の個数で、包…

この記事の目標 SBT についてざっくり理解して、次の機能を実装できるようになります。 Library Checker - Stern–Brocot Tree ABC333 G - Nearest Fraction のような問題を SBT 上の探索で解く おことわり 新規性は特になく、既存の記事を自分用にまとめた程…

概要 競プロでは「周期性」を利用して解く問題がたまに出ます。例： D - Teleporter 長さ の数列 が与えられる（）。 から始めて、 という置き換えを 回行ったときの の値を求めよ。 E - Sequence Sum 漸化式 で定まる数列 に対し、 を求めよ。 難しくはない…

JAG 夏合宿 2023 に参加した。 ICPC のチームは Magical Fish で、メンバーは自分と magsta, confeito の 3 人。今回 confeito 君に合宿に誘われたので行くことにした。（本当は 3 人で行きたかったけど magsta 君が来れなかったみたいで残念） 1 日目 コン…

ABC 寄り？ 問題 難易度 コメント SLASH 100 わかる人には元ネタがわかりそう Time Bomb Game 250 わかる人には元ネタがわかりそう 2 Strong String 300 初作問 Sum of Slide Max 500 K Consecutive Ks (Easy) 550 FizzBuzz Difference 575 ARC 寄りのつもり…

大学の授業で Dilworth の定理が出てきたので、この機会に（競プロer 的な視点から）まとめてみたいと思います。 例題 1 最小パス被覆 最大独立集合 Dilworth の定理 （補足）半順序集合とそのグラフ表現 半順序集合の定義 半順序集合のグラフ表現 半順序集…

概要 通常の最短経路問題と違って、辺を通ったときのコストの変化のしかたが変な場合でも、ダイクストラ法で解けることがある。ダイクストラ法を適用できる条件は 「途中のコストをあえて大きくしたほうが最終的なコストが小さくなる」ということが起こらな…

概要 「条件を満たすものすべてについてのスコアの総和を求めよ」という形の問題を DP で解けることがある。このときスコアの総和だけをもってもうまくいかなくて、条件を満たすものの個数も同時にもっておく必要がある。 例題 atcoder.jp 個の整数 がある。…