小さな誤差を積み重ねる操作と、積み重なった誤差に影響される操作を区別して考えましょう。 同じ符号の浮動小数点数を加算や乗算を計 $k$ 回繰り返しても、$(1+2^{-53})^k-1 \approx 2^{-53}\cdot k$ 程度の相対誤差しか生まれません。 競プロにおける演算回数はせいぜい $2^{30}$ 回程度でしょうから、だいたい $2^{-23}\approx 1.19\times 10^{-7}$ 程度の相対誤差に収まります。 $2^{20}$ 回なら $…

…ることしかできない人かわいそう お近づきのやつ、今年なんだという気持ちになりました。もう大昔な気がしていたので。 ポインタ関連 ポインタ系データ構造を書きたいな B-tree を書きました 気まぐれアルゴリズム √w-bit の入力に対する定数時間 rank/select 区間平均値に関する典型の例 rank/select は簡潔データ構造の文脈で使おうとしていました。 簡潔はあまり人気ないですし、競プロ文脈に沿わないがちというのは承知していつつ、仲よくはなりたいんですよね。…

…ちになります。 ↓ かわいそうシリーズと呼んでいるもの ↓ rsk0315.hatenablog.com rsk0315.hatenablog.com まえがき 「誤差 WA」でツイート検索をすると、「WA が出たが誤差が原因か？」「たぶん誤差のせいだろう」「どういうときに落ちるのかわかんない」のようなふわっとした感覚の人がたくさん見つかりますね。 整数のオーバーフローなどは「とりあえず大きい値を入れて確かめてみる」みたいなやり方があるので、（オーバーフローという概念を知って…

「競プロライブラリにおける抽象化と言えばセグ木」みたいな風潮ができてから久しいですが、二分探索に関してそうした抽象化を意識している人はあまり多くない気がしています。 おきもち 整理・設計 実装 その他 実装に関して 中間値に関して お気持ちに関して めぐる式に関して ライブラリ・スニペットに関して 類題 所感 おわり おきもち たとえば、「ソートされた配列が欲しい」の気持ちのときにいちいちソートの実装を書かされるのはうれしくないはずです。 main 関数にいちいちソートの実装…

…まぐれアルゴリズム かわいそうシリーズ 振り返り DP 関連 数式がちゃがちゃ ブラックボックスのお勉強 浮動小数点数 今年買ったもの 来年に向けて 競プロ以外 うれしい おいしい かわいい かっこいい たのしい おわり 今年書いたもの カスの記事 【期間限定公開】絶対にバグらせないコツ教えます【競プロ er 必見】 $n²+2n+1$ 型の素数の列挙 カスの記事を上げることでしか消化できない欲求があります。 いま確認したところ、期間限定公開の方は web.archive.o…

詳しく解説編があるかはわかりません。 下記のような状況に対する別の策です。 rsk0315.hatenablog.com rsk0315.hatenablog.com 導入 今回は、浮動小数点数をそもそも使わない方針で考えます。 ある（自分で決める）上限 $b$ に対して、分母が $b$ 以下の（既約）分数の集合 $\Q_b$ を考えます*1。 すなわち、$\Q_b = \{p/q \mid 0\lt q\le b\}$ です。 さて、ある関数 $f\colon \R\to …

…ちゃ雨が降っていて、かわいそうな感じになりながら会場に向かいました。雨の中だとスマホが濡れちゃうのが嫌でスマホに道案内してもらいにくいので困ります。 「どこそこを通っていくと便利です」みたいな旨が書かれていましたが、変なことをして到着が遅れると嫌なので、濡れながらお外を歩きました。無事に着けたのでよかったです。 雨まじ？ PC こわれる— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2023年3月17日 こんなので笑ってしまった— かならい (@sugarknri) 20…

…るコンパイラちゃんもかわいそうです。 とはいえ、「ここのコードこうなってるよ」という警告の仕方だけされても（特に初心者が）困ってしまうのは当然かなという気もします。 コンパイラが気にしてくれている理由や、実際にバグっているコードでその警告が出る例などを以下に挙げるので、「たしかにそれは無視するとまずいかもしれないな」という気持ちになる助けになってくれたらうれしいです。 解説のコーナー -Wunused -Wmisleading-indentation -Wsign-compa…

