えびちゃんの日記

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

Toyota Programming Contest 2023 Spring Final など参加記

参加してきました。

「参加記に載せる用の画像を載せておくと、参加記に載せるのが楽になる」というのを思い出したので撮っていました。

予選 B で G を解いていい感じの順位になってしまい、参加する運びとなりました。 今までの AtCoder 主催のオンサイトは、DDCC や CodeFlyer などで就活優遇枠での参加だったり、学生コンや最強コンなどでの決勝イベントのみの参加だったりは経験があるのですが、一般枠のような形での通過は初めてだったのでうれしかったです。欲を言えば予選 A で通過したら文句なしでしたが、仕方ないですね。

起床

5 時半に起きました。諸々準備をしたりごろごろしたりしていたら、わりとギリギリの時間になっていました。

Mac の充電器を忘れて一旦取りに帰りました（一敗）（結局使いませんでした）。 「お飲み物はご持参ください」と書かれていたので前日に買っておいた飲み物を、冷蔵庫でお留守番させていることに電車に乗ってから気づきました（さらにもう一敗）（支給されました（monkukui に進呈しました））。

めちゃ雨が降っていて、かわいそうな感じになりながら会場に向かいました。雨の中だとスマホが濡れちゃうのが嫌でスマホに道案内してもらいにくいので困ります。 「どこそこを通っていくと便利です」みたいな旨が書かれていましたが、変なことをして到着が遅れると嫌なので、濡れながらお外を歩きました。無事に着けたのでよかったです。

PC はこわれませんでした。

Toyota Programming Contest 2023 Spring Final

受付

雨が降っていたりしてわたわたしているうちに入ってしまったので、入口付近の写真を撮り損ねてしまったのが心残りです。 受付の人に対して人見知りを発揮して（たぶん）困らせてしまいました、すいません。

番号が覚えやすくて助かります。

ユーザ名はユーザ ID と同じでよかったらしいです。

なんかギャグで言っているのかと認識してしまったんですよね。

学生コンとか AtCoder がやっているオンサイトではこういう形式だと思ったので、自分で名札を作っていったんですが、よかったかな〜と思います。 特に昔から参加している人は無限回言っているシリーズなんですが、名札は両面に名前を書いておくと、裏返りに対してロバストになるのでおすすめです。

着席

座席が全席指定のオンサイトって珍しくないですか？と思ったんですが、codeFlyer も全席指定だったのを思い出しました。codeFlyer のときは本番よりも前の日にメールで座席表が送られてきていた記憶があります。

（えびちゃん codeFlyer すきすぎない？ レート色背景に白文字のシンプルな名札とか、コンテスト T シャツとか、諸々印象に残っています。上記の名札の裏面もこれを真似したものです。）

たぶきゅんを見つけてこっそりにまにましていたら、あっさりバレました。

コンテスト開始前

オンサイトコンテストといえば、公式 F5 アタックだと思っていて、人々が一斉に F5 なり ⌘R なりを押して負荷を掛けて大丈夫か調べるやつがあったと記憶しているんですが、特になくぬるっと始まりました。そういうのもありかもしれません。

コンテスト

atcoder.jp

A からむずかしいよ〜、正直太陽*1まであるかと思っていました。 とりあえず左上の値 $x$ と高さ $A$ と幅 $B$ を固定すると、その矩形領域の和は $f(x, A, B)$ の形で求まるわけですが、$f(x, A, B) = V$ がいい感じに $x$ について解けるので、$(A, B)$ の全探索でいけるわけですね。 長方形のサイズが求まれば左上の値は一意になるという感じで、たしかにな〜という感じでした。

バグらせたりしていてつらかったので、カスの clar を投げていました。 「はい。3000/01/01 00:00:00 になってから言及してください。」のような返答が来たらどうするつもりだったんでしょう。

B は、なんか頭がこわれていて「$p_i$ で貪欲とかではないですか」と言われてサンプル二つ通ったんですが、三つ目で落ちてくれて助かったです。 とはいえ、それっぽい式を立てて貪欲するしかないのでは感があり、そうしました。 問題 $i$ の直後に問題 $j$ があるとき、$j$ さえ正解すればそれ以降での期待値の寄与には $i$, $j$ どちらが先かは影響しないので、$i$, $j$ を入れ替えたいなら勝手にやっていいみたいなことを考えて、それらの期待値の大小を比較しました。

C は、$R-L \le 10^6$ と書いてあるので区間篩です（安直パターンマッチ）。 「AtCoder で区間篩が出るなんて珍しいな」「企業コン本戦ならそういうこともあるだろ」のような無意味脳内会議をしました。

めちゃくちゃ TLE・RE が出ていました。$\sqrt{R} \le 10^9$ なので区間篩だとしんどいんですよね。制約を見るのが重要らしいです。

なんか結局約数を列挙できるとうれしいんだけどな〜となり、高速素因数分解を貼ってみたりなんか諸々をがちゃがちゃしたんですが、TL にぎりぎり間に合わず、なんか適当に枝刈りをすると通りました。正当性示していません。すみません。

順位表凍結後にようやく通したんですが、凍結後の AC 経験があまりない（初めてまである）ので、それに関してはうれしかったです。 とはいえバカみたいにバグらせてようやく通す感じではなく、凍結直前から考察を始めた問題を凍結後に通すみたいなことをしたいです。精進しなきゃなんですよね。

そんなこんなをしているうちに終わりです。D はなんかいろいろ考えようとしたんですがうまくいかずじまいでした。

コンテスト終わり

お弁当の入っている箱を得ました。おいしいお弁当でした。

オンサイトと言えばねこ耳だと思っているんですが、えびちゃんだけかもしれません。えびちゃんもそう思ってるかと聞かれると正直怪しいです。

chokudai さん以外や chokudai さんの話を聞いたりしました。

これってどうなんでしょうね。なんかアルゴ*2で出てもいいような気もするし、出るとびっくりという気もします。

諸々コーナー

rng さんからの挑戦状を見ました。 前半は茶番という感じでしたが、後半は強い人が手計算で多少（凡人にとっては）大きめのサンプルをぱぱーっと解いて早押しするコーナーをやっていて、おもしろかったです。レジェンドの人たちが茶番をしているのを見るのもおもしろいですね。

ただ、会場が広いせいもあって、スクリーンの内容が後方からだと見にくかったのは多少うれしくなかったかもしれません。

雑談など

いつもの勢とおしゃべりして、あまりいつものではない勢と少しだけおしゃべりしました。 いつもの勢は元気そうなのを確認すれば満足で、特に話すことはないんですよね（でもそれが大事なのかもしれません）。

あと老人なので、ほとんどの人を知りませんでした。COVID-19 が始まってオンサイトがあまりなくなって以降に競プロを始めた人もたくさんオンサイトに来ていたみたいです。

ぬい交流は大事（？）。とりあえず、ぬいを持ってくるといい可能性があります。ただ汚れたりする可能性がなくもないので、一番大事な子は持ってこない方が吉な場合もあるかもしれません。

りきぽんちゃん。

てあちゃん。

たくさんちゃん。

そういえばえびちゃんが最初に買ったぬいは、オンサイトイベント前の時間つぶしでふらっと立ち寄ったお店に売っていたえびふらいのしっぽちゃんでした。 それが実質的に初めてのえびふらいのしっぽちゃんとの出会いなので、えびふらいのしっぽちゃんにハマるきっかけとして AtCoder オンサイトが寄与していると言っても過言ではありませんね。

あ、えびふらいのしっぽちゃんと関わりを持つ前から「えびちゃん」を名乗っていました（豆知識？）。

表彰式

maspy さんが「ますぴーさん」と呼ばれてちょっとざわついている人がいました。

