奈良高専 Advent Calendar 2021 6日目の記事

はじめに

これは奈良高専 Advent Calendar 2021 6日目の記事です。

自己紹介として、最近表に出たことで、第55回高専祭のTalkCafeで「羊の大号令」の登壇をした者で、HNは西の山と申します。拙登壇の羊はお楽しみいただけたでしょうか。

あとは退部しましたが吹奏楽やってました。打楽器。今は数学同好会とか入ってて、時々参加してます。老害。

他ではあまり表に出て何かをすることは無く、細々と活動しています…（これはガチ。自分から表に出ることが滅法苦手なので、お呼びいただかない限りまた表に出ることは皆無ですかね…こっちからお呼びするの慣らしたいです…）

では本題、予告では「羊登壇の裏話か、高専の課題の流儀か、ケモか、数学の何かかのどれか」なんて言ってましたが、よくばりなので全部話します。

このAdvent Calendar、ここまで真面目な話が続いていたのですが、ここで真面目streakをぶった切ります。

はじめに
第１章　羊登壇の裏話
第２章　高専の課題の流儀
第３章　ケモ
第４章　数学の何か
総括
つなぎ

第１章　羊登壇の裏話

冒頭でも触れた通り、55th高専祭のTalkCafeで「羊の大号令」の登壇させていただきました。実は、この登壇の内容は1,2年前から構想は完成していました。

ある日の眠れない夜、羊数えしていました。1匹ずつ数えるしかないので、羊の増え方に満足いかず、悩んでいたら閃きました。

「呼んだ羊に羊を呼ばせば良いんだ。」

この時点では羊が羊を呼ぶ、所謂、倍々ゲームの発想に至りました。号令レベル1ですね。もちろん、これでも羊の増え方に満足出来ませんでした。所詮、べき乗です。ここで第2の閃きが降ります。

「呼んだ羊に羊を呼ばせる号令を呼ばせれば良いんだ。」

　号令レベル2です。再帰ですね。ここから、「号令レベル」という概念も思い浮かびました。この時点で、3匹から号令レベル3をするだけで無量大数を超えるのが見えて興奮しました。深夜です。

「じゃあレベル4は！？レベル5は！？」

知的好奇心は睡眠欲を破壊し、寝るなんて気はとうに消滅しました。しばらくし、「既存の巨大数と比較しよう」となり、おもむろにスマートフォンから巨大数Wikiをチラチラ。「近いもの、ないかな〜。」ありました。"急増加関数"。「！！！面白すぎる！これいつかLTでやるぞ！」と、気分が高揚しました。深夜です。

ここからは、如何に「この拡張羊数えを急増加関数の定義を近づけるか」の脳内議論が始まりました。大雑把に次のルールが構成できました。

羊を $+1$ する号令をレベル $0$ とする
号令レベル $n$ は今いる羊皆に号令レベル $n-1$ を唱えさせる
併発した号令レベルは小さいほうから優先される
睡眠者自身が号令を唱えると、人である自身がいないため、定義より1足りない状態になることに気づく。
- これを解決するため、睡眠者自身も羊になれば良い
- 「睡眠者は羊になってしまった。1匹では寂しいので羊を呼ぶ。」という自然な導入が副産物に
順序数のレベルも羊の数に置き換えて定義可能
- 順序数の $\omega, \epsilon_0$ とか、尋常を超する何かって感じが出てGood

構想が完成し、就寝。さすがに羊になる夢は見ませんでした。見たかった。起きたその日からスライドのプロトタイプ、「羊の大号令」を作成。想像以上に定義にハマって奇体跡験ボンボビビリーしました。

しかしながら、スライドは完成したけど公開せず、お蔵入りにしました。公開に至らなかった理由は単純で、「巨大数」のLTをしすぎた、そしてシンガタコロナヴァイラスでLTの機会が激減したからでした。当時、直近で2回*1も巨大数に関しての登壇をしてました。どちらもゴリ押し爆速LTをやり、結果、傍聴者の頭を爆発させ、「なるほどわからん」にさせてしまいました。よって、巨大数は一旦自粛していたのでした。*2