…日記つけなくなったのかわいそう— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2022年7月23日 日記つけ始めてから 16 ヶ月くらい経つけど、日記つけなくなり始めてから 5 ヶ月くらい経った— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2022年7月23日 一年に一回しか行かないところに行った日の日記、「今年もちょっと迷った。正しい道順はなにでどうで...」みたいな説明が書かれてて笑っちゃった— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2022年7月23…

…んはよくバグらせる。かわいそう。 union-find は十分な回数クエリするとならし \(O(1)\) 時間になるので、そういう場合は BFS するのと比べて損せずに済む。 文字列アルゴリズム界隈や簡潔データ構造界隈、線形時間前処理かつ定数時間クエリじゃないと気が済まないみたいな印象がある。 yosupo.hatenablog.com CHT で仮定を置くと log が消えるやつ。こっちの方が有名そうな印象はある。 \(n\) 以下の逆元の列挙。最近あんまり話題にならないね…

えびちゃんかわいそう。 \(O(1)\) 階差分を取ると imos 法で書ける形になるような区間加算クエリ*1を一生バグらせました。 特に、DP をしながら on-the-fly で imos 法の遅延を解消していくやつを毎回バグらせている気がします。 こういうのはコンテストで出たときにその場でどうにかしようとすると頭が間に合わなくなるので、コンテストのない間に整理しておくのがよさそうです。 null-mn.hatenablog.com この手のセグ木を貼れば済むというのに後…

…こういうのを知っていると 何らかの文脈 で高速化が図れることもあるかも 何らかのことを思いついてうれしくなったり、積んでいたのを書けてうれしくなったり、バグらせている人を見てかわいそうになったりすると書きたくなってしまうみたいです。 A 問題など低難易度帯の解説は、ある程度成長した人の早解きテク用として有用な場合があるかもしれませんね。 自分用のリンク atcoder.jp 他の人も見れる用のページが無いのは若干不便な気もするものの、あってもうれしい局面が少ない気もしますね。

…い回しをする傾向がある気がします。 *2:初心者に限らないですが、主観で本質・非本質を決めつけたがる人はたくさんいる気がします。コーナーケースとか定数倍とか。冗談半分で言っているかも。 *3:さっきの例では、「探索範囲を狭めてよいのか？」「捨てた範囲以外に最適解が常にあるか？」というのを考えるのに相当します。 *4:現場猫のせいでネタにしか見えない。実際ネタだと思ってやっていた感はありますが。 *5:ジャッジがお粗末なサイトだとその限りではないでしょうが。 *6:かわいそう。

…い」と言っている人はかわいそうなので、解説をします。 名前について なんで「x 以上の最小値を得る関数」が lower_bound と呼ばれているのかわからん*1 まず、それを得る関数ではないです。イディオムとしてそう覚えてしまっているような人が多いため、こうなってしまう人が多い気はします。 実際には値ではなくイテレータを返すもので、「x と等価 (equivalent) な値がある区間の下限の位置」が返ってきます。ここでの equivalent というのは == とは違う概…

…読んでいる人がいたらかわいそうなことになりますが、まぁいいかなと思いました。 資料に「紙面の都合で、図はめちゃくちゃ縮小して載せたので、拡大して見てください」と書きつつ無を掲載して、ないものを探させようとしたら怒られそう— えびちゃん (@rsk0315_h4x) 2022年6月28日 改行位置には結構気をつけたつもりです。 小学生の頃の作文で培った "単語をうまく選んで次の行に 1 文字だけ入れて改段落して行数を稼ぐテク"、スライドでの改行位置を調整するときに役立ちがち— …

