えびちゃんの日記

えびちゃん（競プロ）の日記です。

今年のえびちゃん 2021

自分語り記事です。

うっかりし直しました。

今年お勉強したもの

数学関連のものをいくつか学んだり、昔わかった気になったものを学び直したりしました。

  • ACL math
    • floor sum は去年だけど
      • ACL にマージされたのは今年
  • mod tetration
    • \( (a\uparrow\uparrow b) \bmod n = \underbrace{a^{(a^{(\cdots ^a)})}}_{b\text{ many}} \bmod n\)
    • 実装が悪いと \( (2\uparrow\uparrow 3)\bmod 32 = 16\) を \(0\) としてしまう
  • mod Ackermann
    • \(A(a, b) \bmod n\)
  • 離散対数
    • \(a^x = b\pmod{n}\) なる最小の \(x\ge 0\)。なければないと言う
    • 特に、法が合成数の場合
  • 素数の数え上げ
    • \(\pi(n)\)
    • \(n\) 以下の素数の個数を \(O(n^{3/4}/\log(n))\) 時間で数える
  • \(n^2+1\) 型素数篩
    • 特定の状況で必要になるやつ
    • \(n^2+1\) 型の整数の素数判定をできる
    • \(n^2+2n+1\) 型素数列挙というギャグもありました
  • Boyer–Moore majority algorithm
    • 過半数を占める要素を deterministic \(O(n)\) 時間で探す
      • 「過半数を占めているとすればこれ！」というのを探す
      • 実際に占めているかの判定は、再度走査してそれの個数を数えれば可能
  • SA-IS
    • 接尾辞配列を \(O(n)\) 時間で構築する
      • 入力アルファベットのサイズが \(O(n)\) だったりするのを仮定してそうだけど
  • van Emde Boas tree
    • いわゆる lower_bound みたいなのと挿入・削除を \(O(\log(\log(u)))\) 時間でできる
    • この記事は講義動画へのリンクがあるのだけが有用みたいなとこある
  • range LIS query
    • これから大晦日までの間にやるつもり
  • DM 分解
    • これは来年ということで...
  • ACL mcf slope や、それを使う系の問題も来年やります...
  • yosupo judge の問題もうめます...

他にも、全方位木 DP や遅延セグ木を実装したりしました。抽象化に納得がいかなくてもやもやしたりしています。

yosupo judge に hack case の PR を送ったり、ACL (AtCoder Library) に改善の PR を送ったりしてマージされたりしました。 floor sum に関しては、 yosupo さんが 解説 を書いてくださったりもしました。うれしい。

あ、計算量の記事を書いたりもしましたね。

あと、ふと思ったことを言ったら熨斗袋大先生がいい感じにしてくれたのも実はうれしかったです。

Z shell の man を読むのも始めたのですが、ここ数ヶ月は放置してしまっています。

社会堕ち？

えびちゃんも就職しました。陽には就職先を言っていませんが、適切にストーキングすれば公開情報から辿れるようになっています。 あまり大々的には言わない方がいろいろ無難かなと思っているので、見つけてもツイートしたりはしないでもらえるとうれしい気がします。

職場では、特に競プロをしている人やえびちゃんをフォローしている人が「えびちゃん」と呼んでくれたりしてうれしいです。

環境関連とか

すっかり C++ を書く機会が減りました。整備していないが ACL にはあるライブラリを使いたいときに書くくらいになりました。 ほとんど Rust ばかり書いています。

それから先月あたりに SKK を使い始めてしまい、SKK なしでの入力がおぼつかないようになってしまいました。

カーソル上の識別子の形式を変換するのを導入して、特定の場面で快適になったりしました。

キーバインド 変換後の形式
C-c c lowerCamelCase
C-c C UpperCamelCase
C-c - kebab-case
C-c _ snake_case
C-c = SCREAMING_SNAKE_CASE

C-c = はあまり気に入っていません。

ねこちゃん

フォロワーにねこ耳自撮りを送ったり送ってもらったりしました。たすかります。

その他

PAST がそろそろ 2 年経つのでまた受け直したりしました。

Advent of Code 2021 というのを解いたりしていました。数学系の考察は少なくて、実装がんばりましょう系が多めな気がします。 実装が苦手な人はやってみるといいかもしれません。

えびちゃんのぬいを最近また買って、かわいがっています。

書き忘れがまだあるかもしれません。

おわり

来年もよろしくおねがいします。

f:id:rsk0315:20211226165033p:plain