2800 到達時の記録 AtCoder で rating が 2800 に到達しました - noshi91のメモ AtCoder Performances, AtCoder Scores, rating-history などがサービス終了しており寂しさを感じました。 AtCoder AtCoder Charts AtCoder Problems

関連記事 Lagrange inversion theorem - Codeforces [Tutorial] Generating Functions in Competitive Programming (Part 2) - Codeforces 公式集 注意: 一応証明したつもりですが、係数環を一般の可換環に取るところが怪しいです : 可換環 逆関数の係数 \be…

単調増加な正実数列 によって定義される関数 は Monge であることを示せ。 てんぷらによる証明 https://x.com/tempuracpp/status/1854498278190285099 区間の平均値 を定義すると、 である。 \begin{align} & & f(l _ 0, r _ 0) + f(l _ 1 , r _ 1) & \leq f…

グラフ理論ではないしグラフですらない。列。 解法 両端にダミーの頂点を追加すると、操作 は操作 で表現できる。 よって操作 だけを考えればよい。 最初の頂点も操作 で作ることにすれば、問題は以下のように言い換えられる。 頂点 つが辺で結ばれている。 …

問題設定 無向グラフ , 非負の辺重み , 始点 , 終点 が与えられる。 各 について、 上での 最短路長を求めよ。 この問題を の時間計算量で解くアルゴリズムを説明する。 本質的に同じ問題が https://codeforces.com/contest/1163/problem/F で出題されており…

概要 要素の集合を つに分割することを 回行って、どの 要素もどこかで分離されているようにすることができる。 向きの付いた分割についても同様の問題を考え、それぞれの構成法と最適性を示す。 向きの無い分割 問題例 無向グラフ があり、各辺には正の重み…

問題 文字集合を とする文字列 と がある。 の長さ の連続部分列のそれぞれについて、 にマッチするか判定せよ。 ただし文字列がマッチするとは、それぞれの文字列中の を好きな文字に置き換えたときに両文字列が一致することを指す。 解法 (Clifford & Clif…

概要 半順序集合の最大反鎖の計算は通常、Dilworth の定理を用いて最小パス被覆に帰着し、そこから更に二部マッチングへの帰着を行う。 本記事では (最終的にかなり近いアルゴリズムにはなるものの) 直接最小カットに帰着する手法を説明する。 また関連する…

次元遅延セグ木は (かなり制限した設定でも) 実現不能と考えられている (以下の資料を参照せよ)。 勉強会をしました。今日のテーマは「2次元セグメント木」です。スライドを公開します。https://t.co/tL8fMsdBv3— こたつがめ (@kotatsugame_t) 2024年3月18日…

概要 cp-unspoiler この問題の公式解説にある補題群を冪級数を用いて証明する。 定義 この記事内では以下のように定義する。 また、列の大小関係を辞書順で定める。 辞書順関連 を十分小さい正の実数とし、 を で定める。 このとき について となる。 定理 :…

概要 温めておいたのですが、ABC で似た問題が出題されてしまったので (想定解は違いましたが) 起源が問題になる前に公開しようと思います。 問題 標数の十分大きい体 上の形式的冪級数 の 次までの項が与えられる。 を求めよ。 ただし、 を係数とする次数 …

から一様ランダムに素数 を選ぶ *1 。 となる 組の を固定し、誤判定する、すなわち となる確率を求める。 これは が で割り切れることと同値である。 の範囲に素数は 個存在する *2 。 一方、 であるから、 は範囲内の素因数を 個以下しか持たない。 よって…