【でぶ Advent Calendar 2022 Day23】でぶになります

この記事はでぶAdvent Calendar 2022 23日目の記事です。
(ほぼ)ネタ記事です。

経緯
やったこと
- Day1
- Day2
- Day3
- Day4
- Day5
結果発表～～～～！！
おまけ
- アルゴリズム
- 競プロでの用途

経緯

・親に久しぶりに会ったら痩せすぎと言われたのでもうちょっと太ろうと思った。・shojin_debuさんはどのくらいこの世界を占めているのかを自分の身で実感したかった。

やったこと

期末考査期間中、毎日不健康そうなものを食べる。不健康なものをたくさん食べればきっとでぶになれるだろう！

Day1

試験科目: 漢文数学A 家庭科
食べたもの:マクドナルドの15ピースチキンナゲット,ポテトM,スプライトM
感想:イギリスは20ピースだったので少し物足りなかった。これでは太らないのでは。

Day2

試験科目: 地学英語1 古文
食べたもの: 吉野家のチーズ牛丼
感想: ひよって並を頼んでしまい、お腹は満たされなかった...
(写真忘れた)

Day3

試験科目: 物理数学B
食べたもの: らーめんいっとくのつけめん
感想: 麺が好みの中太でおいしかった。おすすめです。
(写真忘れた2)
宣伝

Day4

試験科目: 公民技術
食べたもの: 馬場壱家風の陣のラーメン
感想: スープ濃いめに初挑戦したところ結構重かった。相変わらずばばいちのスープはうまい。かなりお腹が満たされた。
宣伝

Day5

試験科目: 英語2 国語
食べたもの: 焼肉ライクミックスカルビセット
感想: それなりの量の肉に白米おかわり自由で1050円というコスパの良さに感動した。お米がかなり進んでお腹がかなりいっぱいになるくらい食べた。

宣伝

結果発表～～～～！！

予想通りではあったが5日間では別に太らなかった...
試験期間にもかかわらずワールドカップを見まくっていて生活習慣が破滅し、同時にこの5日間で(どちらかといえば)不健康なものを食べたせいでかなり大きな口内炎ができた。
最悪です。今もまだ残っててつらい....

おまけ

競プロにおいて、メモリ制限は軽視されがちな制約です。(実際ないようなものである場合が多い)
しかし、現実世界では痩せられなくとも競プロでメモリ節約できればダイエット成功とみなすことができるので、今回はそんなメモリ節約に関するアルゴリズムを一つ紹介してみなさんのダイエットに協力します！
そのアルゴリズムというのはフロイドの循環検出法です。別名 The Tortoise and Hare Algorithm。
単方向連結リストのような構造やFunctional Graphの循環を検出するアルゴリズムです。
競プロでも有名なワーシャルフロイド法と同じ人が発案したアルゴリズムなので同じ名前がついていますがアルゴリズム自体は全く別物です。

アルゴリズム

今回は競プロでよく出るFunctional Graphであると仮定します。また、 $N$ を頂点数であるとします。
関数 $f$ を行く先の頂点を返す関数とします。
また、 $a_0$ を任意の頂点にして $a_{i+1}=f(a_i)$ として、ある頂点の列を考えます。
今回やりたいループ検出の愚直な方法として、この列の要素を $a_0$ から順にいちいち記録していって、同じ要素が出るまで探すというものがあります。これは空間 $\mathcal{O}(N)$ かかります。
しかし、今回のアルゴリズムではなんと空間 $\mathcal{O}(1)$ しかかかりません！
注目するのは $a_i=a_j$ が成り立つとき $|i-j|$ はループの長さの整数倍となることです。①(証明略)
フロイドの循環検出法では2つのインデックスをもって一方のインデックスを1ずつもう一方を2ずつ増やしてゆき、一致する場合を探します。
インデックスを増やしていくのを繰り返すとある時点で $a_m$ $=$ $a_{2m}$ となり、①より $2m-m=m$ のある約数が循環の長さになります。
この一致が見つかったあと、ループの長さは愚直な方法と似た感じで $m$ から1ずつ増やしていって $a_m$ と一致したときのインデックスと $m$ の差がループの長さとなり容易に特定できます。
このアルゴリズムは実際に空間 $\mathcal{O}(1)$ であることがわかります。