これ知らない人も結構いそうですよね。とはいえ本人もあまり呼ばれに関しては気にしていなさそうなので、まぁ外野がとやかく言うのもアレかな〜と思いつつ、「えびちゃんの方が maspy さんに詳しいが？」と内心思ったり思わなかったりしています。

飾らない感じの優勝コメントすきです。

懇親会

おしゃべりしたりおしゃべり以外をしたりしました。

競プロフレンズさんや segtree さんと話したり、t33f さんと話したりなど、いつもの勢以外ともお話できてよかった気がします。ツイ的にはほぼいつもの勢という気もします。 らずちゃんと初めて話せたのもよかったです*3。

記事見てますーとか、お気持ち表明見てますーとか言ってもらえたので調子に乗っていました。 「最近どの記事読みましたか？」などと聞いたんですが、お世辞炙り出しみたいで社会性無だったかもしれません（？）。

などが挙がりました。bitset のやつはもっとちゃんと整理した方がいいのかな？という感じもしています。word RAM とかの話自体、競プロ界隈ではあまり浸透していなさそうです。そもそも計算量自体ノリでやりがちな界隈ですからね（とはいえ昔ほどではない気もします）。 あと、おふざけ枠として 夢地区 の話が出たのもうれしかったです。記事に起こそうとした時点で狂っており、おふざけだなぁという感じです。

お開きくらいの頃に話したさんせんさんが酔っていて面白かったです。好感度爆上がりですね。

イベントおわり

Summer もよろしくお願いします。

競プロ er 大宴会 2023 春

connpass.com

えいやーという感じで申し込んで、行くことになりました。 決勝イベントとかぶっていて裏でやっているイベントで参加不可能なのかな？と勝手に思い込んでいたのですが、そんなことはなかったみたいでした。 実際、決勝イベント後にすぐ帰宅だとさみしい感じになっていたかもしれません。

（元）北大勢たちで集まって、「誰々は会場までの行き方を知っているだろう」とみんな言っていたのがおもしろかったです。

会

なんかいろいろ食べたり話したりしました。正直、飲みの席で笑った話は文脈や雰囲気ありきなので、参加記に書いてもあまり面白みの再現性がないんですよね*4。

あとぬい交流。いたちゃちゃん。

その他

実は後ろの Mac も衝動買いらしいです。オンサイトに持っていく用という建前でした。

おわり

ねむいです。旬を逃すと書きにくくなりそうなのでばーっと書きましたが、諸々抜けているかもしれません。

*1:たぶん太陽という表現は老人にしか通じないんですね。0 完という意味です。

*2:という分類はあまり好きではないのですが、いわゆるということで。

*3:らずちゃんと話したのは懇親会ではなく雑談タイムだった気がします。でも多くの人にとってはその情報は大事ではない気もします。

*4:カイリキーの利き腕って右半分なのか右の片方なのかどっち？ 後者だとしたら右腕一本と左腕三本あるみたいで不便じゃない？ とかそういう話です。

コンパイラの警告を無視してバグらせる人かわいそう

無視されるコンパイラちゃんもかわいそうです。

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

解説のコーナー

未定義動作の可能性があるのを気にして警告してくれているケースや、そういうわけではないがよくあるバグの原因を警告してくれているケースがあります。ここで挙げる大半は後者です。

GCC では、コンパイル時に -Wall などのオプションをつけることで大抵の警告が有効になります。-Wextra をつけないと有効にならない警告もあります。 -Wextra をつけていても有効にならない警告もあります。たとえば -Wfloat-equal や -Wdouble-promotion というのがあるみたいです。

以下を見るといいかもしれません。

gcc.gnu.org

警告は個別に -Wunused-parameter のように追加したり、-Wno-unused-parameter のように除外することもできます。

他のコンパイラを使っている人は別途調べてみるといいかもしれません。 とにかく、（やばいコードを書いても）警告が出ない環境でコードを書くのはおすすめしません。

-Wunused

-Wunused-parameter や -Wunused-variable などいくつか種類がありますが、宣言・定義されたのに使われていないものに対する警告です。 「使ってないものが残ってたって別によくない？」と言う人がいるかもしれないのですが、使うべきものを使い漏らすことはまぁよくあると思います。

int dot(int x11, int x12, int x21, int x22) {
    return x11 * x12 + x12 * 22;
    // 実際に意図されていたのは x11 * x21 + x12 * x22 などのはず。
    // x21 が x12 になっているのに加え、x22 も 22 と typo している。
}

使わなくてよくなった変数は消す（せめてコメントアウト）方が、unused 系の警告を無視する癖をつけないようにできてよいと思います。

-Wmisleading-indentation

実際の挙動とは異なるインデントに対する警告です。 「別にそんなのよくない？」という人が目に見えるのですが、実際にあった脆弱性から導入された 警告です。

    if ((err = SSLHashSHA1.update(&hashCtx, &signedParams)) != 0)
        goto fail;
        goto fail;
    /* more checking here.  */
  fail:
    /* cleanups */
    return err;

goto fail; が実行されるとエラー時の処理が走るのですが、二つめの goto fail; は if 文に含まれておらず常に実行されてしまいます。

-Wsign-compare

整数同士の比較を行う際、片方（たとえば左辺）は符号つき整数型で、他方（たとえば右辺）は符号なし整数型だったときに出てくる警告です。 これも無視している人がたくさんいると思います。これ起因のバグのうち競プロで頻出のものは次のようなものです。

bool has_xx(std::string s) {
    for (int i = 0; i < s.length() - 1; ++i) {
        if (s[i] == s[i + 1]) {
            return true;
        }
    }
    return false;
}

s.length() の部分は符号なし整数型なので、符号あり整数型である i とは符号の有無が異なります。

まず前提として、C++ においてはこういう状況では、型の符号の有無（signed か unsigned かということで、signedness という呼ばれ方をします）が統一されてから比較が行われます*1。 どちらに合わせるかは状況によりますが、多少複雑なので、下手に覚えると誤ってしまいそうな気もします。たとえば i < int(s.length()) - 1 のように signedness を陽に統一してしまう方が安全そうです。int に収まらないサイズだった場合はこれまたバグの原因ですが、競プロでそういうサイズを扱うことはほぼないと思いますので。

型を合わせる部分に関して

片方が浮動小数点数型の場合は、そちらに合わせられます。両方が浮動小数点数型だった場合は float < double < long double の順で強いです。 以下ではどちらも整数型だとします。

bool < signed char < short < int < long < long long の順で conversion rank というのが定められています。signed T と unsigned T の conversion rank は同じです。char と signed char unsigned char も同じ conversion rank です。

int より conversion rank の低い型に対しては、多くの場面では integer promotion というのがまず適用されます。

  • signed char と short は int になる
  • unsigned char と unsigned char は、int でその型の値すべてを表せるなら int、そうでないなら unsigned int になる
  • char は signed なら signed char、unsigned なら unsigned char 同様に変換される
  • bool は int になる

そのあと integer conversion が行われます。

  • 両方が signed または両方が unsigned ならば、conversion rank が低い方の型が、高い方の型に変換される。
  • そうではなく、unsigned の方の conversion rank が signed の conversion rank 以上だった場合、signed の方の型が unsigned の方の型に変換される。
  • そうではなく、signed の方の型で unsigned の方の型の値すべてを表せる場合、unsigned の方の型が signed の方の型に変換される。
  • そうではない場合、両方の型が signed の方の型の unsigned 版に変換される。

たとえば、int と unsigned long だった場合、二つめの規則により int → unsigned long になります。 long (64-bit) と unsigned int (32-bit) だった場合、三つめの規則により unsigned int → long になります。 long (32-bit) と unsigned int (32-bit) だった場合、四つめの規則に long → unsigned long かつ unsigned int → unsigned long になります。...だと思います。

