今年もやってみます
今年お勉強したもの
実装したものや記事を書いたものも含めます。
- 並列二分探索で k-最小値
- セグ木で priority queue + なにか
- range LIS query
- $\angled{O(n\log(n)^2), O(\log(n))}$、むずかしい。
- オフラインの線形時間 LCA
- 浮動小数点数の二分探索をビット列で解釈してやるやつ
- CHT 実装し直し
- 遅延セグ木 考え直し
- $α(m, n)$ について
- 浮動小数点数のバグ関連 罠はもっとありそう
- 素数の数え上げなど
- ならし計算量お気持ち表明
- 区間更新データ構造なにか
- お気持ち表明記事
- functional graph のやつ
- bonus 制約でユーザ解説を書いた
- リアクティブ問題用のデバッグ環境の話
- ビット並列化
- 競プロ界隈だと比較的ニッチそう
- $\{0, 1\}^w$ に対する転倒数
- $O(\log(w)^2)$ 時間とか
- 線形時間アルゴリズムがあるのに log がついているものばかり有名なやつ
- Montgomery 乗算
- output-sensitive な LCS
今年なにもできていない気がしていたんですが、実は結構書いていたみたいです。月単位で見れば一つ以上記事を書いていそうです。
あと、数年前の競プロ始めたてくらいの年に見て以降何度か挫折していた Hu–Tucker algorithm をお勉強したり、どこかで見て挫折していた LARSCH algorithm をお勉強したりしました。本当は LARSCH の解説をねこねこ勉強ぱーてぃでやる予定だったのですが、全然間に合いませんでした。
たまに「えびちゃんさんが持ってくるニッチめなアルゴリズムネタってどこから仕入れているんですか?」と聞かれることがあった気がするんですが、えびちゃんも覚えていません。どこから仕入れているんでしょう。普通に蟻本とかあるある競プロ本とかでお勉強していたら線形 RMQ とかすら目に入らなさそうですよね。
去年の記事で「来年やります...」と言っていたものをあまりしていませんが、気分屋さんということで許してほしいです。最近は FPS での数え上げとかのお勉強をしています。
そういえば LuaLaTeX を導入して環境を整えつつあります。先日の LCS の記事内の画像も LuaLaTeX+TikZ で生成したものです。TeX のドキュメント中で「DP などをして得られるテーブルを出力したい」のようなときに「別の言語で書いたものをコピペする」「TeX 言語 🤮 で実装する」などをせずに書けるのがうれしいです。Lua は(競プロで慣れている言語と比べると)多少癖がありますが、それでも許容できないほどではない気がしています。
その他書いたもの
数年前に書いたのの書き直しではあるのですが、こういう感じのを書きました。もっとこういう感じのが気にされてもいいよねと思っています。みんな不便に思うでしょ。
なんかこんなの作ってたんだよねhttps://t.co/SoZ5S8Ud6z pic.twitter.com/yvPSdVLwbj
— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2022年5月1日
こういうの も書きました。WebAssembly というのを使っていて、Rust の競プロライブラリを Web サイトに流用できたのがよかったです。動画中ではマウス操作ですが、キー操作にも対応しています。
前に言ってた passwordle です pic.twitter.com/i1ISHCh2Uo
— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2022年2月10日
passwordle はそこそこ伸びました。もっとバカみたいに伸びた記憶があったのですが、見返したら数はそこまででもありませんでした。ただ、海外の人の反応が多めだったり、Gigazine で 記事 になっていたりしたので普段の伸びとは差別化が図れている気もします。
エスパーするやつ はおふざけでした。なんですかこれは。
以下は去年だったらしいですが、まとめて紹介しちゃいます。
- 目を鍛えるやつ
- 有名な人がトークンとかを雑にぐちゃっと塗って画像ツイートしていてヒエッってなったので作った
- ぐるぐるするやつ
- たのしそうなので作った
- マウス移動の際に座標を取得して、直近 3 点に対して CCW みたいな感じで方向を計算している
ぐるぐるするやつは、通常のマウス・パッド操作と違い、無限長のスペース(あるいは指を浮かせて戻す行為)を必要としないので、いい感じに応用できると面白そうかもしれません。
書きかけですが、Z shell のメモも書いていました。
開発環境関連とか
AZIK
日本語入力に SKK を使っていたのですが、さらに AZIK を取り入れてみました。 SKK は変換機能に関するレイヤーが主で、AZIK は変換機能に与える入力の段階のレイヤーなので、一応別物の話ではあります。 SKK の導入は数日くらいで慣れたのですが、AZIK は慣れるまでに半月くらいかかりました。かなりストレスでしたが今となっては快適です。
AZIK の主機能に母音拡張というものがあり、たとえば子音の後の z
が ann
の役割をします。
たとえば、「参加」と書くのに Sanka
ではなく Szka
と入力することができます(先頭が大文字なのは SKK 側の事情ですね)。
z
は QWERTY 配列で a
の下に位置するキーですが、同様に i
u
e
o
の下にある k
j
d
l
は inn
unn
enn
onn
の役割を果たします。
これ以外にもいろいろあります。特に SKK では「(たとえば)sz
と入力したときに さん
が入力されるようにする」のようなことを設定ファイルでカスタマイズできるので、こうした拡張を柔軟に試しやすいです。デフォルトのものも含みますが、以下のような感じで使っています。.
は任意の子音を表します。対応する母音と QWERTY 配列の位置関係で近いものが拡張キーに割り当てられています。
キー入力 | 相当する列 |
---|---|
.z |
.ann |
.s |
.ai |
.k |
.inn |
.j |
.unn |
.h |
.uu |
.d |
.enn |
.w |
.ei |
.l |
.onn |
.p |
.ou |
こうした拡張のせいで、1 キーの打ち間違いで 3 文字くらい入力されてしまい、backspace の回数が直感以上に増えるのが最初は大変ストレスでした。もう慣れました。
たとえば「赤子」と書こうとして手がすべって Akkago
と書くと「あきんあご」のようになってしまい、たくさん消す必要があるということですね。
他にも AZIK のデフォルト動作を試す中で、x
がシャ行に対応する子音(xa
で しゃ
など)にするのが比較的快適ということに気づきました。
そのため、ァ行に x
が使えなくなり、l
を使おうとなりましたが、SKK の半角英数モードの l
と衝突します。
元々 l
があまり気に入っていなかったため、半角英数モードを c
で行うことにしました。この変更はすぐに慣れ、結構快適です。
さて、AZIK では上記の事情から、たとえば「パック」と入力するときに pakku
と打つと「ぱきんう」になってしまいます。
そこで、適当なキーに「っ」を逃がす必要があるのですが、;
を割り当ててみました。上記の例では pa;ku
のようになりますが、同じキーを連続で押さないことにより「キーを離す」がボトルネックにならないのが少しうれしいですね。
他の例として、「あんこ」と入力するときに普通 anko
と打ちますが、これも AZIK では「あにんお」のようになってしまいます(うれしくない)。
annko
an'ko
のようにする方法がありますが、AZIK のデフォルトでは q
を「ん」に当てて aqko
のようにするようでした。
SKK ではカナ変換に q
を使うため、それを変えるのはうれしくありませんでした。そこで \
を割り当てることにしました。a\ko
のように打ちます。
こうした経緯はありますが、「っ」「ん」が ;
\
の 1 キーだけで出せるのは意外と快適です。
また、zk
で ↑
などの矢印入力する機能(これは多くの IME にもあるが、元々は SKK(よりも前の IME)から存在した機能らしい)を使おうとすると「ぞん」のようになってしまい、かなしいです。
これは、zk
の代わりに lk
にすることで回避しました。母音拡張で期待される「ぃん」が母音の後ろには来ず、たとえば「フーディン」などは hu-dhk
のように入力するのが自然*1なため lk
をそうした用途には当てないであろうためです。
AZIK の紹介が長くなってしまいました。
プログラミング側
Rust では rustfmt が自動で走るようにしていましたが、C++ や Python ではそうしたツールを入れていなかったため、「それらの言語のときは手でフォーマットを整える必要がある」のようになってしまっていました。さすがに愚かすぎるので、clang-format と black を導入しました。多少気に食わないときもありますが、正直どうでもよくなってきました。
あと、元日からやっていたらしいのですが、シェルからファイルを開くことが多いのに毎回 emacs ...
と書くのが面倒だったため、C-x C-f
で開けるようにしました。less ...
用の C-x C-r
もあります。とても快適です。
Zsh からファイルを開くのを効率化したかったので(補完もちゃんと効く・打ちかけのコマンドがあったときにもうれしい) pic.twitter.com/om6GESOlRo
— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2022年1月1日
今年あったこと
TTPC がありました。ばたばたしているうちに参加記を書きそこねてしまったんですが、ここで少し触れて満足ということにします。
TTPC 2022 におじゃましています、お疲れさまでした pic.twitter.com/uCIG1l4UJI
— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2022年11月5日
connpass の参加者欄にはいないのになぜという感じですが、所属をよく見ると察するかもしれません。 たまたま自分の所属しているところ*2でオンサイトコンテストが開かれると、特別枠で参加できる可能性が高まるらしいです。
えびちゃんが TTPC 2022 のことを知ったのは一般公開のときだったので、「オンサイト会場に見慣れた住所が書かれてるじゃん?、?!?」という感想でした。
びーとくんと久々に会えたのがうれしかったです。
完全に忘れていたんですが、思い出したので追記です。 GCJ や MHC でいい感じの成績を取り、T シャツを得ることができたのでうれしかったです。
買ったものとか
実体がある
これな〜んだ? pic.twitter.com/UVqiYmRCpY
— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2022年3月9日
iPad Pro や iPhone 13 mini を買ったりしました。えびちゃんは (PRODUCT)RED の色が好きなんですよね。
あとまだ写真は載せていないのですが、ツイで見かけた干支のキメラのマスコットを衝動買いしました。
仕様なのかわかりませんが、四本の足の先が同一平面上になく、ややバランスが悪くて頼りないです。商品紹介ページの写真を見た感じだと仕様ではなさそうですね。 この子も去年の子(冒頭リンクの 2021 の記事参照)同様にヘアゴムを掛ける場所として適しています。しっぽの蛇のところがおすすめです。
実体がない
YouTube のプレミアムや Slack の Pro subscription を使ってみています。どうせ個人で使っているものなので、無料であることにこだわる必要もないのかなとなってきました。以下のことも動機の一つです。
YouTube の広告、スキップが表示されてからどれだけ早くスキップできるかというところにゲーム性があるので、スキップできないタイプの広告がたくさん出ると「金払って消すか」となる
— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2022年8月23日
あと、PayPay などの支払いサービス(デビットカードとかも含む)を導入しました。 現金でがんばるの、oj とかを導入せずに手作業でサンプルを試すのに似ています。 前よりも浪費が簡単になった気もします。嘘喰いとかを一括で買ってしまいました。
その他
毎日忙しくなって「あのとき何してたんだろう」とか思い出せなくなるのやだなーって思って日記つけ始めたはずなのに、忙しくて日記つけなくなったのかわいそう
— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2022年7月23日
日記つけ始めてから 16 ヶ月くらい経つけど、日記つけなくなり始めてから 5 ヶ月くらい経った
— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2022年7月23日
一年に一回しか行かないところに行った日の日記、「今年もちょっと迷った。正しい道順はなにでどうで...」みたいな説明が書かれてて笑っちゃった
— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2022年7月23日
来年はまた日記をつける癖を取り戻してみようかなと思ったりもしています。
おいしい
おいちかった(れあちゃトッピング) pic.twitter.com/buVRzvOigZ
— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2022年8月28日
れあちゃ pic.twitter.com/c6yskf18lC
— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2022年10月23日
レアチャーシューおいしいですね。最近はもう売っていなくてかなしいです。
おわり
意外と書けることが多くてびっくりしました。来年もえびちゃんらしくがんばっていきたいです。よろしくおねがいします。