概要 -march=nativeについて色々調べた。 話題の発端 こちらのツイートであると思われる。 分からんこれ何かの未定義動作踏んでる？？ pic.twitter.com/ACV8fb8PjQ— AllDirections (@AllDirections4) 2023年12月21日 シンプルなコードで、しかも-march=nativ…

概要 / 言い訳タイム FHC 2023 Finalの順位表を見ると、私がBをダウンロードだけして提出していないことがわかると思います。 そもそもカクタス(F)をシバけないとどうしようもないセットではあったのですが、それでもBを出していれば一応5位で入賞であり、こ…

大嘘昔話 実は「segtreeというのはモノイドを載せられて、lazysegtreeはそれにいい感じの作用が行えて…」のようにsegtreeが抽象化されたのは割と最近です。 昔はなんかsegtreeって大体実装一緒だな…と思いながら、みな自分のstarryskytree.cppを毎回コピペし…

注: ガチ誰得記事 Weighted balanced binary treeという平衡二分探索木があります。詳細はwikipedia(Weight-balanced tree - Wikipedia)が詳しいのですが、ざっくり言うと 「子のサイズが親のサイズの少なくとも $\alpha$ 倍」 もしくは同値な表現として「左…

知る人ぞ知る謎の知識みたいになってる気がしたのでメモ。 サイズ $A$ とサイズ $B$ のデータ構造 ($A < B$) が $O(A \log B)$ 時間でマージできる場合、合計 $O(N \log ^2 N)$ 時間で $N$ 個の要素がマージできます。競プロだと std::set や std::priority_…

久しぶりですごい時間がかかったのでメモ 大体次の問題。 $N$ 頂点 $M$ 辺の有向グラフと非負整数 $K$ が与えられる。各辺には非負整数の重みが付いていて、辺 $e$ の重みを $d_e$ とする。$K$ は $1 \to N$ の最短距離より小さくない。 $1$ 円払うと好きな…

AtCoderではともかく、ほかのジャッジでは想定解の正当性の保証がされていない出題が行われることがあります。 想定解の正当性の保証が出来ていなくても、ジャッジが大量にケースを入れてちゃんと動いたからOK!という出題は可能なのか考えてみます。 例えば…

追記：速くなってませんでした！sorry https://x.com/yosupot/status/1689337328547016704?s=20 競技プログラミングではmod 261 - 1のローリングハッシュが安全性と速度のバランスが良く、広く使われています。 詳しくは https://qiita.com/keymoon/items/11…

問題概要 問題 長さNのカッコ列 $a_1,a_2,\cdots,a_n$ が与えられる。これは正しく閉じているとは限らない。各文字は32bit非負整数の重み $b_1,b_2,\cdots,b_n$ を持っている。 カッコ列Sに対して、 $f(S)$ を次のように定義する $S$ が ()を部分文字列とし…