えびちゃんの日記

えびちゃん(競プロ)の日記です。

今年のえびちゃん 2021

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

二分探索の上限を適切に決められずに失敗する人かわいそう

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

最近夢で見た問題

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

Python でも set::lower_bound っぽいことがしたい

したくない人は読まなくていいです。 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) のおさらいを軽く…

全方位木 DP を指して rerooting と呼ぶ風潮に対するお気持ち表明

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

インタラクティブ問題のデバッグに関してなど

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

誤差許容ジャッジちゃんと遊んでみる (part 0)

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

bitset 高速化が定数倍高速化という風潮に対するお気持ち表明

「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 番目の素数を求めるよ

軽めの記事です。 \(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…

intXX_t に関して

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

ICPC 2020 Asia Yokohama Regional 参加記

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

自分で未定義動作を書いて逆ギレする人かわいそう

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

Re: オーバーフロー判定が分からない人のためのスライド

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

ACL の math の解説をするよ

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

PAST #5 J - 長い長い文字列

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

sum of floor of linear の解説するよ

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

ICPC 2020 夢地区参加記 3

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

非再帰セグ木上の任意始点にぶたん

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

α(n) とお近づきになりたい人のための記事

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

PAST #4 参加記

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

ICPC 2020 国内予選参加記

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

ICPC 2020 夢地区参加記 2

参加記 1 は これ。 意外と好評でした。 辛そうにしてるの笑うのはなあと思いつつも内容が面白くてめちゃくちゃ笑っちゃった— olphe (@_olphe) 2020年11月2日 おもしろかった シリーズ化してほしい— そすうさᕱᕱ(素数うさぎ) (@wk1080id) 2020年11月3日 シ…

ICPC 2020 夢地区参加記

夢の中で ICPC に出てた、参加記書くか迷う— えびちゃん (@rsk0315_h4x) 2020年11月2日 ICPC に夢の中で参加してきました。せっかくなので参加記を書きます。 見たい— olphe (@_olphe) 2020年11月2日 期待しないでね。 チームメンバーは monkukui と TAB と…

あとでなおす

競プロをしていて、一時的に値を決めておくけれども、提出時には直したいということがあるかもしれません。何らかの理由で。 int m = 10; // to be edited 実際には m は入力によって変えるべきだけれども、手元のデバッグなどの都合では定数の方が楽、とか…

要素の追加・削除と mex を対数時間で処理するよ

自然数(\(0\) を含むよ)の集合において、mex というのは、minimum excludant (minimum excluded) の略で、それに含まれない最小の自然数のことです。 以下の方針では、もう少し自由なことができます。 整数の集合に対して「\(n\) 以上であって、集合に含ま…