これはなに

rsk0315.hatenablog.com

これです。

まとめ

My Editorial - AtCoder

こうです。

あれ？

わたしがこれまでに書いた 8 本のユーザ解説について、お話しします(?)
— ぽかーん懐古DP@259家(桃音モモ) (@259_Momone) 2022年6月18日

今年の6月に既出らしいです。

本編

Xor Distances
- 初ユーザ解説です。この問題はユーザ解説も多く、この内容はほとんど公式解説のマイナーチェンジと言っていいかも？
- 発想のでどころは違うので、これを読むことで腑に落ちの人もいるかもしれません。
kcal
- 浮動小数点数演算のお気持ち表明解説第一弾です。
- 浮動小数点数の演算にかかる誤差は(変なことをしなければ)十分納得のいく範疇に収まってくれます。
- みなさんも浮動小数点数の誤差を飼い慣らしましょう(わたしは飼い慣らせていますか？いいえ)
- 「想定解答との絶対誤差または相対誤差」、なくなるといいなあと思っています。
Colorful Candies 2
- Polynomial Taylor Shift の紹介/解説がメインのユーザ解説です。
- 形式的べき級数のちょっと非自明な操作シリーズの中では比較的シンプルな畳み込みなので簡単な部類になるかもしれません。その分使える範囲は広くないかも？
Grand Garden
- 昔の問題のユーザ解説シリーズ？公式解説より計算量がいいシリーズでもあります。
- 今のABCで出たらこっちの制約になりそうじゃないですか？ならないかも
1111gal password
- 公式解説より計算量がいいシリーズのユーザ解説です。
- ある種のDPは行列累乗で解けるというの、出てくる概念のわりに実感としてはとても有名な話(初心者向けにもフィボナッチ数の話ができるから？)
- 現実のほうでサークルの人からせっつかれて書いた解説なので、おてほん実装(?)なしの簡易解説になっています。
Range Count Query
- 列を乗せるセグメント木の紹介?解説?をしたユーザ解説です。今回は実際に乗せているのは多重集合でした。
- コンテスト中には公式解説の方針は一切思い浮かんでおらず、「いまどきの AtCoder でもセグ木を自分で実装する回があるんですねえ」なんて思っていました。
- 公式解説より計算量がわるいシリーズ(！)でもあります。
Polynomial division
- 公式解説より実装が楽になるシリーズです。多倍長整数を使います。
- 係数と比べて絶対値が十分大きい整数 $x$ を代入することで多項式と対応させることができます。
- 多項式環 $K\lbrack x\rbrack$ から $K$ への準同型と思う見方もあるかもしれません。だから、 $a$ と $ab$ から $b$ を復元する操作も簡単にできるんですね。
- わたしが以前聞いたちょっとしたパズルを紹介しておきます。
  - 自然数係数多項式 $P(x)$ を当ててください。あなたは事前に自然数 $K$ を宣言して、自然数 $X$ を与えて自然数 $P(X)$ を得ることを $K$ 回まで行うことができます。
Together Square
- 公式解説より計算量がいいシリーズのユーザ解説です。
- 速いのに導出は平易でよくないですか？気に入っています。
- 書いた瞬間あたりは最速だったんですけど、そのあとすぐに atcoder.jp で $\tilde{O}(N^{5/11})$ について言及されてしまいましたぽか。
連結成分
- noshi91.hatenablog.com の紹介/解説がメインのユーザ解説です。
- 公式解説とどちらが速いかはケースによる感じだと思います。公式解説は出力が線形で、こちらはマージが高速です。
方程式
- PAST ユーザ解説シリーズです。
- 微分可能なのでニュートン法が使えます。ニュートン砲！
- 誤差評価についてはなあなあです。助力を求めているところもあります？
Erase and Rotate
- 公式解説の行間を埋めるシリーズのユーザ解説です。
- 公式解説で「区間の左端・右端の位置に単調性があるためスライド最小値を用いて $O(N)$ に改善できます。」とあるところを埋めてみました。
- おてほん実装(?)のコーディングスタイルや癖がぽかいこスタイルになっています。これ以前はなるべく癖を消すようにしていましたけど、どちらがお好みですか？
Intersection 2
- 浮動小数点数演算のお気持ち表明解説第二弾です。長いです。巨大です。執念です。キモいです。
- 全部読んだ方、いらっしゃいますか？感想をお待ちしています。
- 誤差の理論的な評価、ひたすらひたすら格闘して出てくる結果が「じゅうぶん小さいです。」なので、疲れるかも誰もしていない理由がわかった気がします？そもそもできる人がそこまで多くないですか？
- 「想定解答との絶対誤差または相対誤差」は、なくなるといいなあと思っています。