時は流れ、この10月くらい、ちょうど高専祭TalkCafeの募集が始まりました。ただ、卒研の中間発表も差し迫り、「今回の参加は見送りかなー」なんて思ってたら、運営の方から「登壇人員不足！君暇也！学徒出陣令！」なんて言われ、渋々出ることに。ネタも思い浮かばず唸ってたら、お蔵入りしてた「羊の大号令」をふと思い出しました。が、元スライドデータがネットの海に難破し、行方不明。「作るかー〜2021」の気持ちでスライドを１から作り始めました。

構想自体は済みなのに、無駄にアニメーションを入れたがる自分のせいで、スライド作成はグダグダ、さらに、その時は卒業研究の中間発表も重なっており、マジヤバでした。おかげさまで…。しかも急増加関数とグラハム数の近い比較がこの最近に証明されてて*3ビビりました。もちろん、スライドに取り入れました。

撮影当日、スライド完成後の細かい修正中、ある一人から「その表現はマズいちゃうか」言われました。確かに*4マズいですので、大幅に改変、要素を取り除きました。そして、活き活きと撮影に臨場、自前の早口が出て、クソ登壇が完成しました。

そして高専祭当日、自分の登壇はまさかの最後。「え、トリ！？こんなクソ登壇が！？」でも想像とは反し、YouTubeLiveやハッシュタグでのコメントは好評。純粋に嬉しかったです…

せっかくなので、「羊の大号令」スライドを公開します。当時の衝撃は薄れてると思いますが、羊の増殖っぷりを再度お楽しみください。（ん、直接パワーポイントあげちゃったせいで色々壊れている、修正の気力が出ないのでこのままにします…🙇‍♂️）（本名載っちゃったけど、気にしない。）

羊の大号令 from ssuserb50a24

本章とまったく関係ないこと書く、レギュレーション違反をしますが、スライドでも言及した通り、テトリスの対戦相手を探しています。奈良高専内で最強のテトラーを探しています。*5

最後になりましたが、私の登壇をお聞きいただいた皆さん、また、このような機会を与えて下さったTalkCafé運営の皆様に、この場を用いて感謝申し上げさせていただきます。ありがとうございました。

第２章　高専の課題の流儀

皆さん、課題は面倒ですよね。楽してやりたいけど、人のを転写するのは気が引けますよね。安心してください。楽する方法があります。

繰り返し作業は最適化しろ
似ている部分はテンプレートにまとめろ
面倒な部分の10割は楽なルートが存在する

1.は単純。繰り返し作業は最適化しよう。例えば、エクセルでマクロを組むなど。

2.も単純。レポート書くときとかで、体裁を毎回指定してるくらいならテンプレートを作ろう。

3.も単純。面倒だな～って作業をググって見たら簡単なルートが存在するはず。トリッキーな方法も慣れれば楽にできる。

え、簡単に言うなって顔しているな。ああ、もちろん簡単ではない。つまり、楽するためには面倒なことをしようってことだ。課題の作業を面倒ながら毎度やるか、課題の楽なルート作りを面倒ながらやるか、どっちが良いかな。

第３章　ケモ

なんですかこれは。誰がこんなことを。

はい、私はケモノチックなものが大好きです。登壇で羊かわいい言いまくってので想像に難くないと思います。あ、ズーフィリアとかケモナーとかではありません。これだけははっきりと真実を伝えたかった。

高専には多種多様な人が居るはずなので、ケモノが主に好きな人居るだろうって考えてましたが、ええ、観測者0人です。*6

私は、物心着く前から「トムとジェリー *7」「ジャングル大帝 *8」「ポケモン *9 *10」とか言う、いわゆる「人間以外の生物に焦点を当てた系コンテンツ」に囲まれた人生だったので、そりゃ嗜好も歪みますよ。今でも、研究室の席の後ろのクソデカホワイトボードにその系統の絵を描きまくってます。（ごめんなさい）さらに机には沢山のぬいぐるみが居ます。癒やしです。（写真はそれら一例、まるで子どもの落書き）

f:id:nishinoyama:20211202005457j:plain

