09/30(月)

午後3時起床。半からインターン先定例会に出席した。

先週・先々週の月曜日がどちらも祝日で、09/17(火)に振り替えられた回もセミナー聴講のため欠席したので、3週間ぶりである。昨日の朝方の調べもので分かったことを進捗報告で話し、手詰まりとなった部分について質問した。後者も実質的には現状報告のつもりだったのだが、ちょっと画面を共有したら他の人からたちどころに有望そうな回答が得られて大変ありがたかった。

勉強会はMo's Algorithmの話。このアルゴリズムに関しては、区間を任意に縮められなくてもrollbackさえできればオーダーが変わらないという話が好きなのだが、ちゃんと発表資料に盛り込まれていて嬉しかった。というかそれをメインとしたブログに基づく発表だったらしい。

snuke.hatenablog.com

解散後はずっと週記を書いていた。日付が変わる直前に投稿。読んだラノベの感想は逐一書いておいたので、そこで悩み手間取ることはなかったのだが、結局間に合わずUniversal Cupに加えてAGCも穴あきになってしまった。

日付が変わり、月も変わって10月。毎月1日の楽しみであるフォッ毛さんの動画が今月はツイートされず、残念だった。お忙しいらしい。

pic.twitter.com/OAEM1fhInr
— フォッ毛 (@Focke_3) 2024年8月31日

午前1時過ぎ就寝。

10/01(火)

午前9時起床。数時間ほど布団でゴロゴロひながらスマホを触っていた。昼前になって起き出し、シャワーを浴びた。

学食に行こうと思ったが正午を回っている。秋学期初日ということで殺人的な混雑が予想されるため、履修を決めて時間を潰すことにした。講義をチェックして来週行われる基礎論の集中講義を登録。春学期に2単位取ったので、もしこれの単位が出ればそれ以降博士課程で講義を取る必要はなくなる。

博士課程では20単位取る必要があるが、そのうち16単位は研究と博論で自動的に埋まる。つまり残りの4単位だけ考えればよい。
週記（2024/04/15-2024/04/21） - kotatsugameの日記

いつの間にか1時間経過していた。慌てて原付で出発し、生協に行く前にガソリンスタンドで給油した。今日は天気が良く、またこの時間帯は道が空いているらしくて、走っていて非常に快適だった。その後学食で食事し、購買でラノベを買って帰宅。

9月の読書記録をツイートした。上旬ハーメルンに集中していたぶんを、ある程度下旬で取り戻した月だった。

9月の集計
買った：33冊
読んだ：26冊
積読：+7冊
積読（累積）：+148冊
— こたつがめ (@kotatsugame_t) 2024年10月1日

メールを出す必要があるが、文面を考えるのが嫌すぎてしばらくラノベに逃避していた。4時間ちょっとかけてなんとか送信し、あとは寝るまで久しぶりにセミナーの準備をした。午前2時半就寝。

TCBの2024/09回が終了していた。ズルしまくって理論値-105ptで優勝。ここに感想を書いておく。

https://techful-programming.com/techful/event/6380

5問目まではよい。6問目のカウントはイベントソートで行った。7問目は、次数2の頂点を削除し続けて最終的に2頂点1辺のグラフが得られるかをチェックすればよいらしい。実はわからなかったので「maximal outer planar graph degree」でググった。次数列に関する条件そのものではなかったが、解法になっていると気づけてよかった。

math.stackexchange.com

8問目は正直わからず、 $O(N(N+Q))$ で通した。といっても $x$ ごとにBFSでdistを求めると定数倍が悪すぎる。そこで頂点をオイラーツアー順に並べ、木を潜ったり上ったりしながらdistを差分更新した。これなら区間に対するインクリメント・デクリメントだけで十分であり、ベクトル化が効きそうな書き方をしてQCFium法を入れれば通る。

9問目は答えをセグ木状のノードで管理する。各ノードに対し対応する区間が削除されたかどうかを持つ必要があるため、セグ木の中身を弄る必要があった。実装に手間取って20分かかり、-2pt。

