本番全くわからなくて焦った… 解説読んでもあんまりピンと来なかったのですが、半日考え直してようやく理解できたので記事にします。 解法 無限に誰も排除されないことがあるけどどうしよう...となるので、とりあえずサンプル1がなんでこれでいいのかを解き…

ABC331Fでロリハをセグ木にのせろと言ってるようなもんじゃんっていう問題が出たわけですが、その場で解けず悲惨な目にあいました。 なので1点更新のロリハをライブラリ化したわけですが、最近Link Cut Treeのライブラリ化を試みていたりと地味に平衡二分木…

パッと見であんまりよくわからなかったけど、解けてみると面白かったので。 こんなんセグ木に載るんかーといった感じでした。 解法 早い話が、全体の累積和と、各商品種（で分類される種類）の累積和をそれぞれ用意することができれば、各クエリにで回答する…

それぞれ長さであるような配列に対して、といった形の演算を畳み込みと呼び、多項式の乗算の実装等に使えます。 で、そのライブラリのverify用の問題がyosupo judgeにあります(https://judge.yosupo.jp/problem/convolution_mod)。私はRust使いなのですが、…

Montgomery剰余乗算のアルゴリズムを用いると、乗算剰余を計算する際に純粋な除算・剰余算を省くことができる。 用途は色々あって、 128bit剰余算は非常に遅いので、そのような演算が必要な場合には高速化が期待できる SSEやAVX/AVX2には整数除算命令・剰余…

どう考えてもとてもめんどくさいことになりそうなので、機械的に解きたいと思ってやってみたら、案外間に合った。 解法 現在の速度や、速度が上限に達する時間が整数でなくなる瞬間があるのが面倒くさいポイントだが、おそらくたかだか小数点以下1ケタくらい…

ちょっと悩んでしまったが、良い感じにきれいに解けた。 解法 一般に、、とする。 によって構成される格子の1マスに注目して、これがいくつの長方形に含まれるかを考えると、これは となる。(縦の辺については、左側は通り、右側は通り、横の辺については、…

こういうO(1)で気合導出、みたいな問題はめちゃくちゃ苦手… 解法 早い話、ありうる部分列を列挙して重複を除去すれば答えが出る。制約が大きいので重複の仕方が爆発してダメそうに見えるが、重複している数字が1個しかないので、重複の仕方を上手く見つけて…

ネタ解法。理論的な根拠は一ミリもないので閲覧注意。 解法 55個しか出力しなくていいなら、埋め込みがしたくなる。事実、任意の5個の値の和が合成数であるような55項の数列から適当にN個選んできて新しく数列を作っても条件は満たすので、N=55のときの解を…

DP力が貧弱なので、EDPCの解き直しをしつつ、記録を残します。 結構自力で解けてないやつもあるので、解けてない問題は解け次第随時更新となります。 めっちゃネタバレ記事になる予定なので、これから自力で解こうという方はぜひブラウザバックを… A - Frog …