rsk0315.hatenablog.com エゴサしたらこの記事がわりと読まれているっぽかったものの、やや実装が重い気がしたので*1別の解法を書きます。 tl; dr セグ木。 定義 有限集合 \(S\subseteq \N\) における mex というのは、\(S\) に含まれない最小の自然数 \(\mi…

去年末にやると言っていたんですが、やっと終わりました。 クエリで与えられた区間の最長増加部分列の長さを答えるやつで、計算量は \(\langle O(n\log(n)^2), O(\log(n))\rangle\) です。 実装前にイメージがつきにくかったのと、あったら楽しいかなと思っ…

次の操作ができる優先度つきキューのおはなしです。 push(x)：x を挿入する pop_newest(k)：挿入順が新しい方から k 以内の要素の最大値を取得・削除 pop_oldest(k)：挿入順が古い方から k 以内の要素の最大値を取得・削除 取得だけする peek_newest(k), pee…

ここで区間 \(k\)-最小値と呼んでいるのは以下のような問題です。 最初に配列 \(a = (a_0, a_1, \dots, a_{n-1})\) が与えられるよ。 次にクエリ処理を \(q\) 回してね。 クエリは \( ([l, r), k)\) の形式で与えられるので、\(a_l, a_{l+1}, \dots, a_{r-1}…

自分語り記事です。 えびちゃんの一年を振り返る記事をうっかり書きそうになったけど、冷静になったので却下した— えびちゃん (@rsk0315_h4x) 2021年12月16日 うっかりし直しました。 今年お勉強したもの 数学関連のものをいくつか学んだり、昔わかった気に…

競プロ er の間では、（主に実生活で）最適値を探そうと二分探索をして、上限を大きく取りすぎたために破滅するという定番ネタがあります*1。 あるいは、実際のコンテストでも「上限が小さすぎた」「上限を大きくしすぎたため判定関数内でオーバーフローした…

夢に出てくる競プロの問題、自明か既出か #P-complete がち— えびちゃん (@rsk0315_h4x) 2021年11月23日 今回はわりと面白いやつ出たか？と思って考えてたんだけど、寝起きで頭がついてなかっただけで自明枠だったことが判明しつつある— えびちゃん (@rsk031…

したくない人は読まなくていいです。 TL; DR vEB やりたいこと Python の set は「x 以上の最小値は？」「x より大きい最小値は？」といったクエリに答えられないので困ります。それをしたいです。x は整数としちゃいます。 特に競プロの文脈の話なので、外…

思いついたら書きます。 これはなに なにかを思いついたときに、指摘される前に「あー嘘じゃんこれ」というのに気づく用のノートです。あと他人の嘘考察を見るのはたのしい。 嘘考察 嘘考察たちです。 \(n^{1/2}-n^{1/3}=O(n^{1/3})\) \(n^{1/2}-n^{1/3} = n…

計算量についてのお話です。対象は、プログラミング経験はあるが計算量のことを知らない初心者から、計算量のことを知っているつもりになっている中級者くらいです。 数式を見たくない人にとっては読むのが大変かもですが、深呼吸しつつ落ちついて読んでくれ…

最近ロリハあんまり人気なくない？ TL; DR ロリハ + にぶたん で \(O(\log(n))\) 時間で大小比較できるので、愚直に比較する代わりにそれを使ってソートして \(O(n\log(n)^2)\) 時間で構築できる。 おさらい ロリハ ロリハ (rolling hash) のおさらいを軽く…

rerooting DP、rerooting をする DP、DP with rerooting とかなら別によさそう。 全方位木 DP 自体を指して「rerooting」と言われると気になります。 rerooting は木の根を変える操作（全方位木の中で考えられる）を指していて、全方位木 DP 自体のことを指…

インタラクティブ問題は手元でのデバッグが面倒がちなので、いやだと思っている人が多そうです。 coproc というシェルの機能を使えばそこそこ簡単にできないかな？と思ったので、書いてみます。 まえおき 簡単とは言っても、以下のものは自分で書く or 生成…

part 1 以降があるかはわかりません。 導入？ 競プロで、「絶対誤差または相対誤差が \(10^{-6}\) 以下ならば正解と判定される」といった文言はちょくちょく見かけます。 思い出すシリーズ \(2e-3\) atcoder.jp 思ひでポロポロ pic.twitter.com/64N0Qk3SbX— …

「bitset で 64 倍高速化できます」「64 は定数なのでオーダーは変わりません」のような説明は、競プロ界隈でたびたび見かけます。 59 日目の解説です。std::bitset などを使った高速化テクニックは過去に AGC にも出題されたことがある重要事項ですので、理…

\(n\) 以下の素数の個数を求める関数 \(\pi(n)\) を持っていたとします。 このとき、\(n\) の素数判定は \(\pi(n)-\pi(n-1) = 1\) かどうかでできます。 fn is_prime(n: usize) -> bool { n > 0 && prime_pi(n) - prime_pi(n - 1) == 1 } たとえば \(O(n^{3/…

軽めの記事です。 \(n\) 番目の素数を \(p_n\)、\(n\) 以下の素数を \(\pi(n)\) と書くとします。 このとき、\(p_n\) は \(\pi(p_n) \ge n\) かつ \(\pi(p_n-1) \lt n\) を満たします。 よって、これは二分探索で求められます。 上限を決めるのが大変そうで…

別に、おふとんから出たくない朝とかに数えてもいいと思います。 \(n\) 以下の素数の個数を数えたいときどうしますか？ 各整数 \(2\le i\le n\) に対して素数判定して数えます？ 素数判定を試し割り法でやると \(\Theta(n\sqrt{n})\)、線形篩*1を使えば \(\T…

どうしてこんなことに... まえおき 本題 リテラルのつくりかた std::max scanf / printf int8_t ACL の話 そもそも定義されない処理系もある そのほか むかしの まえおき C++ には次の型があります： signed char unsigned char char short signed int (= sh…

あー、おわりです。 えびちゃんの他の参加記は ここから*1。 えびちゃんは B3 の頃から ICPC に出ていました。 four-t で 3 回と、今回 tsutaj で出ました。チームメイトに大変恵まれていたなぁというのをとても思います。 今回で老害化です。 tsutaj（チー…

お店に入るときにドアが開いているか確認せずに歩いていって、ドアにぶつかって怒っている人がいたらおかしい話じゃないですか*1。 未定義動作を起こして怒るのはこれと似ている気がします。 競プロでよくあるコーナーケースなども同じです。 「いま書いてい…

経緯 オーバーフロー判定が分からない人のためのスライドオーバーフロー判定・オーバーフロー判定がわからない人は三 ( ◠‿◠ )☛ 大人しく Python でも使ってろ・ご清聴ありがとうございました— えびちゃん (@rsk0315_h4x) 2021年2月20日 今日は少しだけ真面目…

ACL (AtCoder Library) の内部実装を知りたい人向けの記事です。 お友だちに「ねーね、ACL のこの関数ってどういう仕組みなの？ 知ってたりしない？」と聞かれたとき、「え... なんかほら、わかんないけど、魔法で動くからいいんだよ」としか言えないと情け…

問題ページ。 nagai1mojiretsu 公式解説では後ろからやっていますが、前から解いたので書いておきます。 計算量は公式解説より少し悪化しています。 解法 いままで出力した文字数を y とします（初期値は 0）。 下記のように、順にシミュレートしていきなが…

特に Advent Calendar は関係ない 12 月 13 日の記事です。 これの解説です。 atcoder.jp 以下の二つを参考にしながら考えたことをまとめます。 ACL の floor_sum のコード (特に x_max まわり) が何やってるかわからなくて自分で考え直してたら、x_max が必…

夢地区参加記 2 は これ。 今回は設定が特に謎なのですが、夢なのでそういうものだと思います。 一度ボツにしたものの、変にハードルが上がるとよくないので書きます。 起きた後に軽くメモをしているとはいえ、いくらか日が経っているので正確でない記述があ…

セグ木は知っているとします。 知らない人は えびちゃんのスライド なり適当な記事なりを読んでください。 セグ木上のにぶたんも上のスライドに載っていますが、もう少し解説したいかなと思います。 上のスライドにある図を見るとイメージが湧きやすいかもし…

↓ 勉強し直しました ↓ rsk0315.hatenablog.com union-find の計算量解析で出てくる \(\alpha(n)\) というのがありますね。 Ackermann 関数の逆関数として知られるやつです。 競プロ er の多くは、次のような認識をしていると思います。 計算量に \(\alpha(n)…

考えていたことなどを書きます。 tl; dr 94 点と申します......— えびちゃん (@rsk0315_h4x) 2020年11月8日 受検前 有料期間中に受けるかどうか考えました。 前提として、既にエキスパートの認定証を持っているので、以下のような葛藤が生じます。 エキスパ…

これは夢日記ではありません*1。 夢日記は これ と これ。 チームメイトは夢日記と同様、monkukui と TAB とえびちゃんです。 チーム名は tsutaj で、これは去年までチームメイトだった先輩に由来します。 tsutaj 抜きのチームに tsutaj と名付けるの、余因…