10問目はパスを構築しながら左からdp。マス $i$ を見ているときは、 $(1,i-1)-(1,i)-(2,i)-(2,i-1)$ という3辺がそれぞれ使われているかに加え、構築済みのパスが非連結か、すでにパスが完成したかなどが分かればよい。上下で対称なので自分は8状態になった。ただし数え上げるのはパスではなく $X$ なので、8状態のどれがvalidかを持つbitdpをすることになる。状態の設計で混乱しまくって56分かかり、-35pt。

11問目は円周上に原点に加えて少なくとももう1点乗る。これを点 $A(\vec a)$ とすると、線分 $OA$ の垂直2等分線上に円の中心が来て、ほかの各点 $B(\vec b)$ についてどの区間に円の中心があれば点 $B$ が円の内部に入るか分かる。これを計算してイベントソートすればよい。

詳しい式をメモしておく。3点 $O,A,B$ を通る円の中心を $C(\vec c)$ として、 $\theta=\angle AOC$ 、 $\varphi=\angle AOB$ （ただしどちらも符号付き）とおくと、 $|\vec c|\cos\theta=|\vec a|/2$ 、 $|\vec c|\cos(\varphi-\theta)=|\vec b|/2$ が得られる。連立して解くと $|\vec c|\sin\theta=\frac{|\vec a|(|\vec b|^2-(\vec a\cdot\vec b))}{2(\vec a\times\vec b)}$ となり、これは線分 $OA$ の垂直2等分線上の座標になっている。区間がどちら向きに広がっているかは $\varphi$ の符号による。

果たしてそこまでする必要があったかはわからないが、この式を使えばイベントソートまでは誤差なしで行うことができる。 $\varphi=0$ のケースに注意。また線分 $OA$ が円の直径になるケースも同時にチェックする必要がある。

分母の $2$ を見落としてしまい、サンプルを合わせるのにかなり長い時間を消費した。そもそも説明の図が間違っている。3点 $(0,0),(41,2),(39,33)$ に外接する円の面積は $2050.3936\dots$ となるようだが、計算ミスしたコードは $2051$ を出力していて、floorを取った値としても異なることになかなか気づけなかった。

さらに、円の面積のfloorをlong longで管理したらオーバーフローして1WA、long doubleで管理して出力時にfloorを取ったら小数の出力になってもう1WAしてしまった。80分かかり-68pt。

12問目は挿入dpの $O(N^2)$ が容易に通る。QCFium法すら必要ない。かなり念入りにチェックしても7分だった。

10/02(水)

午前7時前に起床。それから夕方まで、3時間ちょっとの二度寝を挟みつつずっとハーメルンを読んでいた。

「【書籍化】異世界転生したのでマゾ奴隷になる」を読了。面白かった。序盤は主人公の変態性が押し出されていたが、話が進むにつれてその超人っぷりが目立つようになった。この作品の「英雄」のような、強さで一般人との間に明確に壁を設ける設定は好み。たいてい物量にすら負けないので、壁を越えていない敵からは害されないという安心感がある。

syosetu.org

午後6時前になって布団を脱出し、シャワーを浴びて学食で食事した後、セミナー準備を開始した。午後9時に一旦資料を送信し、追加で2時間ほど取り組んで完了。その後ラノベを読んだ。

「カードゲームで世界が滅ぶ世界に転生してカードショップを開店したら、周囲から前作主人公だと思われている」を読了。好きなハーメルンの書籍化。面白かった。ホビーアニメ一般を念頭に置いた話であり、キャラの容姿もそのように設定されていたが、かなりかっこいいイラストがついた。装丁にもどことなく高級感があり、子供っぽさは一切ない。

TCGがメインなだけあって、専門用語が説明なしにどんどん出てくる。TCG一般で使われるものだけでなく、特定のゲーム、具体的にはデュエマと遊戯王の用語もいくつかあった。「サモサモキャットベルンベルン」が当作品の設定の一部と似ているという話があったが、ちょっと調べただけではよくわからず残念。

