右辺は で計算できるので、時間計算量は問題にならないことが多いです。 使う場面 この式を使って和の和を積の和に言い換えると、分配法則が使えてやりやすくなることがあります。 ただし和の和も和の順序の交換などの良い性質を持つので、どちらが良いかは…

優勝しました。すばらしい！ チーム編成 tatyam tatyam - AtCoder potato167 potato167 - AtCoder noshi91 noshi91 - AtCoder goodbaton さんが引退し、potato167 に新たに入ってもらった。 to 要素があったためチーム名は tonosama で続投。 開催まで 12/5 …

Increasing Prefix XOR https://atcoder.jp/contests/arc141/editorial/4048 と を比較することで、答えの具体的な形を FPS を使って導出する。q-binomial coefficient と関係がある。 Stonks https://atcoder.jp/contests/abc250/editorial/3945 離散凸解析…

potato167, noshi91, tatyam で参加しました。 tatyam 視点 → ICPC 2022/23 国内予選参加記 (tatyam 視点) | 東京工業大学デジタル創作同好会traP 初手 A: potato, B: tatyam, C: noshi で担当。noshi は実装が遅いので序盤の速度ゲーに触りたくないため、こ…

概要 を満たす の正整数の約数の個数の最大値は 程度と思っておけば競プロの計算量の見積もりで便利そう。 実験 を の正の約数の個数として、 と定義し、 と の関係を見る。 つまり、 と見積もると実際 *1 にはその 倍から 倍程度に収まることになる。 例え…

2022/05/02 記事中の記号の使い方やその他の軽微な修正をしました。 概要 のアフィン部分空間が の形で与えられるとき、 つのアフィン部分空間の共通部分を時間計算量 で計算する。 アフィン部分空間 ベクトル空間 の部分集合 は、部分空間 と によって と表…

概要 Xorshift によって生成された乱数列について、いくつかの場所の xor を取ると seed に依存せずに になる。 Xorshift Xorshift - Wikipedia 説明は Wikipedia に丸投げする。 本記事では簡略化のため、実装例の一番上にある周期 の実装について議論する…

概要 木上の等高線集約クエリ - suisen のブログ この記事で未解決になっていた変種 を解決する。 を可換モノイドとし、 頂点の木 の各頂点には の元が書き込まれているとする。 に書かれている値を に書き換える。 から距離 以上 未満の頂点に書かれた値の…

チームメイトに投げる場面が多く自分の実力の低下を感じた。 K を検索したのが一番の貢献だったはずだが通せなかったため無に 来年度どうするかあまり考えていない (参加はしたい) 今年は特に問題が面白いと感じたので upsolve 予定

定義 が を満たすとする。 を与えると を の時間計算量で取得できるとして、 を満たす を の時間計算量で求めるアルゴリズムが存在する。 アルゴリズム 一般の数列を三分探索すると極小点が求まるとは限らない - noshi91のメモ 上記の記事の後半で紹介してい…

概要 三分探索を行うと極小点が つも求まらないような数列を構成した。 また、一般の数列に対して の時間計算量で極小点を つ求めるアルゴリズムを説明する。 定義 を実数列とする。 整数 が の極小点であることを、 を満たすことと定義する。 ただし仮想的…

概要 https://dic.kimiyuki.net/d-edge-shortest-path-monge この記事においてラグランジュ双対などで説明した部分を凸共役の観点から解釈し、「 本以上 本以下使う最短路」も同じように解くことができることを解説します。 本文 合成積 関数 の合成積 は \b…

注意: 雑です 概要 [1] で定義された top tree は、葉が underlying tree の辺に対応するなどの条件があります。 [2] は splay tree をベースにした top tree を説明しています。 [1] の定義にはわずかに合致しないものの、いくらかの良い性質を持つ構造を思…