整数のビット長は一般に処理系定義ですが、有名な処理系においては long だけが異なりがちです。AtCoder の環境では 64-bit、Codeforces の環境では 32-bit なのが有名でしょう。

さて、上記のコードの該当箇所では多くの処理系では unsigned の方に合わせられるはずです。すなわち、たとえば unsigned(i) < s.length() - 1 のようになります。 このとき、s.is_empty() の状況では unsigned(i) < unsigned(-1) のようになります。unsigned(-1) はその符号なし整数型の最大値になるので、意図せず i が大きい値までループする（実際には s が空なので、s[1] にアクセスした時点で未定義動作になります（s[0] は '\0' が返るのが保証されているため））ことになってしまいます。

-Wreorder

以下のように、メンバ変数の宣言順とコンストラクタ（の : name(value), ... で初期化する部分）の初期化順が異なるときの警告です。

struct Foo {
    int b, a;
    Foo(int x): a(x++), b(x++) {}
};

これだけ聞いても「別によくない？ 合わせた方が気持ちいいでしょというお気持ち押しつけか？」以外の気持ちにならない気がします。 実際には、メンバ変数の宣言順に合わせて初期化されることになっているため、上記でたとえば Foo(1) とすると Foo { b: 1, a: 2 } のように初期化されてしまいます。 これはおそらく人間様の意図に沿っていないでしょうから、警告を出してくれているというわけです。

初期化時に副作用がないコードを書いていればあまり影響がない気もしますが、あまり自信はありません。なにか忘れているかもしれません。

-Wsequence-point

C++ には “Sequenced before” rules と呼ばれる概念があります*2。 これは “evaluation A is sequenced before evaluation B” という形式で記述され、「処理 A は、処理 B が開始されるよりも前に完了される」ということを規定しています。

この順序関係以外には、“A and B are unsequenced”（処理が並行して行われうる）や “A and B are indeterminately sequenced”（順序は決まっておらず、実行ごとに前後することもありうるが、片方が終わってから他方が始まることは保証される）というのがあります。

int f(int i, std::vector<int> const& a, std::vector<int> const& b) {
    int x = a[i++] + b[i++];
    int y = a[i++] + b[i];
    return x + y;
}

さて、i++ のような副作用*3を持つ処理があったとき、その処理に対して unsequenced な別の処理が同じメモリ箇所を読み書きするときの動作は未定義です。

LLL + RRR のような式に対して、LLL の評価は RRR の評価に対して unsequenced なので、上記のコード（x の定義部分も y の定義部分も）は未定義となります。 x = a[i] + b[i + 1]; y = a[i + 2] + b[i + 3] のようにはなってくれません*4。

詳しくは下記を読んでください。

en.cppreference.com

-Wreturn-type

初心者がバグらせているとき、実はこれが出ていることがとても多い気がします。

int f(int x) {
    if (なんか条件) return 1;
    if (なんか条件) return 2;
    if (なんか条件) return 3;
    // 上記の条件でカバーしたつもりになっている

    // 実際には条件が漏れていて、int を返さないまま関数の終端に来てしまう
}

上記は一例ですが、返り値型が void 以外の関数で値を返さないまま終端に来てしまった場合の動作は未定義です。main は例外で、勝手に return 0; が挿入されますが...

「それを見抜けるならコンパイルエラーにしてくれ」という声はよく聞こえますが、以下のような不都合があります。

int infty_loop() {
    while (実際には常に真となる非自明な条件) {
        if (適当なタイミングで真になる条件) return 1;
        // なんか処理
    }
}

たとえばこのような状況では、コンパイラからは無事に while 文の中で値を返すことを看破できないため、勝手にコンパイルエラーにされると困るわけですね。

（以下は妄想）無限ループ用の特別な構文を別途用意して、

int infty_loop() {
    loop {
        if (実際には常に偽となる非自明な条件) break;
    }
    // 実際には到達しない
}

のようなコードも「loop を抜けうる break があるのでエラーとする」としていいなら、そうするのがよかったのでしょうか。

-Wuninitialized, -Wmaybe-uninitialized

初期化するコードがない場合や、初期化しないコードパスがある場合の警告です。

int main() {
    int x;
    printf("%d\n", x);  // is used uninitialized
}

int foo(int y) {
    int x;
    switch (y) {
    case 0:
        x = 100;
        break;
    case 1:
        x = 123;
    }
    return x;  // may be used uninitialized
}

int foo(int y) {
    int x;
    if (y == 0) {
        x = 100;
    } else if (y == 1) {
        x = 123;
    }
    return x;  // may be used uninitialized
}

初期化せずに使った場合の動作は未定義なので気にしてくれています。ただ、maybe の方は検出してくれないこともある（警告を出すフェイズが、コード解析によって不要と判断した箇所を削除した後という事情があるらしい？）ようで、あまり信用ならないかもしれません。 たとえば、上記コード例で case 1: や else if (y == 1) の部分がなく初期化が一箇所だけの場合は（手元環境では）警告が出ませんでした。

余談として、以下も未定義です。

int main() {
    bool x;
    printf("%d\n", int(x & !x));  // 0 を期待しがち
    printf("%d\n", int(x | !x));  // 1 を期待しがち
}

-Wparentheses

括弧をつけた方がいいですよという警告です。

void foo(int x) {
    if (x = 0) {
        puts("hello");
    }
}