… が大きかったりしてかわいそうになる場合もあります。 atcoder.jp atcoder.jp こうしたケースで上記の方法が有効になりえます。 もちろん、オーバーフローに対して完全に思考停止したいなら多倍長整数を使うのがいいとは思いますが、その辺の見極めは各々に任せます。 思考停止で 1e18 にするよりは、よっぽどマシな気はします。 また、思考停止以外の文脈でも有用で、たとえば「ランダム文字列が二つあり、一致する共通接頭辞の長さを二分探索したい」といった状況で、「ランダム…

…sing u64 = unsigned long long; ... むかしの めちゃくちゃ後の人類、i16777216 とか i2147483648 とかで型名を宣言しなきゃいけなくなったらかわいそう— えびちゃん (@rsk0315_h4x) 2020年10月25日 *1:すごい処理系であれば別にこれに縛られはしないと思うのですが、とりあえず現在よくある環境たちについての話ということにします。 *2:グローバルでアンダースコアで始めるのは、リテラルなら許されるんですかね？

…対する「自分で場合分けを放棄して WA に逆ギレする人かわいそう」という記事や、「自分で定数倍の遅いコードを書いて TLE に逆ギレする人かわいそう」のような記事も書こうとしていました。「誤読して逆ギレする人かわいそう」という気持ちはありますが、記事に書くことはあまりないような気もします？ 人々が何らかの対象に逆ギレしているのを見て、お気持ち表明したくなったらまた書きます。 *1:え、もしかして実在しますか？ *2:未定義なので、もちろん、こうなることは保証されていませんが。

「バグったたすけてー」と言っている初心者の人のコードを見たとします。 バグを見つけてあげるのは（多くの場合）簡単ですが、それを伝えただけでは成長につながらないかなぁとも思います。 「こういうところをこうやって確認したよ」「そしたらこうなったので見つかったよ」みたいなことを教えてあげるといいと思ったのですが、毎回やると面倒なので、記事にまとめます。 あくまでえびちゃんの方法なので、他の人は違うことをしているかもしれません。 最近あまり他人のデバッグをしていないので、記憶と妄想で…

off-by-one エラーとか呼ばれるやつです。「1 ズレてたせいでこわれた」というやつですね。 バグらせやすい書き方をするのがよくないです。書き方を改めるのがよいでしょう。 ここでは、えびちゃんがよくやっている書き方を紹介しますが、別にこれが絶対というわけではないです。 「私の今の書き方が私にとっては世界一書きやすい。私はもう真理に達した」という人はすきにしてください。 バグらせにくい書き方をまだわかっていないとか、コンテスト中にそこでバグらせて不本意な結果になったとか、…

…です。おまけっぽさがかわいそう。 「要素に対する更新・区間の和」をするセグ木の逆で、「区間に対する作用・要素一つの取得」をするデータ構造です。 次に紹介する遅延セグ木を理解してから考える方がいいかもしれません。 可換な作用（区間に対して値を足すなど）であれば、難しい工夫はいらないので、上で述べたセグ木を理解すれば書けるとも思います。 遅延セグ木 「区間に対する作用・区間の和」の両方を処理できるデータ構造です（つよい！）。 定数倍はちょっと重めです。 元のセグ木では、親は子たち…

…一回も出されない人はかわいそうです。 各種類のメニューに関して、次の二つのことを前処理で求めておきたいです。 周期一回分（D 日間）で何回出されるか そのメニューを好む人が、それを何回食べられるかに対応する 周期一回分でそれが出されない期間がどのくらいあるか そのメニューを好む人が、それ以外を何回食べることになるかに対応する 出される間隔 x と与えられた L の割り算を、各間隔について合計して求める あとは、各人間に対して、「周期何回分を考慮すればいいか」「周期から溢れたと…

…うになっていました，かわいそう． B は正規表現でやるだけに見えたので Python でやりました． 一瞬ジャッジが遅くなったので，こどふぉで数回経験した「Python の正規表現で適当をすると TLE するやつ」を踏んじゃったかと思って焦ったけど無事 AC． えびちゃんはえらいので，提出言語を C++ に戻すのを忘れずにやりました． お姉ちゃんが入力読み忘れに気づいて直して AC．お姉ちゃん泣きそうになってた． D はゲームらしくて，お姉ちゃんと一緒に考察を進めます． 双子…