f:id:nishinoyama:20211202004152j:image

ケモノ(furry)と言っても、ひと括りには出来ません。例えば獣100%のferal*11から、獣人半々くらいのanthro*12、ほぼ人型のhumanoid*13まで大雑把に区切られます*14 *15。詳しくはピクシブ百科事典などをご覧いただければ（一応、閲覧注意）

結構、人を選ぶようなコンテンツですが、私はズブズブハマっていきました。特に、ツイッターを始めてから…世界が…広がって……ほんと………おかげ…さまで…………あぁ…………………（懺悔）

ゴリゴリ書いていきたいが、これ以上はいけない。切り離した。ほんと、いけない。それでも見るって方は、私の記事一覧からどうぞ。こうかい　しませんね？

第４章　数学の何か

数学なんてひと括りにするんじゃ無かった…（後悔）

何も思いつかない、数学パズルコンテストこと、競技プログラミングの話に置換するか（最悪）

私はAtCoderで黄色（Top 3%）になれるくらいは競プロ力はあります（些細な自慢）。まあ、それまでですけど。（厚顔）それにこのカレンダー、二日前にも競プロの話してました（執筆時に確定した）が、知ったこっちゃありません。（言語道断）

実力の上げ方ですが、自分が解ける最難関の問題を沢山解きましょう。十分考えたうえで解けないなら解説を読みましょう。解説が理解できない？それは実力が足りていないのでしょう。その問題に挑むには早いです。後回しにしましょう。日を空けるのも手。

これだけじゃ面白くないな、何かのデータ構造の解説しようかしら。

区間クエリ

区間クエリについて、お話しします。問題です。（唐突）

長さ $N$ の数列 ${a_n}$ が与えられる。以下のクエリ（指示）を $Q$ 回応じよ。

$l,r ( 1 \leq l \lt r \leq N )$ が与えられる。 $\sum_{i \in [l,r)} a_i$ *16を求めよ。

制約： $1 \leq N, Q \leq 10^6$ 、 $a_i$ の絶対値は $10^9$ を超えない。

いわゆる、区間クエリを求める問題です。もちろん、クエリごとに総和を求めて…なんてはやってられません。時間計算量 $O(NQ)$ です。クエリの解答を楽する方法を考えましょう。足し算の逆は引き算ですね。じゃあ、区間に対して、その区間を構成する２つの区間に分解してみましょう。

$\sum_{i \in [l,r)} a_i = \sum_{i \in [1,r)} a_i - \sum_{i \in [1,l)} a_i$

おお、どれも1から始まる区間に落とし込めました！つまり、 $s_n = \sum_{i \in [1,n)} a_i$ たる $s_n (1 \leq n \leq N+1)$ をあらかじめ求めてやれば良いことになります。これは、単純な*17 動的計画法で線形時間 $O(N)$ で求められます。後は、クエリごとに $s_r - s_l$ を求めるだけなので、各クエリの計算量は $O(1)$ 。よって全体の計算量は $O(N+Q)$ で求められます。

素晴らしい！これは累積と呼ばれるテクニックです。

区間クエリ+一点更新クエリ

続いて、先程の問題に次のクエリも追加しましょう。

$n, a ( 1 \leq n \leq N)$ が与えられる。 $a_n$ を $a$ に変換せよ。

いわゆる、一点更新クエリを追加しました。累積テクニックが通用しなくなります。更新点 $n$ が1に近いほどど影響を受ける $s_n$ の数が増えます。具体的には、きっかり $N-n+1$ 個。このままでは更新クエリの計算量が $O(N)$ となり、全体の計算量が $O(QN)$ となってしまいます。 $s_n$ にテコ入れをしましょう。 $1,2,4,8,16, \ldots$ の長さの区間を管轄するものを想像してください。図の例は $N=16$

f:id:nishinoyama:20211201211200p:plain

お、 $s_1,s_2,s_4,s_8,s_{16}$ の時は楽に求まるようになりました。でも、 $s_{15}$ とかは、 $s_8$ までは楽できますが、 $a_9, \ldots a_{14}$ の値が必要になって楽できません。 $n=8$ のところでも楽出来るようにテコ入れをしましょう。