セミナー準備で読んでいた論文に、与えられた森を含むラベル付き木の数え上げ公式が載っていた。競プロの問題の解説で見覚えがある。どの問題だったかツイートで聞いて、rniyaさんに教えていただいた。自分の直観とはあまり合わない形だが、プリューファーコードの作成手順を見直すと、与えられた森の各連結成分についてそれぞれ1本だけどこから出たか記録できない辺があることが分かり、納得した。

森のk個の連結成分がそれぞれサイズn_1,...,n_kだったとき、場合の数は(n_1+...+n_k)^{k-2}*n_1*...*n_kになるらしい
— こたつがめ (@kotatsugame_t) 2024年10月2日

P - Bridge Elimination

シャワーを浴びた後もう一冊ラノベを開き、うつらうつらしながら読んでいた。午前5時半就寝。

10/03(木)

午後0時半起床。地下鉄で登校して学食に向かったらホスフィンと遭遇し、一緒に食事した。

午後1時半からセミナー。今日は8月末に数値計算で出した結果について話した。このセミナーに参加してくださっている先生方とは、9月中もメールで報告と多少の議論を行っていたので、結果そのものではなく周辺の話がメイン。それらは論文にも書く必要があるから、今日の発表資料はその下書きのつもりで作っていた。

先月からチャレンジしていたことだったので、何とか結果が出てくれて非常に嬉しい。
週記（2024/08/26-2024/09/01） - kotatsugameの日記

午後4時に終了し、院生室に移動してしばらく駄弁った。麻雀を打つメンツがいない。明日なら人が集まるとのことなので、自分も登校することにした。また、金曜2限の講義に参加する人が何人かいたので、覗きに行ってみる予定。

理学部合同棟の院生室から人を呼んでくる算段がついた。午後6時過ぎに一緒に学食で食事した後、麻雀を2.5半荘打った。

1回目の半荘はひたすらツイていて、高い手のツモ上がりを何度も繰り返した。高い手といっても見栄えのする役を決めたわけではなく、リーチ・ツモ・タンヤオ・ピンフ・ドラの複合である。たまたま前者四つが揃ったときは、手牌に綺麗なパターンがあるわけでもないのに4翻・5200点も貰えて驚きだった。大きな振り込みが1回あったがそれまでの稼ぎで耐え、ギリギリ1着。

ところが2回目の半荘の途中、大きな手を自分の振り込みで逃してから雲行きが怪しくなった。聴牌までたどり着けはするのだが、他の人に先に上がられてまったく勝ちきれなくなってしまったのだ。何度か直撃ももらってしまい、4着。

もう1回半荘を打つ時間はなかったが、最後に東風戦を行った。ここでも4着。ツキとか関係なくただ自分が下手くそだった。急いでいる状況下では「萬子がたくさんあるから来たら全部持っておこう」「索子は数が少なく散らばっているから全部捨てよう」みたいな大雑把なとらえ方しかできず、最終的に出来上がるのはまとまっていない中途半端に染まっただけの手。これでは聴牌すら覚束なかった。

午後11時過ぎに帰宅。ハーメルンを開いたら読み進める手が止まらなくなってしまった。午前6時前後に30分ほど椅子の上で寝ていたらしいから、そこで日記の日付を変えることにする。

10/04(金)

椅子で寝落ちしたので布団に移動したが、なぜか眠気が遠ざかってしまった。ハーメルンを読み続け、午前9時半くらいに家を出て地下鉄で登校した。

2限は午前10時半から正午まで。この時間帯の講義に参加するのはかなり久しぶりである。序盤は熱心に聞いていたが、途中から眠気が襲い掛かってきて大変だった。講義後、後ろに座っていた後輩に「途中寝てましたね」と指摘されてしまった。全然耐えられていなかったらしい。

