えびちゃんの日記

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

えびちゃんの AtCoder ユーザ解説まとめ

振り返りたくなったのでついでに書きます。

新しくなる順。

  • J - 長い長い文字列/Long Long String
    • ほぼ愚直にシミュレートするのが、解析すると妥当な計算量とわかって面白かったので書いた
    • \(x \bmod y\) が \(x\) の半分になるので高々 \(\log(x)\) 回で \(1\) になる
  • Prefix K-th Max
    • 区間 \(k\)-最小値が並列二分探索でできるのに気づいて、面白い気がしたので書いた
    • ついでに WM の宣伝
  • Divisible Substring
    • 公式解説では後ろから見る方針が書かれていたが、前からで解けたので書いた
    • 内容自体は、変数分離のよくあるやつ
  • Sequence Query
    • WM の宣伝
  • Yamanote Line Game
    • Rust の proconioインタラクティブで使って変にしている人を複数見たので書いた
    • コード例も載せたので、自分もここからコピペして使うようになった
  • Inverse of Permutation
    • おふざけではあるが、何らかの気づきを得る人がいるかもしれないと思って書いた
    • SA-IS の base case が、入力が distinct(逆順列を返す)のときであるやつすき
  • LCS
    • LCS がよくある DP 以外で解けるのが面白かったので書いた
    • 古い論文で \(O(n\log(n)+\delta^2)\) 時間が述べられていたが、SA-IS + LCPA の線形時間構築 + 線形 RMQ で \(O(n+\delta^2)\) 時間になった
  • Cutting Woods
    • decremental neighbor query を使えてうれしかったので書いた
    • \(n = 10^9\) bits くらいなら \(n/w\) words くらい持っても平気なやつすき
  • Together Square
    • 線形篩を使えてうれしかったから書いた
    • ぽかいこちゃんが \(\Theta(\sqrt{N})\) 時間の 解説 を書いてくれた
  • Circumferences
    • union-find に対して、全頂点ペアぶんだけ \(\Theta(n^2)\) 回クエリすれば \(\alpha(n)\) がつかなくなる(解析側の問題)のすきなので書いた
    • BFS でやるのと比べて最悪時のオーダーで損していないということ
  • Intersection
    • ビット演算で思考停止できて実装も軽めだったので書いた
  • Long Bricks(★5)
    • 区間代入クエリをしたいが、遅延セグ木もない tree set もないみたいな状況で実装を比較的軽めにやりたいみたいな話があった
    • でも遅延セグ木を勉強すればいいという話もある
  • Slimes
    • 初心者の頃に名前は知っていて挫折していた Hu–Tucker algorithm を書けたので紹介を書いた
    • 中身を書けていなくてすみません
  • Frog 3
    • 黄色になった後くらいに話には聞いて挫折していた LARSCH algorithm を書けたので紹介を書いた
    • 中身はそのうち書きたいです
  • Moving Piece
    • 公式解説にある bonus に加えて、順列の制約も外せてうれしかったので書いた
    • functional graph にモノイドを載せるところまではすぐ思いついたのに、一日くらいダブリングが頭から抜けていて失格だった
      • 問題固有の考察に引っ張られていたりしたのもよくなかった
  • Split?
    • ビット演算で処理できてうれしいと解説を書きがちになってしまう
    • A 問題にこういう解説を書くとノイズになってしまうかもしれません?
  • Index × A(Continuous ver.)
    • 公式解説と雰囲気が違ったのと、CHT 入門のお気に入り問題の式変形だったので書いた
    • 添字をちゃんと考えましょうみたいな記事 の直後だったのにフォロヮが添字を適当にやっていたので書きたくなってしまった
  • Submask
    • pdep とか pext みたいな CPU 命令が有名でない気がしたので書いてみてしまった
    • 競プロにおいては、こういうのをやるより学ぶべきことがある感はあるが、そう言っていると一生学ばない系な気もする
    • こういうのを知っていると 何らかの文脈 で高速化が図れることもあるかも

何らかのことを思いついてうれしくなったり、積んでいたのを書けてうれしくなったり、バグらせている人を見てかわいそうになったりすると書きたくなってしまうみたいです。 A 問題など低難易度帯の解説は、ある程度成長した人の早解きテク用として有用な場合があるかもしれませんね。

自分用のリンク

atcoder.jp

他の人も見れる用のページが無いのは若干不便な気もするものの、あってもうれしい局面が少ない気もしますね。