f:id:nishinoyama:20211201211618p:plain

このテコ入れで、 $n=s_9,s_{10},s_{12}$ のところも楽に求まるようになりました。このテコ入れを $n=2$ や $n=4$ 、 $n=10$ 、 $n=14$ のところでもどんどん適用してみましょう。

f:id:nishinoyama:20211201211840p:plain

なんかきれいな感じになりました。これで $n$ がどんな値であっても、適当に管轄する区間を選べば、 $s_n$ を高速に求めることができます。やった！

本筋に戻りましょう。必要なものは一点更新でした。ある地点の更新を可視化してみましょう。例えば $n=5$ の更新ならば、

f:id:nishinoyama:20211201212509p:plain

こんな感じに、それ程多くない区間が更新されることになります。これだけ少ない更新で済むならば、一点更新クエリもさばけます！

したがって、このデータ構造を用いることで、計算量 $O(N+Q \log N)$ で問題を解くことができました。これはFenwic Treeと呼ばれ、頻出なテクニックとされています。

区間クエリ（逆元なし）

ここまでよく読んでくれました。まだ続きます。区間クエリを総和から最大値に変更します。

$l,r ( 1 \leq l \lt r \leq N )$ が与えられる。 $\max_{i \in [l,r)} a_i$ *18を求めよ。

$s_n = \max_{i \in [1, n)} a_i$ としても、任意の区間の最大値は求められません。 $s_r - s_l$ みたいなことをしたいですが、逆操作ができないのです。悲しい…

でも安心！Fenwic Treeを思い出して！あれ、隙間空いてたじゃん。そこを埋めてみると何か見えそうです。

f:id:nishinoyama:20211201214012p:plain

適当な区間、今回は $l=6, r=16$ なんか試してみましょう。

f:id:nishinoyama:20211201214325p:plain

ん、誰が一番下だけでやれっつった。

f:id:nishinoyama:20211201214450p:plain

もう少し、上へ

f:id:nishinoyama:20211201214530p:plain

よしきた！クエリ処理がだいぶ楽できました。それぞれ選ばれた区間の最大値を求めれば、区間クエリに解答できます。

と、上の通り、クエリ処理が少し大変ながら、一つ一つ求めるよりかは遥かに楽に求めることができます。一点更新のクエリも簡単にできます。（図は省略）

これにより、任意の区間を逆操作なしで求めることが出来るようになりました。問題も $O(N + Q \log N)$ 時間で解けます。これはSeg Treeと呼ばれ、上級問題で必須とされるテクニックであります。

区間クエリ（木）

さて、今宵のラスボスは、木の上での区間クエリです。解いてみましょう。問題文です。

頂点数 $N$ の無向木 $G$ が与えられる。 $G$ の各頂点 $i (1 \leq i \leq N)$ には $a_i$ の値が書き込まれている。以下のクエリを $Q$ 回応じよ。

$s,t ( 1 \leq s, t \leq N )$ が与えられる。木の頂点 $s$ から頂点 $t$ への道にある頂点（端点を含む）の値の最大値を求めよ。

$n, a ( 1 \leq n \leq N)$ が与えられる。 $a_n$ を $a$ に変換せよ。

制約： $1 \leq N, Q \leq 10^5$ 、 $a_i$ の絶対値は $10^9$ を超えない。

「木」なので、素直に１列に並んでくれません。悲しい。

f:id:nishinoyama:20211201220427p:plain

普遍な木ですね。木を分解して、少しいじめてやりましょう。左上の頂点を根とし、一番重そうな辺*19をどんどん選んでいきましょう。

f:id:nishinoyama:20211201220531p:plain

残った部分木にも同様に適用しましょう。

f:id:nishinoyama:20211201220817p:plain

お、緑の区分だけで見ると、１列に並んでいますね。SegTreeにでも乗っけちゃえ。緑の区間は好き勝手出来るので、木でも問題なく区間クエリを高速に処理できそうです。

ところで、この木の分解は、高々 $O( \log N)$ の深さになります。証明は難しいです。*20 *21