学食で昼食を摂り、午後1時。麻雀は夕方からだと思っていたが、もう暇人が4人集まったので始めることにした。牌の音が廊下に響かないことは確認済み。午後6時までで2半荘打ち、1回目はたしか2着、2回目は1着だった。字牌を整理し終えたら手がまとまっていたという運だけプレイが多い。しかし昨日の経験も踏まえ、何となくわかってきたことはある。

まず、役牌は速くても強くない。タンヤオもピンフも消えるし、鳴いたらリーチまで消えてしまうから。そこで字牌をどんどん切っていくと、たくさんある牌を数牌だけに圧縮することになるため、くっつきやすくなって聴牌がかなり近づいた。あとは名前だけ聞いたことのあった「5ブロック打法」というのも意識してみた。

学食で食事し、少し友人の数値計算の手伝いをして、午後7時に帰宅。ハーメルンを読んだり日記を書いたりして午後11時過ぎに寝た。

10/05(土)

午前8時起床。ハーメルンを読んだ。

「ようこそ俺小路くんの無念を晴らす教室へ」を読了。

syosetu.org

続いて「よう実RTA　決闘者チャート」を読了。

syosetu.org

書く

午後4時くらいに二度寝に成功したものの、30分くらいしてドリルのようなとんでもない音が部屋中に響き渡り、飛び起きた。自分の部屋に原因があるのかと心配したが、音の聞こえる方向を調べたら部屋の外からのようだったので安心。音はしばらく続いて止まった。

しかしこの出来事で眠気はすっかり消えてしまった。またずっとハーメルンを読んで過ごし、午後9時からABC374に出た。

KEYENCE Programming Contest 2024（AtCoder Beginner Contest 374） - AtCoder

書く

www.youtube.com

ハーメルンにのめりこんで動画の投稿作業ができなかった。上の動画は次のコンテスト後に公開したものである。午前2時からMHC Round 1。

Meta Hacker Cup - 2024 - Round 1

書く

ABCの動画を公開して、午前7時就寝。

10/06(日)

午後0時半起床。2時間ほどハーメルンを読んだ後、布団を出てシャワーを浴び、午後3時からCF #977 div.2に出た。

Dashboard - Codeforces Round 977 (Div. 2, based on COMPFEST 16 - Final Round) - Codeforces

書く

www.youtube.com

午後7時過ぎ地下鉄で街に出て、立ち食いそばを食べてゲーセンに入った。それから閉店までで25クレプレイ。

先週木曜日、チュウニズムに名取さなさんのオリジナル曲「モンダイナイトリッパー！」が追加された。非常に好きな曲だし、譜面の難易度もちょうど良く、気持ちよくプレイできた。MASTERもULTIMAも手をバタバタ交互に上げ下げさせる配置がある。ご本人のショート動画で見た覚えのある動きで、もしやと思っていたらULTIMAのSSS称号がまさにその動画のタイトルだった。元ネタに気づけて嬉しい。

譜面、やっぱりこれの再現だったのか pic.twitter.com/oKV5Rfm6ZB
— こたつがめ (@kotatsugame_t) 2024年10月6日

www.youtube.com

同日に追加された「マシンガンポエムドール」のAJを出した。35連奏。といってもこんな体力譜面を続けざまにプレイしていては身が持たないので、半分くらいは途中で捨てゲーしてしまった。ただ速いだけでなくしっかり指押しを要求してくる配置もあって非常に難しかった。譜面定数14.9らしいが納得。先週niconicoジャンルの全譜面のスコアを98↑に乗せたばかりだったので、ギリギリ維持できてよかった。

マシンガンポエムドール　AJ pic.twitter.com/6VjEpXClOx
— こたつがめ (@kotatsugame_t) 2024年10月6日

油そばを食べて日付が回ってから帰宅。そのまま朝方までハーメルンを読んでいた。シャワーを浴びて日記を書き、午前7時半就寝。来週は集中講義の週である。