ユニークビジョンLT会に登壇してきた

Published on 2025-02-07
Last Modified 2025-02-07

概要

ユニークビジョンプログラミングコンテスト2024クリスマス(AtCoder Beginner Contest 385) に参加し、参加者限定イベントの、ユニークビジョンオフィスにて行われるLT会に登壇者として参加しました。

半月ほど時間がたってしまっていますが、これは単にさぼっていたのが半分、ユニークビジョンのイベント開催記事みたいなのが出てから出そうと思っていたというのがもう半分です。(出そうにないので諦めました。)

登壇資料

台本

実は台本を読んでいました。だから、話が詰まらなかったんですね。(弱メガトン構文)

皆さんこんにちは。私からは、「ダブリングの定数倍を救いたい」というテーマで発表させていただきます。よろしくお願いします。 まずはダブリングについて軽く説明をします。ダブリングとは、すべての頂点の出次数が1の有向グラフにおいて、K回進んだ先がどこになるかを高速に求める手法のことです。 異なるものを指してダブリングと呼ぶこともあるかと思いますが、ここでは触れません。 解法としましては、dp[i][j]を「頂点iから2^j回進んだ頂点」と定義したテーブルを用意して、これを利用してクエリに解答するのが一般的です。 「2^j回進んだ」という少々変わった定義を使っていますが、こうするといろいろと都合が良いです。これ以上細かいアルゴリズムはここでは説明を省略します。

さて、少し前にPermute K timesという問題がありました。この問題はまさにダブリングを用いて解ける問題の例になっています。 考察すると、頂点iから頂点Xiに辺をはったグラフにおいてダブリングを行えばよいことがわかります。計算量は、O(NlogK)です。 競技プログラマの皆さんなら、logは「定数」ということで、logKの部分は問題にならないと考える場合が多いかと思います。果たして、本当にそうでしょうか。実際に試してみましょう。

細かいコードは後で見てほしいのですが、こんな感じのプログラムをD、pypy、C++の三つで提出して、かかった時間を見ていきます。 こちらが結果になります。 なんと、D言語とpypyがTLEしてしまいました。C++も1200msかかってしまっていて、あまり良い感じではないですね。一応断っておきますが、極端に定数倍を悪くする恣意的な操作はしていません。気になる方は後でコードを見てください。

今日はこの問題に対する定数倍改善を2種類紹介します。まずは弱い方です。dpテーブルの添え字の順番を変えます。先ほどと逆に、dp[i][j]を「頂点jから2^i回進んだ頂点」としてあげましょう。改善前のコードでは、長さ60程度の配列をN本持つ実装になっていましたが、こちらは長さNの配列を60本程度持つ形になっています。

結果です。本当に添え字を入れ替えただけなんですが、なんと全言語TLEを回避することに成功しました。pypyは7ケースくらいTLEしていたんですが、全部通りました。驚きですね。

さて、もう一方の改善も紹介します。 こちらは問題にもう一つ仮定を入れなければいけません。仮定は、クエリをオフラインで見れることです。 アイデアとしては、クエリごとにダブリングをするのではなく、ある桁に対するダブリングを全クエリ一斉に処理してしまおうというものです。next dpをダブリングに適用するといった表現が適切かもしれません。一旦使った桁のテーブルはもう捨ててよいので、副産物として、空間計算量からlogKが落ちます。データを捨てようとすると、自動的に弱い改善を利用する必要があるため、二重にお得です。

口頭の説明だけだとかなり厳しいと思ったので、実装のイメージも載せておきました。興味のある方は後で見てみてください。

結果です。劇的に早くなったことがわかるかと思います。なんと、全言語500msを切ることができました。地味に空間計算量が落ちるのもうれしいポイントです。

まとめです。 今回提案する定数倍改善は「添え字入れ替え」と、「クエリ処理のオフライン化」です。添え字入れ替えは既存のコードを少し変えるだけで入れることができます。原理が謎というデメリットはあります。オフライン化は、かなり効果がありますが、オンライン必須のときは使えませんし、実装も少し変える必要があります。

おや？駄々っ子が「オンラインアルゴがいい」と言っているようですね。 おっと、どこかで見たことのあるロボットがアドバイスをくれています。

はい、しょうもないネタを入れてしまいましたが、実はダブリングしなくてもこの問題は解くことができます。 Kに依存せず、オンラインで、クエリlogNで、それなりに手軽に解くアルゴがあります。 第三の定数倍改善「ダブリングをしない」に関して、私のブログの方で解説を書いていますので、興味のある方は是非ご覧ください。

以上、InTheBloomの発表でした。ご清聴、ありがとうございました。 スライドは私のXで公開しています。

その他

ユニークビジョンの写真を撮りました。Belugaって書いてあるのが現地です。 場所は新宿駅から近いものの、微妙に行き方がわからない場所だったので地図片手にウロウロしてました。寒かったです。

登壇は私以外にも数人いました。 あまり知らない分野の話が聞けました。

LT会がひと段落したらピザと銀の皿の寿司が出てきました。 醤油をつけるのが面倒だったので、寿司を全てプレーンで食べました。プレーンで食べてもおいしかったです。 宅配ピザ食べたの多分数年ぶりです。 パソコンポチポチしてたらおいしいご飯にありつけたので、こんなの許されて良いのか…？って気持ちでした。

2、3人ほど知っている方がいたので、お話していました。会話スキルなさ過ぎて苦しかった。お互いあまり知らない状況で会話をするのって難しいなと毎度思います。

一番の収穫はD言語Language owner上位の方(名前は伏せます)とお話しすることができたことです。 D言語に関して話をすることって普段ないので、とても楽しかったです。 writeflnに%(%s%)を渡すことで配列の出力ができるという仕様を教えてもらいました。

全体的に楽しかったです。 あと、登壇を通してXのフォロワーが結構増えました。 フォローしてもらえるのはうれしいのですが、あのアカウントはあまり大きくしたくないのでちょっと困ってます。

---