suggest parentheses around assignment used as truth value
      |   if (x = 0) {
      |       ~~^~~

のようなことを言ってくれるのですが、「if (x == 0) のつもりか？」などと言ってくれた方がわかりやすい気がします。

他にも、1 + 2 << 3 * 4 / 5 >> 6 | 7 ^ 8 のような式を書いたときも「<< の内側の + のまわりには括弧をつけよう」「| のオペランドの算術演算には括弧をつけよう」とか言ってくれるようです。

-Wfloat-equal

rsk0315.hatenablog.com

こちらでも触れていますが、浮動小数点数の比較を == や != で行おうとすると誤差などによって意図しない挙動になりがちです。

int main() {
    assert(1.0 / 49 * 49 == 1);
}

これはおそらく false になって abort します。

おまけ

きもち 1

C++ に詳しくない人ほど「警告が出ているから書き方を改めるか...」ではなく「よくわからないから無視するか...」となってしまいがち感があり、かなしいね。

でもいきなり -Wstrict-aliasing で “... will break strict-aliasing rules” とか言われてもよくわかんなくてこまっちゃうよね。

きもち 2

コンパイル時警告の出し方と、基本的な典型バグだけでも押さえておけば、「なんでバグってますかこれ、助けてください」「警告見ましたか？ いろいろ出てますよ」のようなやり取りが減らせてうれしそうな気がします。

おわり

ねこねこ

*1:実際には型が統一されているわけですが、ここでは符号のことに言及すれば十分だったので。

*2:C や、古い C++ では sequence point と呼ばれる概念がありました。

*3:副作用という用語も、わりとふんわりお気持ち定義で使われている感があるかもしれません。？

*4:未定義動作の結果、たまたまそういう挙動になることを否定しているわけではありません。

ある種の無限級数を DP で求める

というやり取りがありました。

$$ \sum_{k=1}^{\infty} \frac{k^{n+k-1}}{k!\, 2^k\, e^{k/2}} $$ という無限級数を求めたいです。ここでは $O(n^2)$ 時間の方法を述べますが、頭のいい人がちゃんと考察をすればもっと高速になるのかもしれません。

動機

たぶんここは読み飛ばしてもいいです。上記の無限級数がどうして求めたくなったかの話を書きます。

数え上げの講義資料（？） の 12 章の演習問題から抜粋です。 $N_n = \{0, 1, \dots, n-1\}$ の部分集合全体からなる集合 $2^{N_n}$ を考えます。

この部分集合 $\Delta\subseteq 2^{N_n}$ であって、$A, B \in\Delta \implies (A\cap B = \emptyset) \vee (A \subseteq B) \vee (A\supseteq B)$ を満たすもの全体の集合を $\mathcal{N}_n$ とおきます。$\Delta$ は、うまくネストされた部分集合たちという感じです。

たとえば、$\mathcal{N}_0 = \{ \{\}, \{\{\}\} \} = 2^{2^{N_0}}$、$\mathcal{N}_1 = \{ \{\}, \{\{\}\}, \{\{0\}\}, \{\{\}, \{0\}\} \} = 2^{2^{N_1}}$、$\mathcal{N}_2 = 2^{2^{N_2}}$ です。

$\mathcal{N}_3$ の要素としては、$\{\{0\}, \{0, 2\}\}$ や $\{\{1\}\}$ や $\{\{\}, \{0, 1\}, \{2\}, \{0, 1, 2\}\}$ や $\{\{\}, \{0\}, \{1\}, \{2\}, \{0, 2\}, \{0, 1, 2\}\}$ などがあります。一方 $2^{2^{N_3}} \smallsetminus \mathcal{N}_3$ の要素としては、$\{\{\}, \{0, 1\}, \{1, 2\}, \{0, 1, 2\}\}$ や $\{\{\}, \{0\}, \{1\}, \{0, 1\}, \{2\}, \{0, 2\}, \{1, 2\}, \{0, 1, 2\}\} = 2^{N_3}$ などがあります。

これに対してがちゃがちゃすると、 $$ \gdef\card#1{\#{#1}} \card{\mathcal{N}_n} = 4\sum_{k=1}^{\infty} \frac{k^{n+k-1}}{k!\, 2^k\, e^{k/2}} $$ が言えるらしいです。というわけでこれを求めたいです。

考察

$W$ 関数との関連

Lambert の $W$ 関数 というのがあります。これは、$w(x) = xe^x$ の逆関数で、$x = W(x) e^{W(x)}$ です。 たとえば、$w(-1/2) = -\frac{1}{2}\cdot e^{-1/2} = -\frac{1}{2\sqrt{e}}$ なので、$W{\left(-\frac{1}{2\sqrt{e}}\right)} = -1/2$ です。

これに対して、 $$ W(x) = \sum_{k=1}^{\infty} \frac{(-k)^{k-1}}{k!} x^k $$ という表現が知られています。 $$ \begin{aligned} -W(-x) &= -\sum_{k=1}^{\infty} \frac{(-k)^{k-1}}{k!} (-x)^k \\ &= \sum_{k=1}^{\infty} \frac{k^{k-1}}{k!} x^k \\ \end{aligned} $$ が成り立つので、$x = a \coloneqq \frac{1}{2\sqrt{e}}$ として $$ -W(-a) = \sum_{k=1}^{\infty} \frac{k^{k-1}}{k!\, 2^k\, e^{k/2}} = \frac{\card{\mathcal{N}_0}}{4} $$ となります。$W(-a) = -1/2$ より、$\card{\mathcal{N}_0} = 2$ とわかります。

さて、 $$ f_0(x) = -W(-x) = \sum_{k=1}^{\infty} \frac{k^{k-1}}{k!} x^k $$ とおき、$f_{i+1} = x\cdot f_i'(x)$ ($i = 0, 1, \dots$) と定めると、 $$ f_n(x) = \sum_{k=1}^{\infty} \frac{k^{n+k-1}}{k!} x^k $$ となります。

$W$ 関数の微分

$\gdef\dd{\mathrm{d}}$

逆関数の微分などを考えます。 $y = W(x)$ とすると $x = w(y) = ye^y$ で、$\dd x/\dd y = (y+1)e^y$ より、 $$ \frac{\dd y}{\dd x} = \frac{1}{\frac{\dd x}{\dd y}} = \frac{1}{(y+1)e^y} $$ です。$e^y = x/y$ に注意すると、 $$ W'(x) = \frac{W(x)}{x\cdot (1+W(x))} $$ となります。

$f_0(x) = -W(-x)$ であったので、 $$ \begin{aligned} f_1(x) &= x\cdot(f_0(x))' \\ &= x\cdot(-W(-x))' \\ &= x\cdot W'(-x) \\ &= -\frac{W(-x)}{1+W(-x)} \end{aligned} $$ とわかります。

ここで、$V(x) \coloneqq 1+W(-x)$ とおくと、$f_1(x) = -W(-x)/V(x)$ と書けます。

DP

手でがちゃがちゃやったりしていると、一般に $W(-x)^j/V(x)^{2i-1}$ の微分（に $x$ を掛けたもの）を求めたいな〜という気持ちになります。 計算過程は煩雑なので、結果だけ載せます。商の微分公式や合成関数の微分公式などを使いながらがんばるとよいです。

$$ \begin{aligned} x\cdot \left(\frac{W(-x)^j}{V(x)^{2i-1}}\right)' &= \frac{W(-x)^j}{V(x)^{2i+1}}\cdot(j+(j-(2i-1))\cdot W(-x)) \\ &= j\cdot\frac{W(-x)^j}{V(x)^{2i+1}} +(j-(2i-1))\cdot \frac{W(-x)^{j+1}}{V(x)^{2i+1}}. \\ \end{aligned} $$

$\gdef\DP{\mathrm{dp}}$ ここで、$f_i$ における $W(-x)^j/V(x)^{2i-1}$ の係数を $\DP[i][j]$ で定めます。 $f_1(x) = -W(-x)/V(x) = (-1)\cdot W(-x)^1/V(x)^{2\cdot 1-1}$ だったので、$\DP[1][1] = -1$ です。

上記の微分より、 $$ \gdef\xgets#1{\xleftarrow{#1}} \begin{aligned} \DP[i+1][j] &\xgets{+} j\cdot\DP[i][j]; \\ \DP[i+1][j+1] &\xgets{+} (j-(2i-1))\cdot\DP[i][j] \end{aligned} $$ の更新を $(i, j)$ の昇順に行えばよいです。

さて、$W(-a) = -1/2$ および $V(a) = 1 + W(-a) = 1/2$ より、 $$ \begin{aligned} \left.\frac{W(-x)^j}{V(x)^{2i-1}}\right|_{x=a} &= \frac{(-1/2)^j}{(1/2)^{2i-1}} \\ % &= \frac{2^{2i-1}}{(-2)^j} \\ % &= -\frac{(-2)^{2i-1}}{(-2)^j} \\ &= -(-2)^{2i-j-1} \end{aligned} $$ となるので、$n \ge 1$ に対して $$ \begin{aligned} \card{\mathcal{N}_n} &= 4\sum_{j=1}^n \DP[n][j] \cdot (-(-2)^{2n-j-1}) \\ &= -\sum_{j=1}^n \DP[n][j] \cdot (-2)^{2n-j+1} \end{aligned} $$ とわかります。

あるいは、最後に $(-2)^{*}$ を掛けるのではなく、遷移しながら $-2$ を掛けていくような別の方針の DP もできるかもしれません。 そちらの方針についてはあまり考えていません。

実装

実装自体は、（遷移が与えられていれば）DP 初級編くらいの内容な気がします。すぐにめちゃ大きくなるので、998244353 を法として求めます。

use proconio::input;

type Mi = ModInt998244353;

fn main() {
    input! {
        n: usize,
    }
    let mut dp = vec![vec![Mi::new(0); n + 2]; n + 1];
    dp[1][1] = Mi::new(-1);
    for i in 0..n {
        for j in 1..=i {
            let x = dp[i][j];
            dp[i + 1][j] += Mi::new(j) * x;
            dp[i + 1][j + 1] += (Mi::new(j) - Mi::new(2 * i - 1)) * x;
        }
    }

    let powm2 = {
        let m = 2 * n;
        let mut pow = vec![Mi::new(1); m + 1];
        for i in 1..=m {
            pow[i] = pow[i - 1] * Mi::new(-2);
        }
        pow
    };

    let sum: Mi = (1..=n).map(|j| dp[n][j] * powm2[2 * n - j + 1]).sum();
    println!("{}", -sum);
}

$(\card{\mathcal{N}_n})_{n=0}^{\infty} = (2, 4, 16, 128, 1664, 30208, \dots)$ となりそうです。

所感

自分語りのコーナーです。 唐突ですが、$e^{e^x}$ の $i$ 階微分は、$e^{e^x + jx}$ ($1\le j\le i$) の線形和で表せます。 たとえば、 $$ \frac{\dd^4}{\dd x^4} e^{e^x} = e^{e^x + x} + 7 e^{e^x + 2 x} + 6 e^{e^x + 3 x} + e^{e^x + 4 x} $$ といった具合です。

高校生くらいのえびちゃんは競プロや DP という用語を知りませんでしたが、これの係数を手計算で求めようとして DP をしていた記憶があります。

$$ \begin{aligned} \frac{\dd}{\dd x} e^{e^x + jx} &= (e^{e^x})'\cdot e^{jx} + e^{e^x}\cdot (e^{jx})' \\ % &= (e^{e^x+x})\cdot e^{jx} + j\cdot e^{e^x}\cdot (e^{jx}) \\ &= (e^{e^x+x})\cdot e^{jx} + j\cdot e^{e^x + jx} \\ &= e^{e^x+(j+1)x} + j\cdot e^{e^x + jx} \\ \end{aligned} $$ となることから、$\DP[i+1][j] \xgets{+} j\cdot \DP[i][j]$ と $\DP[i+1][j+1] \xgets{+} \DP[i][j]$ で遷移できるわけですね。 係数に $j$ が含まれるのが大変そうな気もしますが、形自体は単純なので、なんかいい感じの手法で高速化できるのでしょうか。

ともあれ、今回出てきた DP と発想がほぼ同じで、昔のことを思い出してなつかしくなったという話でした。

おまけ

WolframAlpha すごい。

www.wolframalpha.com

www.wolframalpha.com

もう少し大きい $n$ に対しては、無限級数として与える方では、誤差が出たり TLE したりしました。

おわり

にゃんこ。

順列の LIS を O(n log(log(n))) 時間で求めてみようかな

これの解説みたいなのを書きます。

rsk0315.hatenablog.com

この記事の参考文献にある “Bounds on the complexity of the longest common subsequence problem.” の冒頭で、できるとの記述があったので考えた結果です*1。

前提知識

まず、successor query という形式のクエリがあります。 管理している集合 $S \subseteq \N$ に対してクエリ $x$ が与えられ、「$S$ の要素で $x$ より大きいもののうち、最小のものは？」を答えるというものです*2。 存在しないときは $\infty$ としておきます。

たとえば、$S = \{2, 7, 61\}$ のとき、$x = 2$ や $x = 5$ に対しては $7$、$x = 61$ に対しては $\infty$ といった具合です。

集合への要素の追加・削除および successor query を $O(\log(n))$ 時間で処理できるデータ構造として、平衡二分木があるのは有名です。

競プロ界隈では比較的有名でないデータ構造*3として、vEB (van Emde Boas) tree や、y-fast trie というものがあります。 集合に入りうる最大値を $u$ として、以下のような計算量です。

名前 空間 時間
vEB tree $O(u)$ $O(\log(\log(u)))$
vEB tree (with hashing) $O(n)$ expected $O(\log(\log(u)))$
y-fast trie $O(n)$ expected $O(\log(\log(u)))$

これらの紹介としては、下記の記事（にあるリンク）などがあります。

rsk0315.hatenablog.com

qiita.com

方針

LIS を求めるにあたって、セグ木で平面走査をする方針や、蟻本に載っている DP などが有名です。 ここでは後者をベースとした方針を用います。

たとえば [1, 4, 2, 3, 0] の LIS を求める際は、以下のような流れになります。

[oo, oo, oo, oo, oo]  # 初め oo (= ∞) で初期化
↓
[ 1, oo, oo, oo, oo]  # 1 を入れて昇順になる位置に挿入
↓
[ 1,  4, oo, oo, oo]  # 4 について同様
↓
[ 1,  2, oo, oo, oo]  # 2 について同様
↓
[ 1,  2,  3, oo, oo]  # 3 について同様
↓
[ 0,  2,  3, oo, oo]  # 0 について同様
↓
oo より左にある個数が LIS の長さとわかる

ここで、この配列の最終状態が実際の LIS になるとは限らないことには注意しましょう。

手法

さて、上記では配列で管理していた部分を、集合と見なすこともできます。 たとえば、[1, 4, oo, oo, oo] は $\{1, 4\}$ と見なします。 これに対して $2$ を入れるときは、$2$ の successor である $4$ を削除し、$2$ を集合に追加します。

これは、vEB tree などを用いることで、一つあたり $O(\log(\log(u)))$ 時間でできます。 順列なので $u = n-1$ であり、全体で $O(n\log(\log(n)))$ 時間です。

各要素が小さい方から何番目にあるかなどの管理は必要ありませんが、別途それが必要であれば管理は可能です。 追加しようとしている要素は既存の要素を上書きする（削除される要素以外の順位には影響しない）場合と、末尾に追加される場合しかないためです。

実装例

vEB バグってるかも。あんまりテストしてません。

その他

一般の整数列であれば、期待 $O(n \log(\log(u)))$ 時間とかでできそうです。 特に、$u = n^{O(\log(n))}$ であれば $O(n \log(\log(n)))$ ですね。

「vEB tree で処理できる形の解法を考えて $\log$ を $\log\circ\log$ にする」が好きな界隈、ありそうです。

おわり

にゃんこ。

*1:$1, 2, \dots, n$ からなる重複のない数列二つの LCS、という形で言及されています。片方を昇順に並べるように番号をつけ直せば LIS に（あるいは LIS から）帰着できます。

*2:$x$ 自身を含むかどうかについては流儀によるようです。その違いは大きな問題にはならないので、ここでは「含まない」で統一しておきます。

*3:有名でないデータ構造の中では有名寄りな印象。

期待 O(n) 時間の前処理で、クエリごと最悪 O(1) 時間で座標圧縮しようかな

ハッシュを使います。

導入

ある程度の仮定は欲しいです。 というのも、これが一般の型でできたら期待 $O(n)$ 時間でソートができることになるためです*1。

$a = (a_0, a_1, \dots, a_{n-1})$ が与えられ、$a_0 \lt a_1 \lt \dots \lt a_{n-1}$ であるとします。

あるいは、word size がいい感じなのを仮定して基数ソートの類で $\Theta(n)$ 時間でソートができる状況とします。

qiita.com

これに対して前処理をしておき、「$a_i$ の値のみが与えられるので、$i$ を返す」というクエリを最悪 $O(1)$ 時間で処理したいです。 $a$ に含まれない値は与えられません*2。

紹介

突然ですが、cuckoo hashing という手法があります。 競プロ界隈ではハッシュマップの類があまり有名でない気がします*3。

CS166.1226/6 などで、絵つきのスライドで紹介されています。

これは、要素の追加を期待 $O(1)$ 時間、削除と取得を最悪 $O(1)$ 時間でできるデータ構造です。 これに対して $a_i\mapsto i$ の対応づけを入れればおしまいです*4。あれれ。

それ以外の紹介

本当は以下で紹介する話を調べて記事にする予定だったのですが、cuckoo hashing で終わるじゃんと気づいてしまったので、ざっくり紹介だけになります。 簡潔データ構造寄りの文脈の話なので、cuckoo hashing より空間計算量には気を使っているのですが、それこそ競プロ界隈では興味が薄い人が多そうです*5。

座標圧縮に相当するハッシュ関数を monotone minimal perfect hash function と呼ぶ話とか、それを期待 $O(n)$ 時間で構成する文献の紹介とかを以下でします。

ハッシュについての話

キーとしてありうるものの集合 $\mathcal{X}$ とします。たとえば、整数全体の集合 $\Z$ だったり文字列の集合 $\Sigma^*$ だったりします。 そこから $n$ 個選んできたものを $\mathcal{K}$ とします ($\mathcal{K}\subseteq\mathcal{X}$, $|\mathcal{K}| = n$)。

それに対して、クエリ $x\in\mathcal{X}$ が与えられて $x\in\mathcal{K}$ を判定したい状況は頻出です (set)。 あるいは、各 $x\in\mathcal{K}$ に値 $y$ が関連づけられていて、与えられた $x\in\mathcal{K}$ に対してその $y$ を答えたい状況もあります (dict, map)。

以下、$[n]$ で $\{0, 1, \dots, n-1\}$ を意味するとします。

何らかの関数 $h: \mathcal{X}\to[m]$ ($m \ge n$) を用いて、長さ $m$ の配列 $A$ に $A[h(x)] = x$ ($x\in\mathcal{K}$) としておいてみます。 これによって、クエリの $x$ に対して $A[h(x)] = x$ なら $x\in\mathcal{K}$ と判定できそうです*6。 この $h$ をハッシュ関数と呼びます。

しかし、$h$ の選び方によっては、$x, y\in\mathcal{K}$ ($x\neq y$) に対して $h(x) = h(y)$ となってしまうことはありえます。 これを衝突と呼びます。 衝突すると誤って $y\notin\mathcal{K}$ と判定してしまったり、衝突を回避するために計算量を犠牲にすることになったり、もう散々です。

「定数時間を実現するためにハッシュを導入したのに、最悪ケースでは線形時間とかになるらしい。は〜ばかばかしい 😩」となる競プロ er は多そうです。わかるわかる。

以下では衝突のことは気にしないので、衝突が起きた際の処理 (open hashing, closed hashing) とか衝突が起こる確率とかの話はしません。

+perfect

衝突しないハッシュ関数は perfect hash function と呼ばれています。 すなわち、$x, y\in\mathcal{K}$ ($x\neq y$) に対して $h(x) \neq h(y)$ となる $h$ です*7。

$\mathcal{K}$ が静的*8であれば perfect hash function を構成することができます。 また、dict のクエリにおいては、$x\in\mathcal{K}$ は保証されていて、対応する値を返せばよい問題設定であるケースも多いです。 すなわち、$h:\mathcal{K}\to[m]$ を構成すればよいです。

そうした状況では、配列 $A$ のための $\log(\binom{|X|}{n})$ bits が必要なくなり、$2.46n + o(n)$ bits と期待 $O(n)$ 時間で構成する手法があるらしいです。

+minimal

さらに、perfect hash function のうちで $m = n$ とできるもの、すなわち $h: \mathcal{K}\to[n]$ ($x\neq y \implies h(x) \neq h(y)$) を minimal perfect hash function といいます。

これもなんやかんやして $2.46n + o(n)$ bits にできるらしいです。

+monotone

キーの集合を整数 $\mathcal{X} = [u]$ とします。 このとき、minimal perfect hash function が $x\lt y \implies h(x)\lt h(y)$ を満たすとき、monotone minimal perfect hash function といいます*9。

要するに、いわゆる座標圧縮は monotone minimal perfect hash function に相当していますね。 競プロ界隈でそういう呼び方をしている人はほぼいなさそうです。

また、整数の大小関係だけではなく、与えられた任意の順序を保存できるハッシュ関数 ($x\prec y \implies h(x)\lt h(y)$) は order-preserving と呼んで区別する流派もあるようです。

これは $O(n\log(\log(u)))$ bits と期待 $O(n)$ 時間でできるみたいです。クエリを $O(\log(\log(u)))$ 時間にしてよいなら $O(n\log(\log(\log(u))))$ bits に落とす手法もあるとかなんとか。

文献

この辺の話は Navarro, Gonzalo. Compact data structures: A practical approach. Cambridge University Press, 2016. の 4.5.3 Dictionaries, Sets, and Hashing に載っています。結構お高い。フォロヮからお年玉をもらったので新年早々買ってしまいました*10。今月ちょっとピンチです。

以下も読んでみると面白いかも。えびちゃんはまだです。

  • Belazzougui, Djamal, Paolo Boldi, Rasmus Pagh, and Sebastiano Vigna. “Theory and practice of monotone minimal perfect hashing.” Journal of Experimental Algorithmics (JEA) 16 (2008): 3-1.
  • Belazzougui, Djamal, Paolo Boldi, Rasmus Pagh, and Sebastiano Vigna. "Monotone minimal perfect hashing: searching a sorted table with $O(1)$ accesses." In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pp. 785–794. Society for Industrial and Applied Mathematics, 2009.

実測

一応してみました。

あーあって感じ。もっとチューニングをがんばればいい感じになるのかもしれません。

おきもち

ハッシュ系とかのデータ構造はあんまり流行らないのかなぁという気がします。 ヒュだとハッシュを使う人もいるのかなあ。えびちゃんはヒュに興味が持てないのでわかりません。

競プロで出てくるものの大半は整数（integer alphabet の文字列含む）なので、もっと整数系のデータ構造とかは流行ってもよさそうなのに、wavelet matrix とかも（最近はある程度知れ渡ってきた気もするものの）まだ知る人ぞ知る感がある気もします。

他にも log を落とす系のものもあんまり人気がなさそうです。仕方なさそう。

rsk0315.hatenablog.com

「log を落とす系は定数倍が悪いことが多いから...」と敬遠する割には、ビット並列で高速化するやつは「非本質な定数倍高速化だし...」と言う人もいたりしそうです。

rsk0315.hatenablog.com

rsk0315.hatenablog.com

人には人の興味なので、興味のありそうなアルゴリズムを調べてみるとよさそうです。

おわり

今年もよろしくお願いします。

*1:最悪と言ってはいないので不可能ではないかも？ わかりません。ただ簡単そうではない気がします。

*2:特に、与えられた $x$ 以下で最大の $a_i$ は？という形式の predecessor query は考えません。

*3:最悪計算量以外興味なし、期待計算量は FAKE のような風潮があったりなかったり。気持ちはわかる。

*4:$a_i$ に対して適当なハッシュ値を計算するのが定数時間でできるのは仮定します。

*5:競プロ界隈の興味のために記事を書いているわけでもないのですが。

*6:この $A$ のために $\log(\binom{|X|}{n}) = n\log(|X|/n) + O(n)$ bits 必要になります。

*7:$x\in\mathcal{X}, y\in\mathcal{X}\setminus\mathcal{K}$ について $h(x) = h(y)$ となっても問題ない気がするけどだめ？

*8:追加されたりしない状況。削除されるのはここでは問題なさそうだけど削除もされないとするのが普通そう。

*9:minimal じゃないものについては monotone perfect hash function とかになるかもしれません。ここではそういうのは考えません。

*10:@rsk0315_h4x さんありがとうございます。

はてなブログで KaTeX を使う

まとめておいた方がいいかなと思ったので。

導入方法

$\KaTeX$ の JavaScript を読み込む必要があります。各記事のヘッダ部分にそれを追加します。

以下のスクショを参考に、管理画面 (デザイン) > カスタマイズ > ヘッダ > ブログタイトル下の入力欄を探します。

デザイン

デザイン > カスタマイズ > ヘッダ

追記：管理画面 (設定) > 詳細設定 > 要素にメタデータを追加 の部分に書く方がいいかもしれません？

そこに、$\KaTeX$ > Browser > Starter template の <head>...</head> の中の内容を入れます。 実際には、使い勝手の向上のために多少手を加えたいので、まるっとコピペできる用のものは記事下部に載せます。

はてな記法の tex 記法との比較

help.hatenablog.com

たとえば、以下のように書きます。

[tex: \sum_{i=1}^n \left\lfloor\frac{n}{i}\right\rfloor = O(n\log(n))]

あるいは、_ \ などをエスケープして以下のように書く癖をつけた方が無難かもしれないので、以下のようにも書きます。

[tex: \\sum\_{i=1}^n \\left\\lfloor\\frac{n}{i}\\right\\rfloor = O(n\\log(n))]

どちらの場合も、次のように表示されます。

\sum_{i=1}^n \left\lfloor\frac{n}{i}\right\rfloor = O(n\log(n))

$\KaTeX$ を導入した場合は次のように書きます。

\\(\\sum\_{i=1}^n \\left\\lfloor\\frac{n}{i}\\right\\rfloor = O(n\\log(n))\\)

あるいは \\(...\\) ではなく $...$ を用いることもできます。

$\\sum\_{i=1}^n \\left\\lfloor\\frac{n}{i}\\right\\rfloor = O(n\\log(n))$

どちらの場合も、次にように表示されます。

$\sum_{i=1}^n \left\lfloor\frac{n}{i}\right\rfloor = O(n\log(n))$

フォントが違っているため、（フォント関連の設定をしている場合を除き）どちらの記法で書かれた記事かは見ればわかりがちです。

キーワードリンクに関して

「はてな」のように、特定のキーワードにリンクがつく機能です。

markdown の処理やキーワードリンクの処理がなされた後、$\KaTeX$ による数式処理がされるわけですが、数式中にリンクが含まれているとうまく変換してくれません。 解決はできるので大丈夫ですが、素朴にやると変になる例を先に挙げておきます。

衝突する例と ad hoc な回避策

たとえば、$m-1$ のように書きたい場合でも $m-1$ のようになってしまいます。このケースでは $m-1$ の代わりに $m -1$ のように書くことで回避できますが、うれしくありません。

また、$∧$ (\wedge) を書きたい場合、$\wedge$ のようになってしまいます。 $\KaTeX$ は記号の直接入力ができるので、$∧$ と入力すれば $∧$ を出せますが、入力が多少大変です。

さらに、$\arcsin$ (\arcsin) を書きたい場合も、$\arcsin$ のようになってしまいます。 これは、（数式中の空白が無視されることを利用して）$\\gdef\\asin{\\operatorname{arcsi n}}$ のようなマクロを作ってから $\\asin$ のように書けば回避できますが、かなりうれしくないです。

解決方法 1

さて、はてな有料版であればキーワードリンク無効化のオプションがあるらしいですが、これだけのために有料版を使うのもうれしくなさそうです。 上記のはてな記法ヘルプを見ると、「自動リンク停止記法」というのがあります。

はてな はてな []はてな[] はてな []はてな[]

はてな はてな はてな はてな はてな

これを数式に対して使う方法があります。[]...[] が <span> で囲まれてしまい、$ の中に <span> があるとうまくいかないようなので*1、特定箇所だけではなく、数式全体を囲む必要があります。

$\\[]arcsin[]$ []$\\arcsin$[]

$\arcsin$ $\arcsin$

複数行についても回避可能なようです。

[] $$
\\begin{aligned}
x &= y \\\\
&= m-1
\\end{aligned}
$$ []

$$ \begin{aligned} x &= y \\ &= m-1 \end{aligned} $$

汎用的な方法ではありますが、数式を $...$ ではなく []$...$[] で囲むのはちょっと面倒そうです。

あれ、もしかして記事全体を [] で囲む（記事の先頭と末尾に [] を書く）と解決しますでしょうか。

解決方法 2

テンプレートに onload="renderMathInElement(document.body); と書いてある通り、ロードされた後の所望のタイミングで数式の組版ができることがわかります。 よって、「数式と衝突しそうな単語のキーワードリンクを除去してから組版する」という方法があります。

（別に数式関係なく無効化したいという人はそれでもいい気もするのですが）さすがにアレかなと思い、自分で列挙しています。 キーワードリンクに追加される単語は随時追加されているようなので、昔の記事が勝手に変な感じになる可能性はありそうです。 これはかなり嫌ですが、共通設定のヘッダ（上記で言及した「ブログタイトル下」の部分）に追記するだけで直せるのでいいかなという感じです。

具体的な記述に関しては以下のコピペ用部分を見てください。

マクロなど

人によっては、たとえば以下のようなマクロを頻繁に使うかもしれません。

  • $\gcd(x, y)$ (\\gcd(x, y))
  • $\polylog{n}$ (\\polylog(n))
  • $\floor{n/i}$ (\\floor{n/i})
  • $\angled{O(n), O(1)}$ (\\angled{O(n), O(1)})

こうしたものを各記事で定義することもできるのですが、毎回書くのは嫌そうです。 これも、共通のヘッダに書くことができます。 具体的な記述は以下を参考にしてください。

note: 記事中での定義は以下のようにして可能です。

$$
\\gdef\\foo{\\operatorname{foo}}
\\gdef\\bar#1#2{\\operatorname*{bar}\_{#1}\^{#2}}
$$

$$\\foo \\bar{a}{b}$$

$$ \gdef\foo{\operatorname{foo}} \gdef\bar#1#2{\operatorname*{bar}_{#1}^{#2}} $$

$$\foo \bar{a}{b}$$

コピペ用

<script>
    'use strict';
    const mathWord = new Set([
        // 必要に応じて追加する
        'arccos',
        'arcsin',
        'arctan',
        'k-1',
        'l-1',
        'm-1',
        'qed',
        'sigma',
        'tau',
        'wedge',
    ]);
    const isMathWord = w => mathWord.has(w.toLowerCase());
    function cancel(el) {
        Array.from(el.querySelectorAll('a.keyword'))
            .filter(e => isMathWord(e.innerHTML))
            .forEach(e => e.outerHTML = e.innerHTML);
    }
    const KaTeXOptions = {
        delimiters: [
            {left: '$$', right: '$$', display: true},
            {left: '\\[', right: '\\]', display: true},
            {left: '$', right: '$', display: false},
            {left: '\\(', right: '\\)', display: false},
        ],
        macros: {
            '\\halfopen': '[#1, #2)',
            '\\floor': '\\lfloor #1\\rfloor',
            '\\ceil': '\\lceil #1\\rceil',
            '\\Floor': '\\left\\lfloor #1\\right\\rfloor',
            '\\Ceil': '\\left\\lceil #1\\right\\rceil',
            '\\angled': '\\langle #1\\rangle',
            '\\Angled': '\\left\\langle #1\\right\\rangle',
            '\\lcm': '\\operatorname*{lcm}',
            '\\gcd': '\\operatorname*{gcd}',
            '\\poly': '\\operatorname{poly}',
            '\\polylog': '\\operatorname{polylog}',
        }
    };
</script>

<!-- See https://katex.org/docs/browser.html -->

<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/katex@0.16.4/dist/katex.min.css" integrity="sha384-vKruj+a13U8yHIkAyGgK1J3ArTLzrFGBbBc0tDp4ad/EyewESeXE/Iv67Aj8gKZ0" crossorigin="anonymous">

<!-- The loading of KaTeX is deferred to speed up page rendering -->
<script defer src="https://cdn.jsdelivr.net/npm/katex@0.16.4/dist/katex.min.js" integrity="sha384-PwRUT/YqbnEjkZO0zZxNqcxACrXe+j766U2amXcgMg5457rve2Y7I6ZJSm2A0mS4" crossorigin="anonymous"></script>

<!-- To automatically render math in text elements, include the auto-render extension: -->
<script defer src="https://cdn.jsdelivr.net/npm/katex@0.16.4/dist/contrib/auto-render.min.js" integrity="sha384-+VBxd3r6XgURycqtZ117nYw44OOcIax56Z4dCRWbxyPt0Koah1uHoK0o4+/RRE05" crossorigin="anonymous"
    onload="cancel(document.body);renderMathInElement(document.body, KaTeXOptions)"></script>

参考

markdown の記法と衝突しないようにするための書き方など

kmyk.github.io

はてな記法からの移行に関してなど

noimin.hatenablog.com

過去の記事で $...$ などを書いていなければ、$\KaTeX$ を導入しても過去の記事への影響は基本的にはないのではなさそうな気もします。

おきもち

人々が「はてなで数式を書くのしんどい」と言っているとき、はてな記法の tex 記法に対して言っているのか、そもそも TeX 自体がしんどいのか、$\KaTeX$ を使っているけれども markdown と衝突するため \_ や \\ などと書いたり、はてな記法との衝突を避けるために \^ のようにしたりするのが嫌なのか、などが場合によりそうなので、見極める必要がありそうです。

[tex: ...] と書くのが面倒というだけであれば、$\KaTeX$ を導入するのが一番楽なのではないでしょうか。

おわり

😀 \\sum\_{i=1}^n \\left\\lfloor\\frac{n}{i}\\right\\rfloor = O(n\\log(n))
😄 $\\sum\_{i=1}^n \\left\\lfloor\\frac{n}{i}\\right\\rfloor = O(n\\log(n))$
😣 $\\arcsin$
😄 $\\arcsin$

楽に書けるようになるとよいですね。

*1:タグのネスト関連の事情。

今年のえびちゃん 2022

今年もやってみます

rsk0315.hatenablog.com

今年お勉強したもの

実装したものや記事を書いたものも含めます。

今年なにもできていない気がしていたんですが、実は結構書いていたみたいです。月単位で見れば一つ以上記事を書いていそうです。

あと、数年前の競プロ始めたてくらいの年に見て以降何度か挫折していた Hu–Tucker algorithm をお勉強したり、どこかで見て挫折していた LARSCH algorithm をお勉強したりしました。本当は LARSCH の解説をねこねこ勉強ぱーてぃでやる予定だったのですが、全然間に合いませんでした。

たまに「えびちゃんさんが持ってくるニッチめなアルゴリズムネタってどこから仕入れているんですか？」と聞かれることがあった気がするんですが、えびちゃんも覚えていません。どこから仕入れているんでしょう。普通に蟻本とかあるある競プロ本とかでお勉強していたら線形 RMQ とかすら目に入らなさそうですよね。

去年の記事で「来年やります...」と言っていたものをあまりしていませんが、気分屋さんということで許してほしいです。最近は FPS での数え上げとかのお勉強をしています。

そういえば LuaLaTeX を導入して環境を整えつつあります。先日の LCS の記事内の画像も LuaLaTeX+TikZ で生成したものです。TeX のドキュメント中で「DP などをして得られるテーブルを出力したい」のようなときに「別の言語で書いたものをコピペする」「TeX 言語 🤮 で実装する」などをせずに書けるのがうれしいです。Lua は（競プロで慣れている言語と比べると）多少癖がありますが、それでも許容できないほどではない気がしています。

その他書いたもの

zenn.dev

数年前に書いたのの書き直しではあるのですが、こういう感じのを書きました。もっとこういう感じのが気にされてもいいよねと思っています。みんな不便に思うでしょ。

こういうの も書きました。WebAssembly というのを使っていて、Rust の競プロライブラリを Web サイトに流用できたのがよかったです。動画中ではマウス操作ですが、キー操作にも対応しています。

passwordle はそこそこ伸びました。もっとバカみたいに伸びた記憶があったのですが、見返したら数はそこまででもありませんでした。ただ、海外の人の反応が多めだったり、Gigazine で 記事 になっていたりしたので普段の伸びとは差別化が図れている気もします。

エスパーするやつ はおふざけでした。なんですかこれは。

以下は去年だったらしいですが、まとめて紹介しちゃいます。

  • 目を鍛えるやつ
    • 有名な人がトークンとかを雑にぐちゃっと塗って画像ツイートしていてヒエッってなったので作った
  • ぐるぐるするやつ
    • たのしそうなので作った
    • マウス移動の際に座標を取得して、直近 3 点に対して CCW みたいな感じで方向を計算している

ぐるぐるするやつは、通常のマウス・パッド操作と違い、無限長のスペース（あるいは指を浮かせて戻す行為）を必要としないので、いい感じに応用できると面白そうかもしれません。

rsk0315.github.io

書きかけですが、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 もあります。とても快適です。

今年あったこと

TTPC がありました。ばたばたしているうちに参加記を書きそこねてしまったんですが、ここで少し触れて満足ということにします。

connpass の参加者欄にはいないのになぜという感じですが、所属をよく見ると察するかもしれません。 たまたま自分の所属しているところ*2でオンサイトコンテストが開かれると、特別枠で参加できる可能性が高まるらしいです。

えびちゃんが TTPC 2022 のことを知ったのは一般公開のときだったので、「オンサイト会場に見慣れた住所が書かれてるじゃん？、？！？」という感想でした。

びーとくんと久々に会えたのがうれしかったです。

完全に忘れていたんですが、思い出したので追記です。 GCJ や MHC でいい感じの成績を取り、T シャツを得ることができたのでうれしかったです。

買ったものとか

実体がある

iPad Pro や iPhone 13 mini を買ったりしました。えびちゃんは (PRODUCT)RED の色が好きなんですよね。

あとまだ写真は載せていないのですが、ツイで見かけた干支のキメラのマスコットを衝動買いしました。

www.felissimo.co.jp

仕様なのかわかりませんが、四本の足の先が同一平面上になく、ややバランスが悪くて頼りないです。商品紹介ページの写真を見た感じだと仕様ではなさそうですね。 この子も去年の子（冒頭リンクの 2021 の記事参照）同様にヘアゴムを掛ける場所として適しています。しっぽの蛇のところがおすすめです。

実体がない

YouTube のプレミアムや Slack の Pro subscription を使ってみています。どうせ個人で使っているものなので、無料であることにこだわる必要もないのかなとなってきました。以下のことも動機の一つです。

あと、PayPay などの支払いサービス（デビットカードとかも含む）を導入しました。 現金でがんばるの、oj とかを導入せずに手作業でサンプルを試すのに似ています。 前よりも浪費が簡単になった気もします。嘘喰いとかを一括で買ってしまいました。

その他

来年はまた日記をつける癖を取り戻してみようかなと思ったりもしています。

おいしい

レアチャーシューおいしいですね。最近はもう売っていなくてかなしいです。

おわり

意外と書けることが多くてびっくりしました。来年もえびちゃんらしくがんばっていきたいです。よろしくおねがいします。

*1:自然とはなにかについて考えさせられそうですね。すでに AZIK を自然だと感じてしまっています。

*2:陽に所属を明らかにしていませんでしたが、わかりやすくなってしまいました。とはいえ今後もあまり触れない方針のつもりです。