従って、この問題は $O(N \log N + Q \log ^2 N)$ で解けました。

「Heavy-Light分解」、ちぢめて「HL分解」と呼ばれるテクニックです。実装は大変です。これをスクラッチ実装できる人は尊敬しますので、完成したらご一報ください。大いに崇めさせていただきます。

ここまでの話ですが、むっっっっちゃくちゃ代数学を裏で使ってます。区間クエリは結合律を満たすものに対して効率的に求められます。「群なら累積やFenwick Treeで任意区間を求められる。」「群から逆元がなくなったモノイドでも、Seg Treeで区間クエリをさばける。」など、数学の知識が使われる現場に当たった今、数学を勉強するべきだなって少しでも感じてくれたら嬉しいです。

総括

いかがでしたか？

何もテーマが定まってないやつが記事を動的に書くと記事の内容が意味不明になることが分かりました！貪欲は身を滅ぼします。執筆に数日かかってます。4つの相反するテーマを一つの記事に纏めるようなバカは私が最初で最後になることを願ってます。

つなぎ

明日の記事は「カラス式リーダー論」です。むっちゃ尊敬している同級生による発表です。楽しみにしています！

*1:TalkCafe#3 と高専カンファレンス初風。カンファレンスの方はアーカイブが残っていますので探してみてください。

*2:その時のTalkCafeでのLTは競技プログラミングと再帰に関するもの。結局数学。

*3:User blog:Kyodaisuu/Upper bound of Graham's number in fast-growing hierarchy | Googology Wiki | Fandom

*4:「脳内に映し出された頭の「ひつじたち」。これは夢なのか、現実なのか…。残暑の秋、寝苦しい夜、加速した「ひつじかぞえ」はついに危険な領域へと突入する。」なんて表現は

*5:実力は40Lineの時間から察してください。プレイできるプラットフォームは「ぷよぷよテトリス（PC版、無印）」か「TETR.IO」です。

*6:単純に未観測なだけの可能性は大。我こそはって方はこっそり教えてね。

*7:VHSで死ぬほど見た。ライオンの回とか、ネズミ捕り必勝法とか、100万ドルのやつとか脳裏に焼き付いてる。

*8:映画が心に刻み込まれている。どの映画だったかが名前が出てこない。調べてたら、おそらくテレビでやってた長編スペシャルアニメっぽい。参考：ジャングル大帝 - 勇気が未来をかえる -｜アニメ｜手塚治虫 TEZUKA OSAMU OFFICIAL

*9:特に外伝作品。レンジャーとかトローゼとかポケダンとかポケパークとか。今はクリスタルやってますけど。

*10:大体こいつらのせい。今ではマッスグマとか愛しい。パルキアのかわいさに気づく（ぱるぱるぅよりも、フォルム。）

*11:野山をかけめぐる系、モンスターハンターのモンスターとか、リトルポニー(MLP)とか

*12:例としてズートピア、アニマルクロッシングとか

*13:もののフレンズとか、ウマなんちゃらはこれ？触ってない作品なので直接的な言及は控える

*14:humanoidはfurryじゃない派だけど

*15:え、なんで急に英単語かって？勘が良いですね。日本のサイトだけじゃ満足出来ない身体になってしまったんですよ…

*16:つまり、 $a_l, a_{l+1}, \ldots , a_{r-1}$ の総和

*17:「単純な」「有名な」「簡単な」みたいな言い回しは、それを知らない人にとってはキツい言葉に感じる人もいることを知りました…ちゃんと解説すると、 $s_1 = 0, s_{n+1} = s_n + a_n$

*18:つまり、 $a_l, a_{l+1}, \ldots , a_{r-1}$ のうちの最大値

*19:部分木の頂点数が最も多くなるような辺の選び方

*20:そうでない証明だと直感的に嫌な気分になります。

*21:直感的には最もく深くなる最悪ケースは完全二分木ですが、どうですか、数強さん。合ってます？

はじめに

第１章 羊登壇の裏話

第２章 高専の課題の流儀

第３章 ケモ

第４章 数学の何か