週記（2024/10/14-2024/10/20）

10/14(月)

午後5時起床。今日は祝日だが大学の講義は休みにならなかったようで、大学生協も変わらず営業している。学食で食事して購買でラノベを受け取り、帰りにコンビニに寄ってきた。

先週の週記を書き進めて午後11時過ぎに投稿。またしてもスカスカである。先週・先々週は読んだハーメルンの感想すら埋まっていなくて大変。「よう実」の二次創作ばかり読んでいたので、どの話がどんな展開だったか頭の中で混ざってしまった。

午後11時半からECR170。

Dashboard - Educational Codeforces Round 170 (Rated for Div. 2) - Codeforces

Aはコピーは高々1回。sとtのLCPを求める。LCPの長さが0のケースではコピーする必要がないことに注意。Bは表を書くと2^kだとわかる。k=nのケースがないのはかなり優しい。Cはソートして尺取り。

Dは片方の現在のレベルを持つdp。ポイント獲得時はO(m)かけて更新してよい。それ以外は区間インクリメントになるので、imos法で処理する。ポイント獲得の度にまとめて反映しても変わらずO(m)で処理できる。

Eはスートごとに、先手がカードを何枚持つかを状態としてdpする。後手に勝つような出し方があるかは、カードをランクの昇順に見ればチェックできる。O(m^2)でdpした後、スート2\dots nの分としてn-1個畳み込むと、後手が何枚余らせるかわかるので、そのO(m)通りそれぞれについてスート1に関するdpを行う。合計O((n+m)m^2)。

Fは\pm 1を後から決めてよく、このときインデックスごとに+1と-1を交互に行うのが最適だから、各インデックスをできるだけ偶数回操作するのが目標となる。これは辺(x,y)を集めて作ったグラフにおいてEven Degreesをすればよい。

B - Even Degrees

Gはa+bラウンドで1ダメージ食らうと解釈するのが良い。これをヒーローhと防具dそれぞれの寄与に分解すれば、ペア(h,d)に対してラウンド数がh+\min(h,d)だけ伸びると分かる。最大化するためにはhとdを降順に並べてマッチングしていくのが良い。しかしこれでもまだ計算は難しい。

ここで、h+dから損する分d-\min(h,d)を考えてみる。この値を数直線において区間[\min(h,d),d)に対応させ、幅1の区間c_i=[i,i+1)にバラすと、実は次のようにして計算できる：すべての防具について[0,d)に+1、すべてのヒーローについて[0,h)に-1したとき、\max(c_i,0)の総和。これは平方分割で計算できる。

Gのoff-by-oneで配列外参照を起こし、3回ほど37ケース目で落ちることを繰り返したが、ギリギリ時間内に気づいて修正できた。全完6位。

www.youtube.com

ハーメルン「『パワプロ成長』でダイヤのA」を読了。面白かった。投手全振りだと思っていたらいつの間にか打撃も最強格になっていて爽快。原作のことは全く知らないが、特に問題なかった。

同じ作者の「二郎になりました…真君って何？」も読んだことがある。どちらも300話前後あるが、1話あたりの文字数が少ないので総文章量はそれほどでもない。話の内容・展開が結構あっさりしていて、重たいシーンや重要な見せ場などをさっさと通り過ぎていくのも共通。ある種の読みやすさではあると思う。

syosetu.org

午前8時就寝。

10/15(火)

午後4時過ぎに目を覚ましたら、JOI一次予選の第2回が公開されていた。気づくのが遅すぎてShortestもFastestも取りつくされていたが、Bだけ1B更新することに成功した。Nibbles。

JOI 2024/2025 一次予選 (第2回) 過去問 - AtCoder

布団に戻って2時間ほど二度寝したあとは、R18のハーメルンを読み漁っていた。四つばかり読了。

「無口無表情でダウナー系の幼馴染は僕の部屋でくつろぎすぎている──ダウナー系で隠れ巨乳美少女な幼馴染がオナニーしているところを見かけてしまってから、僕が彼女と生ハメセックスを繰り返す仲になるまでの七日間」。良かった。タイトルからして短くまとまりそうなのも嬉しい。もう少しで完結するのではないか。

syosetu.org

「一色開発日記」。設定・シチュエーションに興味を掻き立てられたが、ほとんど進展なくエタりかけているのが残念。

syosetu.org

「俗物な転生者が天竜人になるようです」。ワンピースの通常の二次創作として面白かった。ところで、そもそも自分はワンピースの原作キャラをそういう対象にするのが苦手な気がする。頭の中にあるデフォルメされた原作イラストとR18の相性が悪い。

syosetu.org

「多分子供向けTCG世界か何かに転生したっぽいが、俺だけ成人誌の世界なんだが？」。エロではなくグロのR18。まあそんなにグロくはなかった。3話でエタりかけているが、TCG世界の最強キャラとして非常に良い雰囲気が伝わってきた。

syosetu.org

午後10時過ぎに寝落ち。

10/16(水)

午前2時半起床。

昨日に引き続いて、R18ハーメルン「最強雌殺しチンポ持ちのマスター君がサーヴァント達をハメ潰しまくる短編集」を読了。1話1話が長い。またFateにおけるキャラのビジュアルを詳しく知らないのだが、かといって一次創作のように自分で自由に想像するのも違うだろうから、頭の中でどのようにイメージすべきかが難しい。

syosetu.org

今週末のUniversal CupはTUPC2023セットである。準備が大詰めを迎えており、自分も英語問題文のチェックで参加した。やはり読むのと書くのは大違い。競プロの英語問題文なんてこれまで大量に読んできたはずなのに、典型フレーズをちっとも覚えておらず、文章に違和感があっても修正案をうまく出せなかった。

午前5時くらいからセミナー準備を始めた。セミナー準備というか、前回資料の英訳。これも修論とは別のpreprintになる予定である。

午後1時過ぎに学食に行った。今日の麺メニューは「濃厚魚介つけ麺」。以前からある「黒胡椒つけ麺」はつけダレの粘度が低いが、こちらは濃厚の名に恥じぬとろみがついていた。粘度が高いほうが好みな自分としては非常にありがたいところである。

ラノベを買って帰宅。セミナー準備を続けようとしたが眠気に負け、3時間ほど仮眠をとった。起きてから再開し午後9時くらいに完了。セミナー参加者にメールを送信した。

ハーメルンを読んで、日付が変わるくらいに寝落ち。

10/17(木)

午前3時過ぎ起床。

ハーメルン「俺がカードゲームで無双できる都合のいい世界　〜カードゲームアニメの世界に転移したけど、前の世界のカード持ち込めたので好き放題します〜」を読了。面白かったが周囲のレベルからあまり逸脱しないように力をセーブしているのはちょっと残念だった。一家揃って転移してきたから、家族のことを考えると悪目立ちもできないのだろうと理解はする。

この作品オリジナルのTCGは、詳細なルール説明はなかったが、読んでいるとだんだんわかってくる。基本的には遊戯王っぽくモンスターの召喚・魔法の発動にコストが必要ない。さらに簡単にするためか、召喚権がターン1ではなく、さらに魔法の発動を任意のタイミングで（相手ターンでも！）手札から直接行えるようになっている。その分、モンスターゾーンは3体分しかない。

syosetu.org

セミナーについて、昨日はほぼずっと資料の英訳をしていたため、今日新たに話す内容がほとんどない。そこで追加の準備を試みた。数値計算によってある条件を満たすグラフのリストが手に入っているのだが、そのリスト全体で何か共通する性質がないかを探してみた。

これまでは一つのグラフに注目してできることをずっと詰めていたから、全体を見渡すのはやったことがなかった。さらに言えば、そのような性質は簡単には見出せないだろうと思っていた。ところが、試しに部分グラフの関係を見てみたところ、なんとリストのうちある一つのグラフが他のすべてのグラフを含んでいることが判明。ここから何がわかるかまだ不明とはいえ、かなり顕著な性質であった。

午前9時ぐらいから3時間半二度寝して、原付で登校。悠長に学食で食事する時間がなかったため購買でパンを買って食べ、教室に向かった。

午後1時半からセミナー。今朝の内容を話したがふーんという反応だった。自分でも今のところふーんとしか言えないので、まあそれはそう。あとはpreprintに何を書くべきかと、数値計算で得られたデータをどのように工夫して見やすく表示すべきかという点について助言をもらった。

2時間で終了。しかしそこで解散ではなく、それから後輩の発表を少し聞いたり、先生が担当するセミナー形式の講義に参加したりした。講義には10月から先生の下に来ている留学生も参加しており、挨拶した。去年と同じ半年だけの留学プログラムで、今年は後輩が留学生のチューターを担当している。

学食で食事して午後7時から麻雀を打った。2半荘でどちらも2着。上がった回数は少なかったが、高い手が多かった。日付が変わる前に帰宅。

家に帰ってからもフラッシュゲームで麻雀を打っていた。ツモれば四暗刻の手が舞い込んだのに先に上がられて残念、と思ってふと相手の手を見たら国士無双だった。これに負けるなら納得感がある。

シャワーを浴びて、午前4時前からYandex Cup 2024のQualificationを走った。参加できる期間が週記公開前に終わるので、ここに感想を書く。

https://contest.yandex.com/contest/69390

Aは算数で判定して二分探索。Bは左右から前計算しておく。Cは全部Lまたは全部Rに置換するのが最適。Dは上限を倍々で探索した後二分探索。そういえば去年のQualの最終問題は、Stern-Brocot treeの探索にこのテクを使うことで\logが一つ落ちるという話だった。運営はこれが好きなのか？Eは適当にdpしたら\lfloor n/2^i\rfloor-200から\lfloor n/2^i\rfloorしか出てこないという、正直親の顔より見たやつ。

まず二分探索の上限を指数探索で調べれば判定回数が全体でlog log 回になるらしい。自分の実装はおそらくここがlog log 二つになっていて落ちたのではないか。

週記（2023/10/23-2023/10/29） - kotatsugameの日記

Fは問題文に最適なクエリ回数が書いてあってありがたい。15クエリの最適な聞き方があって、それへの正しい返答を15bitの数だと思うと、1bitまでflipされて返ってくる。つまり答え一つに対して返答が1+15個存在するから、識別できる最大値は2^{15}/16=2048。よって0から2024を区別するにはほぼ理論上の最大値を達成する必要がある。

しかし非常にあっけなく見つかった。結論だけ言うと、15bitの数を小さいほうから探索して、1bitまでflipした数16個がすべて未使用だったら採用して16個を使用済みにするという方法で、互いに識別可能な2048個の数が見つかる。あとは正しい返答がこれになるようにクエリを定めればよい。

何も悪いことをしていないのにジャッジから-1が返ってくることがあるらしく、1REに加えてバグ探しで14分ロス。結局バグはなく、1ペナ支払ってREではなくWAになることを確かめようとしたら通ってさすがにひっくり返った。確かに、問題文を正確に解釈しようとすれば、ジャッジの気分次第で答えが返ってこないことがあると読めなくもない。マジで言ってる？

少し日記を書いた後、数値計算に取り組んだ。今日のセミナーで、求めたグラフのリストに平面グラフはなかったのかと聞かれたため、チェックしてみた。見つかった。まあ平面性が関係しそうな話は今のところ一切ないので、やっぱり部分グラフの話と同じく現状ではただ見つかったというだけ。

午前9時就寝。

10/18(金)

午後6時から2時間ほどの中途覚醒を挟みつつ、午後11時起床。そこから少しハーメルンを読んだら午前2時。起き上がって食事した。

朝まで数値計算と格闘していた。また一つのグラフに注目する作業。以前対象に選んだグラフについては決着がついたのだが、もう一つくらい例があっても良いかもと言われた。せっかくなので昨日発見した平面グラフを使うことにした。

しかしこれが全然うまくいかなかった。手法をあまり確立できておらず、以前もガチャを回したのだが、今回はそれ以前の段階で躓いている。延々試行錯誤していた。全探索のようなことも何度か行っており、小刻みに待ち時間が発生して、気を抜くとすぐダラダラしてしまう。

どうやら「当たり」のパラメータを引き当てたようだ。

週記（2024/08/26-2024/09/01） - kotatsugameの日記

その待ち時間で先週の集中講義の課題レポートに取り組んだ。講義資料にいくつか用意されたExerciseのうち二つ三つ解くという形式。せっかく先生にいろいろ質問しに行ったのだから、それなりに難しいものを選ぼうと思ったのだが、最初に選んだものがどれもポンポン解けてしまった。

とはいえ残っている問題のうち難しそうなものには手が出ないので、諦めて解けたものを書くことにした。今はとりあえずアイディアをメモしておくだけにして、後から清書する予定。ちなみにClassroomにはまだ課題の提出先が用意されていないため、締め切りがいつになるのかは不明である。

午前10時くらいになって寝ようとしたが、せっかくなので学食が開くまで待ち、生協でいくつか用事を済ませることにした。こちらの待ち時間ではラノベを読んでいた。

午前11時半に出発。すっかり秋だと思って長袖の上からパーカーを着たが、なんと今日は夏日らしい。非常に暑かった。食事してラノベを買い、散髪して帰宅。

シャワーを浴びて午後2時前に寝た。

10/19(土)

午後7時起床。昨日読んでいたラノベ「バスタード・ソードマン」4巻を読み切った。

このシリーズは主人公のしょうもない日常が良いという話を以前にした。しかし3巻ラストの衝撃を受け、それでは物足りなくなってしまった。4巻も戦争の気配が漂ってきて何かありそうではあるのだが、まだ何も起こってはいない。そもそも戦争が始まったとして、それに主人公が関りを持つともあんまり思えない。先行き不透明。

食事して午後9時からABC376に出た。

AtCoder Beginner Contest 376 - AtCoder

Aはよい。Bは算数をしたくなかったので愚直に数えた。Cは二分探索。Dは1\rightarrow uの最短経路と辺u\rightarrow 1に分解する。Eは\max Aを固定、正確には値Mであって\max A\le Mとなるものを固定すればよい。

Fはdpで、直前の操作によって状態数がO(N)通りになる。また遷移は手を時計回りに動かすか反時計回りに動かすかのみ。操作回数は頑張って算数するしかない。まあBを読んだ時点で、これは回避不可能だとわかっていた。場合分けとコピペが大量発生してかなり怪しかったがサンプルは一発で合い、幸いそのままACできた。

Gは何もわからず。頂点を探索する順番を長さNの順列Pとしたとき、すべてのiについてP_{p_i}\lt P_iであることが条件であり、また期待値は分母を除いて\sum a_i P_iになる。このPを探す問題。どうせ貪欲だろうと思ったが、自分が思いつく範囲では何をキーにしてもうまくいかなかった。

6完23位。コードゴルフはAのみ、Nibblesで書いた。scanl1を使って「直前に飴をもらった時刻」の列を作成し、重複を除いた長さを求める方針。

午後11時から、普段より30分早くCF #979 div.2。

Dashboard - Codeforces Round 979 (Div. 2) - Codeforces

Aは、b_2以降はすべて\min a、c_2以降はすべて\max aとできる。b_1=c_1なのでこれが最大。Bはf(s)=2^{n-1}-1とするべきであり、sを1文字だけ1にすることで達成できる。

Cは端に1があれば先手勝ち、途中に11があってもその間にANDを入れることで先ほどと同じ議論が回り先手勝ち。逆にそれ以外のケースは後手勝ちである。

DはLRで区切ってみると各成分の内部では自由に交換可能で、成分が異なると交換不可能である。pを見ると成分の区切りになってはいけない箇所が列挙できて、ダメな区切りがいくつあるか差分更新できるようになる。

書く

午前2時からはMHC Round 2に出た。

Meta Hacker Cup - 2024 - Round 2

書く

MHCはファイル提出のため余計なものが映り込む可能性が高く録画したくなかったのだが、ABCとCFの振り返りが間に合わなかったので、録画を中断してMHC後に30分ほど追加で録った。二つの録画ファイルを繋げて計5時間半の動画をエンコードするのに3時間くらいかかり、午前9時を回ってようやく公開できた。

www.youtube.com

今日も数値計算に取り組んだ。平面グラフはいくつかあるので、昨日のように一つのグラフに対して適用できる方法を探し求めるのではなく、一つの方法について適用できるグラフを探し求める方針にしてみた。するとめでたく発見。

実のところ、計算がうまくいきそうというだけで、本当に成功するかはもっと長い間待たなければわからないのだが、ともかく長い時間CPUをぶん回すフェーズに入ることができた。前回は7時間かかった計算を、今回はもう少し大きな入力に対して行う。果たしてどれだけの時間がかかるだろうか。

午後0時半就寝。

10/20(日)

午後5時半起床。午後6時からCF #980 div.1に出た。同時開催のdiv.2は、ついに到来したIDが2024のコンテストである。

Dashboard - Codeforces Round 980 (Div. 1) - Codeforces

書く

www.youtube.com

動画投稿を終えて午後9時半。それからゲーセンに向かい、閉店までで8クレプレイした。14+の「Trackless wilderness」と「Megameteor」のAJを出すなど成果は上々。この2譜面はもともとのスコアが低かったので、オーバーパワー的にも嬉しい。

ラーメンを食べて日付が変わってから帰宅。

数値計算が思ったより遅い。今回している入力に対してかなり効きそうな高速化ポイントがあったため、改善したものも同時に走らせることにした。

様子を見守っているうち椅子の上で意識を飛ばしそうになったので、慌てて布団に移動。午前2時過ぎに寝落ちした。

週記（2024/10/07-2024/10/13）

10/07(月)

午後2時前起床。今週は集中講義の週であり、月曜日の談話会は午後4時から始まるため時間に余裕がある。ゆっくり準備し、天気が悪いので地下鉄で登校した。購買で買ったパンを食べて川井ホールへ。

前半、眠気に負けてうつらうつらしていたら重要な定義を聞き逃したようで、談話会の主題っぽい部分が全然わからなかった。失敗。聞き取れた範囲では「連続論理」という、真偽値を0以上1以下の実数に拡張したものが面白かった。特に0に近いほうを真とすることで、論理式における等号の代わりに距離関数が使えるようだ。このとき量化記号\forall xと\exists xはそれぞれ\sup_xと\inf_xになる。

学食で夕食を摂った後、4人集めて麻雀。みんな忙しいようだし自分も先週の週記が全然書けていなかったので、東風戦1回だけとなった。ただし連荘が続いたため3時間ほどかかった。着順は2着だがトップの一人勝ちで、和了は1回だけ、持ち点は25000点を下回った。

一向聴くらいまでは安定して手が進むようになったと思う。最終局は4巡目くらいに聴牌して、そこから打点を高めてみようと手を崩しタンヤオを狙った。結果、残念ながら上がれなかったものの、一盃口もつけてリーチをかけるところまでは行けた。後から確認したらなんと雀頭が裏ドラだったので、5翻満貫の手になっていたらしい。まあこれを直撃させてもトップはまくれなかったのだが、打点を狙いに行って成功しかけたのはドキドキした。

午後10時前に帰宅。先週の週記は穴あきだらけのまま、体裁だけ整えて投稿した。日付が変わってからは延々ハーメルンを読み続け、午前7時くらいに寝落ち。

10/08(火)

正午起床。2時間ほどハーメルンを読んでから登校した。地下鉄を使ったのも購買でパンを買って食べたのも昨日と一緒。

午後3時から集中講義「モデル理論入門」。完全性定理については既習であることを想定すると言われ、すべてを忘却していた自分は震え上がったが、講義資料がかなり丁寧で事前知識もある程度カバーしてくれた。ただわからなかった点を先生に質問しに行ったら講義内容以前の基礎的な事項だったので、やっぱりダメかもしれない。今週は学部生のふりをしようかな……。

自分の質問とは別の話。モデルMとNについて、任意の論理式\varphiに対しM\models\varphiとN\models\varphiが同値となることを示すには、\Rightarrowと\Leftarrowの片方だけ確認すればよいらしい。なぜなら\Leftarrowの対偶は(M\models\lnot\varphi)\Rightarrow(N\models\lnot\varphi)となり、\lnot\varphiもまた論理式であるから。暗黙的に使われまくっていたので、典型テクニックなのだろう。

学食で食事してから、今日も麻雀。3.5半荘打って3着、1着、4着（トビ）、1着だった。最後の0.5半荘については自分が抜けた後を別の人が引き継いで南場に突入したらしく、最終的な順位がどうなったかは知らない。今日はなぜか起家にドラの絡んだ高い手が出やすく、5万点から6万点くらい集め最下位を飛ばして終わるのが3回繰り返された。南入しない回もあったため普段より多くの半荘をこなすことができた。

終電の1本前で帰宅。ハーメルンを読んだ。最近夢中になっていた「ようこそ未熟者がいく教室へ」を読了。

書く

syosetu.org

コンテスト後に行っている振り返りについて、ホワイトボード単体で共有してほしいというコメントがYouTubeに来ていたので、画像としてエクスポートしてDropboxに上げておいた。例えば勉強会のスライドはGoogleドライブに上げているが、メールアドレスがバレるのが気になる。YouTubeからワンクリックでたどり着けてしまうのは違うよな、ということでDropboxを使うことにした。

Dropbox - コンテストの振り返り - Simplify your life

午前4時過ぎ就寝。

10/09(水)

午前11時に目を覚ましハーメルンを読み始めてしまったが、1時間半で二度寝に成功した。午後2時起床。今日は天気が良いため原付で登校した。つい先日まで半袖Tシャツで原付に乗っていたはずなのに、今日は長袖の上からパーカーを羽織ってもなお寒かった。防寒具を出す必要があるらしい。

購買でパンを買い、院生室で少し話した。昨日の麻雀は自分が抜けた後、南場を終えてすぐ解散となったらしい。結局その半荘も起家が1着になったと聞いた。起家は持ち回りで務めたため、全員1回ずつ1着をとったことになる。

午後3時から集中講義二日目。昨日質問したことについて、資料に補足説明が追加されており、講義中でも少し触れられた。これに関して自分の理解を少しメモしておこう。

昨日の講義ではこのような説明があった：単位元、逆元、積の演算をfixした群の列G_0\subset G_1\subset\cdotsについて、\bigcup_n G_nもまた群となる。一方、比較演算のみをfixした「最小元を持つ」全順序集合の列M_0\subset M_1\subset\cdotsでは、\bigcup_n M_nが最小元を持つと限らないため、このような極限について閉じていない。この二つの違いは、群の公理がすべて\Pi_1論理式（\Pi_2でも可）で書けるのに対し、全順序集合における最小元の存在が\exists m.\;\forall x.\;m\le xという\Sigma_2論理式になる点である。

それに対し、昨日こういう質問をした：群は単位元をfixしなくても\exists e.\;\forall x.\;ex=xe=xという\Sigma_2論理式で公理化できるが、もしそうしたなら極限で閉じなくなるのだろうか。答えは「閉じる」。これは群論の話である。今日の補足説明では、群ではなくモノイドについて、単位元をfixしなかった場合に列の極限が単位元を持たなくなる例が示された。

一方、極限で閉じることと公理がすべて\Pi_2論理式で書けることが同値であるという定理が存在するため、群の単位元の存在は\Pi_2論理式で公理化できるはずである。それはxx^{-1}のようなしょうもない話ではない。なぜなら、逆元をfixしなくても積さえ共有していれば群は極限について閉じるからである。

つまり群の公理は積のみを用いた\Pi_2論理式で書ける。その具体的な形は、集中講義を聴いておられた先生によって与えられた。詳しい形は覚えていないが、確か\forall x.\;\forall y.\;\forall z.\;(xz=yz\land zx=zy)\rightarrow x=yのような積のキャンセルを使っていたはず。

今日も講義後に質問しに行ったら学年を聞かれて、D1であることを白状した。学部生への擬態失敗。すると何やら飲み会に誘っていただけた。明日の講義後、教員と博士課程の学生のみで行うらしい。光栄な話なので参加することにした。

学食で食事し、院生室に戻ってきたが、今日は麻雀を打つ人が足りない。仕方がないので帰宅し、ゲーセンに遊びに行った。

閉店まで18クレプレイ。今日は12+のスコア詰めをして全譜面99↑に乗せたり、「周防パトラ」イベントのクエストを完走したりした。

ラーメンを食べて日付が変わってから帰宅。ハーメルンを読みふけり、午前3時半くらいに寝落ちした。

10/10(木)

午後0時半起床。少しハーメルンを読み、買っておいたパンを食べて午後2時くらいに家を出た。今日も天気が良いが、大学から店まで集団で移動するため原付を使えない。郵便局に寄る必要もあり、せっかくなので徒歩で登校することにした。

地下鉄を使うのとほぼ同じ30分で着いたものの、延々坂道を歩かされたのでめちゃくちゃ疲れた。原付を使えないほど天気・足元が悪いときに歩きたい道ではない。ないが、火曜日みたいなシチュエーションで終電より麻雀を優先するのが視野に入ってきた。

午後3時から集中講義三日目。ある元が満たす論理式をすべて集めて作る「タイプ」という概念はかなり面白かった。講義で「タイプ」と言われていたのでなかなか気づけなかったが、これはプログラマ的には「型」と訳してほしいものだろう。もしもそれがアヒルのように歩き、アヒルのように鳴くのなら、それはアヒルに違いない……。

これまでピッタリ午後6時に終えてきた講義だが、今日は30分早めに終わった。院生室で少し時間を潰し、午後6時半に青葉山駅に集合。そこから地下鉄に乗ってイタリアンレストラン「Notti vago」に向かった。

参加者は集中講義の先生と東北大の教員4名、学生は自分を含む3名で全員D1。論理学の話だとついていけないかもなあと心配していたが、もっぱら学生だけで地元のことや同期のことについて喋っていたため問題なし。非常に楽しかった。自分の専門であるグラフや、趣味のプログラミングにも興味を持ってもらえて嬉しい限り。こちらから相手の専門に歩み寄るタイミングがなかったので、それは申し訳なかった。

あまりたくさんお酒を飲んだつもりはないのだが、少し騒がしいテーブルで大声で喋っていたら酔いが回るのも速くなり、かなりフラフラになった。日付が変わる前に帰宅。布団に倒れこんで少しハーメルンを読み、午前1時過ぎに寝落ちした。

10/11(金)

午前6時に目を覚ました。微妙に気持ち悪さが残っているが、うっかりハーメルンを開いてしまい眠気が遠ざかった。幸い4時間ほどして二度寝に成功。追加で3時間寝て、午後2時前に起きたら元気になっていた。シャワーを浴びて原付で登校。

午後3時から集中講義最終日。一瞬だけマトロイドの話が出てきてびっくりした。代数的閉包の一般化が定義できて、公理にうまい性質があるとマトロイドにおけるexchange propertyが成立する。すると閉包を使って定義された基底の濃度が一致してくれるらしい。無限マトロイドのことは何も知らないので、有限集合でなくてもマトロイドっぽいことが成り立つこと自体驚きだった。ところで基底というからには全体をspanしてほしいのだが、これもexchange propertyがないと保証できないようだ。

午後6時終了。今回の集中講義は信じがたいことに毎日時間内に終了した。

学食で食事して麻雀。2半荘打って2回とも2着だった。内容はあんまり覚えていない。

午後10時前に帰宅し、ハーメルンを読んだ。「ようこそ享楽至上主義の教室へ」を読了。

書く

syosetu.org

午前3時就寝。

10/12(土)

午前8時に目を覚ました。ハーメルン「ようこそ享楽至上主義の教室へ　IF等まとめ」を読了。

書く

syosetu.org

追加で3時間寝て、午後0時半くらいに起床。シャワーと食事を済ませ午後2時からUniversal Cupに参加した。今日は12回目、Qinhuangdaoセット。

書く

感想戦後、食事して、午後9時からABC375。

Panasonic Programming Contest 2024（AtCoder Beginner Contest 375） - AtCoder

書く

www.youtube.com

日記を書いていたつもりが、いつの間にか麻雀のフラッシュゲームに手を出していた。CPUが喰いタンのみとかダマのピンフのみとかでポンポン上がってくるため普段と感覚が違う。また自分が上がって気持ちよくなるのを優先してしまい、危険牌を考える意識が薄れてきた。1回きりのゲームでは適当に打ってしまってよくない、が、雀魂などで腕を磨くというほどのモチベーションもない。

無料で遊べる麻雀ゲーム「麻雀」GAMEDESIGN

少しハーメルンを読んで午前9時就寝。

10/13(日)

午後3時に目を覚まし、3時間ほどハーメルンを読んだ。それから二度寝して午後8時起床。食事とシャワーを済ませて午後9時からARC185に出た。

AtCoder Regular Contest 185 - AtCoder

書く

www.youtube.com

ハーメルンの短編「走れセリヌンティウス」を読了。「走れメロス」ほどの名作文学作品を原作知識あり憑依転生の舞台にするのは新鮮。ただ原作の雰囲気が失われてしまったという点で好きではなかった。

syosetu.org

午前4時半からCF #978 div.2に出た。普段とは全く異なる時間帯のコンテスト。途中で外が明るくなってきて、なんだかワクワクした。

Dashboard - Codeforces Round 978 (Div. 2) - Codeforces

書く

www.youtube.com

日記を書いて正午くらいに就寝。

週記（2024/09/30-2024/10/06）

09/30(月)

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

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

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

snuke.hatenablog.com

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

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

午前1時過ぎ就寝。

10/01(火)

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

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

博士課程では20単位取る必要があるが、そのうち16単位は研究と博論で自動的に埋まる。つまり残りの4単位だけ考えればよい。

週記（2024/04/15-2024/04/21） - kotatsugameの日記

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

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

メールを出す必要があるが、文面を考えるのが嫌すぎてしばらくラノベに逃避していた。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本だけどこから出たか記録できない辺があることが分かり、納得した。

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称号がまさにその動画のタイトルだった。元ネタに気づけて嬉しい。

www.youtube.com

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

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

週記（2024/09/23-2024/09/29）

09/23(月)

徹夜で先週の週記を書き続けていた。

午後1時頃昼食を食べに出かけようとした。街の中心部まで出る気はなく、最初に思いついた店がインドカレー屋「RAJ」。しかし念のため営業しているか調べてみたところ、Googleに臨時休業と書かれていた。これを見て外出する気力すら失い、結局部屋でパスタを食べた。

午後7時過ぎ、週記を書き上げて投稿。昔は穴あきがないのは当然のこととして、投稿前に読み返して校閲まで行っていたのだから信じられない。今日はもう眠いため、そこまで手が回らなかった。

ちょっとラノベを開いたがやはり眠気が限界。1時間ほどで寝た。

09/24(火)

午前2時過ぎ起床。MHCのPractice Roundが終了していたので、ここに感想を書いておく。無事全完できていた。

Meta Hacker Cup - 2024 - Practice Round

Aは最も速い人を酷使すればよい。Bは浮動小数点数を信じて(P/100)^{1-1/N}-P/100を計算した。テイラー展開を使えばもっと精度良く求められそう。ただ、validationにNが最大のケースと最小のケースが数個ずつあったから、それが通れば何でもよいだろう。

Cは乱択。2点をランダムに選び、それを通る直線をチェックすることを繰り返す。M\ge N/2-1ならN-2を出力しても正解と扱われ、そうでないなら点の過半数が同一直線上に乗っているからあたりを引く確率が1/4以上となる。

D1は最終的な石の座標の集合がEと一致し、インデックスは当然原点から遠い順に並ぶ。D2も結局似た方法で解けて、結論から言えば「石の座標とインデックスの和」の集合がE_i+iたちと一致する。石の衝突によって距離1だけエネルギーを使わず移動できるのを、代わりにインデックスを1減らしたと捉えているようだ。

D2はもともとO(N^2)で通そうと思っていた。石の座標の列を管理すると、ある位置への挿入とそれより前の要素のデクリメントで更新が行える。デクリメントしなくてよいよう管理する値にインデックスを足してみたところ、見事ただのソートになって解法が得られたというわけ。まあ実行時間が6分もあるので、O(N^2)でも答えは求まる。

ラノベ「R．G．O！」を読了。サブタイトル「女子高生、VRMMOで理想の魔法ジジイを目指します」がストーリーを説明している。面白かった。老魔法使いに対する憧れには共感できるので、そのロールプレイをしながらNPCたちと交流を深めるシーンはワクワクした。また攻略勢に発見されていないイベントを進めてキャラを成長させるのも好み。キャラの老成した容姿に見合う強さを手に入れるのはまだ先のことだろうが、それまでの過程も楽しめそう。

続いて「多元宇宙的青春の破れ、唯一の君がいる扉」を読了。SFラノベで、小ネタとしてキャラの苗字が有名な物理学者に由来していたり、章題がSF小説のパロディだったりする。序盤の主人公は並行世界の行き来でギャルゲーのようなセーブ＆ロードを実現していたから、何かしっぺ返しが来ることは予感できたが、思ったより壮大で思ったより容赦がなかった。セカイ系というやつだろうか。

午前8時から3時間ほど二度寝し、少し布団でゴロゴロして、正午を回ってから学食に向かった。これが大失敗。夏休み期間なのに信じられないくらい混んでいた。快速レーンでカレーだけ確保して食事。

購買で予約していたラノベを受け取って帰ってきた。一気に10冊届いたのでレジを通すのに時間がかかったが、学食と異なり購買は空いていたので助かった。

2時間ほどかけてメールを1通送信し、布団に戻って買ってきたラノベを読んだ。「万年を生きる平和主義ヴァンパイア、いつの間にか世界最強に」を読了。

タイトル通り長命な主人公の自己評価がズレている勘違いモノ。面白かった。似た設定で気に食わなかった作品もあるが、こちらは「大昔に関わった人が主人公を慕ったまま大成」という展開をそれほどプッシュしていないのが良かったのだと思う。ただ、そうなったのはそもそも主人公が人の肩書を認識していないからなので、今度はそちらによるコミュニケーション不全が目についてしまった。

午後6時半就寝。

09/25(水)

日付が変わる少し前に起きた。食事してシャワーを浴び、少し日記を書いて、その後はずっとラノベを読んでいた。今日は5冊読了。

1冊目、「隣に住んでる聖女様は俺がキャラデザを担当した大人気VTuberでした」。好きななろうの書籍化。配信で扱うネタがコンプラ的にちょっと際どくて、こんなだっけと思いつつも、相変わらず面白かった。1巻分でずいぶん仲が深まったように見えたが、後書きによればこれでまだ恋愛感情には至っていないとのこと。どこまで甘くなるのだろうか。

1作読了。「隣に住んでる聖女様は俺がキャラデザを担当した大人気VTuberでした」。

週記（2022/06/20-2022/06/26） - kotatsugameの日記

ところでこの本は校正に問題がある。誤字脱字が散見されるのはともかくとして、「同じ文章が2連続する」「鉤括弧の向きが変」というのはなぜ発生するのかがわからない。前者は242ページと、他に2か所ほどあったはず。後者は229ページ。

2冊目、「前世は冷酷皇帝、今世は幼女」。面白かった。前世で持っていた強さを、武術・魔法・知恵すべて今世に持ち越せているのが嬉しい。またその威風から幼女の見た目で舐められるという描写が一切ないのがありがたかった。「今世は自分のために生きる」という目標は活躍の道筋が見えず好みではないが、日常生活の中でも能力を振るう機会はたくさんあり、いたるところで格好良さが楽しめた。

3冊目、「妹の配信に入り込んだらVTuber扱いされた件」。好きなハーメルンの書籍化。Web版では場面転換の際大きくスペースを空けていたが、書籍化にあたってありとあらゆる空行が一切合切削除されており、かなり読みづらい。1行くらいは残す必要があったと思う。そうやって文章を詰め込み、さらに400ページに届かんとする厚みを持って、1巻ではハーメルンにおける23話ほどを収録している。別に巻としてオチがついたようにも見えないので、そこまでしなくてもよかったのではないかと思う。1話完結の会話劇を延々重ねる作品のためオチがつかないのは仕方ないことだと思う。

よくわからない記号列があったのでWeb版を確認したら、顔文字が縦書き対応にされていないだけだった。別の顔文字はちゃんと向きが合っていたから、そういう点に対する努力は一応見られる。

学食で食事し、帰ってきて4冊目「モンスターの肉を食っていたら王位に就いた件」。「悪の令嬢と十二の瞳」の著者・駄犬さんの作品。先週以下のようなことを言っていたが、こちらは主にそのストーリー・設定が面白かった。それもひたすら強い主人公が歩む勘違い覇道という、まっとうなラノベらしいもの。外伝で重要な背景設定を明かし、読後感にチクリと刺激を与えてくるところは共通していても、こちらではあくまで添え物という感じである。

こういう作品を書く著者なら、他の作品もストーリー・設定に依らず面白いことが期待できる。

週記（2024/09/16-2024/09/22） - kotatsugameの日記

このラノベが発売されたとき、自分も新刊チェックであらすじを確認したはず。かすかな記憶によれば、主人公が誰かの弟子になる展開は微妙かなと思って避けたのだと思う。読んでみるとそのあたりは一瞬で終わり、それどころか1巻の前半だけで最強の王へと成り上がったから、自分好みの話の速さだった。しかし「投稿小説全ての書籍化が瞬く間に決まった驚異の新人」とは凄まじいことだなあ。

gcnovels.jp

続いて5冊目「モンスターの肉を食っていたら王位に就いた件」2巻。面白かった。1巻ラストで敵として描かれたキャラがメインだが、うまくヘイトが消されていて受け入れやすかった。また師匠の登場にもびっくり。最強たるべき主人公が誰かの下に位置するのが苦手なのであり、夫婦という形を得るならまあ問題はない。話の内容とは別件で、1巻では明度が低く何が何だかよくわからなかったイラストが全体的に明るくなっており、これも良かった。

午後9時半就寝。

09/26(木)

午前3時から2時間ほど起きており、論文を読んでいた。

午前10時起床。TCBの2024/09回に参加した。来週火曜日までなので、感想は来週の週記に。

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

午後4時頃外出し、地下鉄に乗って仙台駅まで出た。駅地下の飲食店街にある大戸屋で食事。この店は先々週行った海鮮丼屋の向かいにある。仙台駅前だとロフトの上にある少し閉店の早い店舗しか知らなかったので、別の店を発見できて嬉しかった。まあググれば出てくるのだが……。

店に一番近い出口から地上に上がると、仙台駅の南端くらいまで来ていた。普段は北のほうを利用しておりこちらには滅多に来ない。その北のほうにある丸善でラノベを買おうと思っていたが、せっかくなので喜久屋書店で買うことにした。品揃えは比べるまでもなくこちらのほうが良い。駄犬さんの「誰が勇者を殺したか」とその続編を入手した。まああれだけ売れているなら丸善にも置いてあっただろう。

その後GiGO仙台まで移動しチュウニズムを遊んだ。以前は8台あったはずだが、2台減って代わりにオンゲキが2台増えておりびっくり。少し待ちが発生しつつも、捨てゲーしてしまうことも多く、5時間で30クレプレイした。専らniconicoジャンルのスコアを詰めており、全譜面を98↑に乗せた。

帰りに「六朗」でつけ麺を食べた。いつの間にか食券からモバイルオーダーになっていた。店が地下にあってネットが繋がりにくいのに何やってるんだという気持ちはあるが、これまで口頭で伝えていた大盛や熱盛をメニューから選ぶことができたのは良かった。

帰りも地下鉄に乗って午後11時半に帰宅。シャワーを浴びた後、洗濯機を回しながらラノベを読んでいたが、急激な眠気に襲われ洗濯物を干さないまま午前1時半ごろに寝てしまった。

09/27(金)

午前5時起床。洗濯物を干した後、ついでに部屋の掃除とゴミ出しを済ませた。生ごみをまとめて捨てるため、冷蔵庫に転がっていた貰い物の梨も食べた。かなり上手に剥けて嬉しい。

布団に戻ってラノベ。3冊読了した。

1冊目、「モンスターの肉を食っていたら王位に就いた件」3巻。相変わらず面白かったが、バルカン国の反乱を組織するシーンは容赦がなさすぎてちょっと引いてしまった。なんだかんだヒロインたちの心情に配慮した展開になると勝手に期待していた。シーラが他のヒロインに比べて常識的すぎるだけかもしれない。また新ヒロインのマリアは自己主張が強すぎて苦手気味。好みなのはフラウである。何を考えているのか分からない系のキャラの視点で内心が語られると、得体の知れなさが反転して安心感を得られる。

2冊目、「横溝碧の倫理なき遊戯の壊し方」。面白かった。自信満々かつそれに見合った才能を持ち、結果を出し続ける主人公が良い。天性の感に頼っている部分もあるとはいえ、あまりに堂々と振る舞うから不安定さは感じなかった。ただ1巻の結末は残念ながら片手落ちで、黒幕の悪辣さを印象付けるものとなった。取り返しのつかないことが起こってしまったように見えるが、2巻は一体どういう出だしになるのだろうか。

午後2時半ごろ学振の結果が出た。今年も不採用C。ただし評定やTスコアを昨年と比較するとそこそこ改善されている。昨年よりマシな申請書を出したらマシな結果が返ってきたので、一種の成功体験。まあこの伸び幅をもう1年続けても通りそうにないが……。

ラノベに戻って3冊目、「黒幕ゲーム」を読了。面白かった。主人公は計画の立案能力が並外れており、実行をほとんど仲間に任せていてもおんぶにだっこという印象はない。それにしても主人公の才能だけ融通の利かなさがはなはだしいが、それだけ未来を垣間見ることは特別と設定されているのだろうか。この能力で情報を集めるテクニックもかなりアクロバティックだった。

午後7時から3時間ほど仮眠をとり、パックご飯を食べて午後10時半からCF #975 div.1に出た。

Dashboard - Codeforces Round 975 (Div. 1) - Codeforces

Aは山のサイズをnから1まで試し、分割できる最大の枚数までカードを買い足してチェック。Bは時刻1,\dots,nの時点で征服しておくべき区間が指定されている。各時刻で始点の候補となる区間を求め、それらの共通部分をとればよい。Cは残す葉の深さを全探索。深すぎる頂点、または十分な高さのない部分木の頂点を削除する必要があるが、この二つの条件は排反であるため、独立に数えられる。

Dはまず、最適に塗った際赤い要素の最大値が\max(a)となることを示せる。そこで赤い要素の最小値を固定、正確には赤く塗れる要素の下限を決め打ったときに、塗れる要素数の最大値が求まればよい。塗れる要素は数列のいくつかの区間になっており、1個飛ばしで取っていくのが最適。ただし\max(a)を赤く塗るために1個損するケースもある。これらの管理を差分更新で行う。

長い間E1を考えていたがついに解けず、F1に移動した。Bの解法からすぐにO(n^5)状態のdpが得られる。遷移も頑張ってまとめることで、やはり全体でO(n^5)になる。しかし実装してみると最大ケースで8secくらいかかってしまった。そこからの高速化もうまくいかず、結局提出できなかった。

4完83位で2967→2917(-50)。F1はありえない状態からも遷移していたのが悪かった。そういうところまでループを回さないようにするとちゃんと定数倍が軽くなり、1.4secで通った。

www.youtube.com

ラノベ「黒幕ゲーム」2巻を読了。面白かった。作中最強格のキャラには勝てないから、直接対峙するのは避けて敵の敵になってくれるように動くという手法は結構見るかもしれない。終盤までずっと綱渡りで大変冷や冷やしたが、最後は主人公がきっちり決めてくれて嬉しい。

あとがきで、カクヨムでサイドストーリーが連載されていることを知ったので、そちらも読んだ。ほとんどラブコメで、たまにちゃんとした舞台裏がある。キャラのセリフに句点を用いず1文ごとに鉤括弧を分けており、話者の交代が空行で表現されている。最初は読みづらかったがすぐ慣れた。

kakuyomu.jp

シャワーを浴びて日記を書き、午前9時半就寝。

09/28(土)

午後1時起床。学食で食事し、急いで帰ってきて午後2時からUniversal Cupに出た。今日は10回目、West Lakeセット。

書く

午後9時からABC373に出た。

AtCoder Beginner Contest 373 - AtCoder

Aはよい。Bは誤読してS^{-1}を考える必要があることに気づいておらず、少し手間取った。C、Dもよい。EはXを変数として式を立て、解けないなあとしばらく唸っていたが、単調性が意味から明らかなので二分探索してしまえばよかった。Fはうれしさをv+1-2kに分解し、wごとにまとめて遷移。後半を思いつくのに時間がかかった。

Gは線分の交差判定が結構面倒で特に良い性質もないので、何かアクロバティックな解法が必要。適当に割り当てた後、線分の交差を解消するようにswapを繰り返せば解が求まるのではないかと考えた。swapするたび交点が一つ以上減ることを示したつもりだったが、後で考え直すと大嘘。コンテスト中はこの事実からswap回数がO(N^2)になり、更新をO(N)で行えばOKだろうと思って提出した。すると爆速でAC。

52分で全完して5位。コンテスト後の振り返りをしているときにGの嘘に気づいた。ただし交差を解消するswapが線分の長さの総和を縮めるから、そのうち解にはたどり着けるらしい。swap回数はO(N^2)にはならないと思うが、まだ反例はないようだ。

コードゴルフはCまで。AとBはNibblesで書いたが、Aは==でなく^0-を使うことでImplicit Argsが使えるようになるらしく1B負け、BはSをソートすれば'A'..'Z'が得られるのに気づけず3B負け。CはNibblesが入力だけでTLEしたので別の言語を持ち出す必要があり、久しぶりにRakuを使った。

www.youtube.com

ラノベを読んでいたら眠気に負け、午前2時半ごろ寝落ち。

09/29(日)

午前6時半起床。

ラノベ「ビリオネア・プログラム」を読了。「Vのガワの裏ガワ」の著者の新作。MF文庫Jはこういう学園モノが好きすぎると思う。正直、微妙……。主人公がチャラすぎて苦手だし、掲げる信条と行動がかなりズレていて、その理由もあまり説明されていなかったように感じた。ラストもどんでん返しというよりちゃぶ台返しで、2巻が出るとしてどう話を続けるつもりなのかよくわからない。

続いて「孤高の華と呼ばれる英国美少女、義妹になったら不器用に甘えてきた」2巻を読了。ラストの野球の試合シーンはなかなか熱い展開だった。四番バッターである主人公はデータに基づいて打つタイプで、珍しい設定だと思う。この試合で一皮むけたらしく、今後の躍進が描かれることにも期待が持てる。

その後しばらくハーメルンを読み、正午から午後5時までは二度寝、起きてからまたハーメルン。

「超強化怜(贋)」を読了。「うちの脳内コンピューターが俺を勝たせようとしてくる」の人の最新作。この人の書く主人公最強ものはやはり面白い。描写があっさりしているのが特徴だろうか。細部について想像を膨らませる余地がある。

syosetu.org

ハーメルンは面白かったが、睡眠には失敗している。そもそも二度寝に入るのが遅かったし、午後5時に目を覚ましたときもまだ眠れそうだったのにすぐスマホを触り始めてしまった。シャワーを浴びたり食事したりして眠気を振り払い、午後9時からAGC068に臨んだ。

AtCoder Grand Contest 068 - AtCoder

書く

直後のCFは、いつの間にか開始が1時間遅らせられていた。A問題の振り返りを撮って30分過ごし、午前0時半からCF #976 div.2。

Dashboard - Codeforces Round 976 (Div. 2) and Divide By Zero 9.0 - Codeforces

Aはk進法の桁和。Bはn-\lfloor\sqrt n\rfloor=kが条件で、二分探索。Cは引き算で繰り下がりが発生しないためbitごとに決定できる。Dは同じdでまとめて辺を張っていくとよい。Eは典型で、f(S)をbitの和で表現し、2乗を展開することで、2bitだけ見るdpを55回行う問題となる。

Fはg(i)=f(i^k,d)が乗法的関数となっているため、他人のライブラリでぶん殴れる。しかし勘違いでg(p^e)=\binom{d+ke}{d}であることになかなか気づけず、かなり時間をかけてしまった。

乗法的関数のprefix sum | Nyaan’s Library

1時間弱で全完して6位。簡単回。

www.youtube.com

3時間ほどインターン関連の調べものをした後、日記を書いて午前11時くらいに布団に入った。しかし眠れない。諦めて学食に向かった。キャベツサラダに乗っていたブロッコリーが消えていて仰天。値段は変わっていないし、キャベツが増えたようでもない。

ラノベを買って帰宅し、午後1時前に就寝。

今週は本を14冊読んだ。「当たり」、つまり面白かった本が多くて楽しかった。駄犬さんの既刊の作品はすでに8冊すべて購入済みであり、今週までに4冊読んだこととなる。どれも面白かった。残りも、特に「誰が勇者を殺したか」は評判から間違いなく面白いだろう。こうなると逆に読むのに気合が必要となってくる。

週記（2024/09/16-2024/09/22）

09/16(月)

午前5時起床。

布団で最近読み返していたハーメルン「じゃしんに愛され過ぎて夜しか眠れない」を読了した。やはり面白い。傲慢なくらい自信に満ち溢れていて実力と知名度が伴っている主人公の造形が好みだし、デスティニードローを駆使したカードバトルでの無双も見応えがある。

syosetu.org

起きて先週の週記を書いていたが、正午を回ったくらいでもう眠くなってきてしまった。諦めていったん寝ることにし、午後2時半くらいに仮眠に突入した。

数度の目覚ましを無視し、午後8時になってようやく起床。そこからまた週記を書き進めて日付が変わる前に投稿したが、コンテスト数個に加え日曜日の分が丸々穴あきになってしまった。

昨日チームメイトに発送した賞品のスマートウォッチがもう届いたらしい。こちらでも開封し、写真をTwitterに上げた。一足先に受け取ってはいたが、なんとなくタイミングを合わせてみた。続いてスマホに「Huaweiヘルスケア」アプリを入れて諸設定を済ませた。

何やら心拍数、血中酸素濃度、さらに謎のストレス値も計測できるらしい。自分が一番気になっているのは睡眠の記録である。いつも部屋が明るい中で寝ているし、時間もバラバラな現状、果たして睡眠の質はどのようになっているのだろうか。

また時計としての使い方も面白かった。どうやらディスプレイを上に向けて水平にすると勝手に画面が点灯するようだ。つまり腕に着けた状態で腕時計の文字盤を見るしぐさをすると、手を触れなくても時刻が確認できる。腕を下ろせば消灯するので内容が人目に触れることもあまりない。デフォルトの時計は見にくいが、着せ替え機能でシンプルなものにしておいた。

先週の週記に日曜日分とABCを追記した後、ラノベを読んだ。「悪役転生者は結婚したい」を読了。

面白かった。ヒロインの心を射止めようと努力しアタックする、恋愛に対し積極的な主人公に好感を抱いた。一方で悪役転生である必要性がよくわからなかった。原作主人公も原作ヒロインも人の話を聞かないどうしようもないキャラとして悪し様に描かれており、ゲームのメインキャラとして成立していたとは思えない。そこがかなり気になってしまった。

午前5時半就寝。

09/17(火)

午前8時少し前に起床。今日は東邦大学で行われるセミナーを聴講する予定である。寝不足で途轍もない不安があるが、こうなってしまったものはしょうがない。ただ残念なことに、せっかくスマートウォッチを着けて寝たのに睡眠時間が3時間未満だったため詳しい計測が行えなかった。

荷物を整え午前8時半出発。駅で立ち食いそばを食べて新幹線に乗り、東京駅で総武本線に乗り換え、正午前に津田沼駅に着いた。移動中はずっと本を読んでいた。時間に余裕があったので駅近くの本屋を少し長め、バスに乗車。午後0時半ごろセミナー会場の東邦大学習志野キャンパスに到着した。

まず学食で昼食を摂った。カレーを注文したが、東北大学からは消えて久しい福神漬けがまだ残っていて感動した。会計は東北大学生協の電子マネーが当然使えなかったので、現金。アプリが同じだけらしい。

午後1時にセミナー会場の教室に到着。30分ほどボーっとして、セミナーの開始時刻を迎えた。タイトルは「辺着色グラフと関連する代数構造」。

可換代数と組合せ論セミナー

内容になんだか既視感があったが、問題の定式化が昔Universal Cupで見た手法だった。もっと言うと、当時参考にしたこどふぉブログの「Colorful spanning tree」の話だった。ということでここまでの話が容易に理解できたため、最後まで話についていくことができた。講演者の方の共同研究者としてY.Y.さんが出てきてびっくり。

Login - QOJ.ac

[Tutorial] Matroid intersection in simple words - Codeforces

4時間弱で終了。懇親会は不参加の予定だったので、すぐさまバスに乗って津田沼駅前に戻ってきた。よこに連絡を取って東京で一緒に夜ご飯を食べることにしたが、その前に駅前でチュウニズムをプレイしておく。全国行脚である。

行きのバスの車内からAPINAが見えていたので、まずはそこに向かった。しかし残念ながらクレーンゲームと太鼓の達人しか置いていないタイプの店舗。仕方ないので少し歩いてシルクハットに入った。2台しかなく、しかも埋まっていたが、並んでみると一人帰ったので無事連コできた。3クレで称号「千葉勢」を獲得。

記録を確認すると、全国行脚で新しい県が埋まったのは実に6年ぶりらしい。ひとつ前に埋まったのは神奈川県で、大学一年生時のICPCで行ったときだった。そこから自分の行動範囲は一切広がっていないようだ。分かっていたこととはいえ、こうして突きつけられると思うところはある。

総武本線で東京に戻る道中、JOI一次予選の第1回が公開されていることに気づいたため、スマホで縮めた。Cのみsed、残りはNibbles。改行コードを1Bにするテクが必要なかったのはラッキーだった。またPascalでも実装し、すべて0msを出しておいた。

JOI 2024/2025 一次予選 (第1回) 過去問 - AtCoder

午後7時半過ぎ、予定より少し遅れて御茶ノ水駅に到着。よこと合流し、しばらく線路沿いを歩いて適当なラーメン屋に入った。

食後、帰りの新幹線までまだ時間があったので、秋葉原まで歩いてゲーセンに入った。こちらでも3クレプレイ。

秋葉原駅で解散し、東京駅に向かった。秋葉原駅を出たのは新幹線が発車する15分前だったが、二駅しか離れていないし乗り換えも慣れたものなので問題なく乗車に成功。車内では行きと同じく本を読んでいた。「池袋ウエストゲートパーク」17巻を読了。

コロナ禍初期、2020年夏から1年の間に発表された作品四つ。トラブルシューターの仕事は人と会わないとやっていけないから、あまり自粛しているような印象は受けなかったが、通行人・客が少ないとか店が夜遅くまで開いていないとか、随所にコロナ禍の描写が挟み込まれていた。まさにウィズ・コロナの小説。

次の巻はコロナ禍初期の、一番騒がれていた時期の話になるだろう。どのように描かれるのか気になる。

週記（2023/12/25-2023/12/31） - kotatsugameの日記

パターンとして、作品四つのうち最後のものは表題作であり、ページ数が少し多く内容も重厚である。この巻だとネット炎上の話。誹謗中傷した人を訴えたわけでもなければ改心させられたわけでもない、なんともスッキリしない結末だった。それ以外の三つはかなり軽快。特に二つ目の「グローバルリングのぶつかり男」は、多少ご都合主義的な側面もあったが主人公が大活躍していて好みである。

午後11時過ぎに仙台駅着。最近寒い気がしたので念のためパーカーを持って行ったのだが、東京で使わなかったのはもちろん仙台に帰ってきても半袖で過ごせる暖かさだったから、完全なお荷物だった。

帰宅してシャワーを浴び、しばらくラノベを読んで午前3時前に就寝。

09/18(水)

午前8時前起床。布団でラノベ「レベル0の無能探索者と蔑まれても実は世界最強です」2巻を読了した。

主人公は自分が強いことを自覚していないため、パーティーにおける自分の役割について悩んでみたり、メンバーのサポートこそが本懐だと結論付けてみたりしているが、何もかも縛りプレイとしか思えない。世界最強であるという設定がどこにも表れていなかった。残念。

正午から午後4時くらいまでは二度寝。起きてから、ついに計測に成功した睡眠を確認した。よくわからないが質はそう悪くないようでびっくり。まあ若さにものを言わせているだけな気もする。

しばらくスマホで動画を見て、午後5時過ぎに外出した。今日は数学科の友人と焼肉を食べる。店は2か月ほど前に新しくオープンした「焼肉きんぐ」。

「炙りすき焼カルビ」を食べたくて食べ放題コースのランクを上げたのだが、薄切りの肉は焼くのが難しく、かなり焦がしてしまった。また「きんぐカルビ」や「壺漬けドラゴンハラミ」など大きめの肉を網の上で切ろうとして、熱気でやけどしそうになった。普通のコースで十分。

午後8時解散。それからゲーセンに行き、閉店まで20クレ遊んだ。久しぶりに「Blue Noise」をプレイしたらいつの間にかラストを押せるようになっていたので、ちょっと頑張ってAJを出した。なんと99AJが出て精度も大満足。もともとSSS+8点という14+で下から2番目のスコアだったことを思うとすごい伸び幅だ。

ドンキに寄って帰宅。シャワーを浴びてラノベを2冊読んだ。

1冊目、「怠惰な悪辱貴族に転生した俺、シナリオをぶっ壊したら規格外の魔力で最凶になった」2巻。書籍版で追加されたエピソードだと思うが、舞踏会部分が好きではなかった。学校行事の運営に精を出したり上級生にからかわれたりする主人公は、ちょっと丸くなりすぎている。凶悪さがどこにも出ていなかった。その観点で言えば、本編もあまり尖ってはいなかったかもしれない。そちらはまだ許容範囲内だった。

2冊目、「悪の令嬢と十二の瞳」。信じられないくらい面白かった。次の段落はネタバレ注意。

終盤まではあらすじ通り普通の逆行転生モノで、それも十分面白かったのだが、オチが素晴らしかった。このようなストーリーを根底から覆す仕掛けは大好物であり、その存在を知らないまま読めたことはかなりの幸運だったと思う。帯の文言がいちおう匂わせっぽくなっているものの、結末を知らないとそうとはわからないだろう。読む前の自分は気にも留めていなかった。

こういう作品を書く著者なら、他の作品もストーリー・設定に依らず面白いことが期待できる。調べると、デビューがたった1年前なのにも関わらずすでに他に4シリーズも手掛けられていた。どれも新刊チェック時にあらすじを読んで買わないことに決めてしまったのを覚えている。今また出会えてよかった。

ということで既刊7冊の購入を決定。ついでに9月・10月の新刊チェックを行い、計27冊注文した。「誰が勇者を殺したか」シリーズ2冊は品切れ中だったので、いずれ本屋で手に入れてくる予定。

今年のYandex Cupの日程が出て、参加登録が始まっている。自分も登録した。職業を学生にしたら学年の選択肢にD1がなかったので「Postgraduate Program」を選択しておいたが、調べた感じ何か違うような気がする。まあ間違っていても大した問題にはならないだろう。

Yandex Cup — championship for developers

しばらくハーメルンを読んで午後1時就寝。

09/19(木)

午後7時半起床。布団でラノベを読んでいたが、3時間ほどでまた寝てしまった。ここで日記の日付を変えておく。

09/20(金)

午前2時半起床。ラノベを2冊読んだ。

1冊目、「こましゃくれり！！」。設定がびっくりするくらい「依存したがる彼女は僕の部屋に入り浸る」と似ている。以前ハーメルンで見かけたときは二つ目はいらないかなと思ってスルーしたが、なんとこちらも書籍化とのことで買ってみた。比較すると、こちらはかなり理性が失われているという印象を受けた。正直ライン越えだと思うクズ描写もあって、ちょっと肌に合わなかった。

2冊目、「家事代行のアルバイトを始めたら学園一の美少女の家族に気に入られちゃいました。」2巻。主人公の主婦力は1巻で十分描写したということなのか、2巻は主人公とヒロインの両片思いがメインだったように思う。ヒロイン宅でヒロインの家族を巻き込んで進行する点は特徴的かもしれないが、前提として雇用関係があるせいかまだ距離感が遠く、偽の恋人関係を始めたりもして、すれ違っていきそうな印象を受けた。

午後1時頃シャワーを浴び、生協へ。学食で食事して購買で本を買い帰ってきた。火曜日のセミナーに関する出張報告書を作成し、午後5時半に寝た。

5時間くらいで目を覚ましTLを見て、今日CFがあることに気づいた。しばらくラノベを読んで待ち、午後11時半からCF #973 div.2。

Dashboard - Codeforces Round 973 (Div. 2) - Codeforces

Aは毎秒\min(x,y)個の果物を処理できる。Bは符号を考えるとa_{n-1}のみ必ず負になる必要があり、それ以外は正にできるからこれが最適。

Cは細かいところがかなり面倒だった。最初に空文字列を用意し、sの部分文字列という状態を保ちながらクエリ2回で1文字ずつ伸ばしていく。ただし伸ばす方向を切り替えるタイミングで2回のロスが発生するため、これをカバーする必要がある。切り替えた後はクエリ1回で1文字伸ばせるので、少なくとも1回は減らせる。もう1回は初手の分で、最初に"0"を聞いて0が帰ってきたらsは全部1だと確定する。

Dは先頭から舐めることにより\min(a)の最大値が求まり、それを固定した状態で今度は後ろから舐めると\max(a)の最小値が求まる。これが最適。Eはprefixの長さと\gcdを持ってdpしたいが、状態数が多すぎる。そこでprefixの長さを持たず、代わりにdpの値を少し調整するとうまくいく。遷移は約数包除でちょっと大変。

F1は先手後手ともに勝敗が確定しない手が高々一通りしかないので、勝つチャンスが巡ってくるまではそれを採用して1手ずつ進めていけばよい。根とuを結ぶパスの上をお互いに1歩ずつ近づくような形になる。勝敗の判定は、各部分木について根からできるだけ長く続くパスの長さを前計算しておくと、セグ木と適当な区間取得で行える。

F2はパスuvをLCAで分割してそれぞれ解くと、根と始点を結ぶパスたちが重なる。あとはその上で頑張って並列に解く。先手後手ともに初めて勝てるのが何ターン目かを求めればよい。勝てるならば相手の頂点が根と始点を結ぶパス上でどの区間にいるか、というのが計算できるから、並列で行うのが効く。

ところがF2が合わない。そのままコンテストが終了し、6完10位となった。その後30分くらいかけてようやくどこが違うのか判明。前計算では根とuまたはvを結ぶパスの外しか考えておらず、例えばuの親を始点としたときに、後手が初手でuに降りるようなケースをカバーできていなかった。初手だけF1の方法で計算することにして対処した。

www.youtube.com

MHC2024のシーズン到来。Practice Roundが始まったので念のため参加しておいた。終了は来週火曜日なので、感想は来週の週記に。

Meta Hacker Cup - 2024 - Practice Round

朝方から日記を書いていたが、昼前にはハーメルンに移っていた。「幸運薬オーバードーズ少女、ホグワーツに行く」を読了。興味深い設定であり、どのように話を転がしていくのか気になった。

syosetu.org

次にラノベ「現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変」6巻を読了。面白かった。たしか5巻の時点でもあった描写だと思うが、外野が主人公と総理の対立を予想して動くのに対し、主人公は未来知識から総理には勝てないと判断して敵に回さないよう立ち回り、結果はしごを外された外野の人々が大損して痛快。この総理は元ネタが元ネタだし、描かれ方的にも主人公の頭を押さえつけるような政治が許容できるくらいの大物である。

午後3時就寝。

09/21(土)

午後8時半起床。食事して午後9時からABC372に出た。

UNIQUE VISION Programming Contest 2024 Autumn (AtCoder Beginner Contest 372) - AtCoder

Aは問題名が問題になっている。sedで書いたらピリオドのエスケープを忘れて1WA。Bは3進法での展開を使う。これが最適なので、N\le 20であることはチェックしていない。Cは周り5文字だけ見る差分更新。Dは累積MAXをstackで管理するテク。Eはマージテクとsetで連結成分の頂点集合を管理した。

Fは辺N+1\dots N+Mのどれを直前に使ったか持ってdp。計算量はO(KM^2)であり、配列アクセスも飛び飛びのため1900msかかってびっくりした。dpの次元を入れ替えると1400msにはなった。GはCHTで凸包を作成し、floor_sumで内部の格子点を数えた。面倒だが書いてみると案外できる、といいつつ傾きが同じ直線の処理をミスって1WAした。

45分で全完、3位。コードゴルフはAとBをNibblesで書いたがどちらも負けた。

www.youtube.com

午後11時半からはCF #974 div.3。10分こどふぉった。

Dashboard - Codeforces Round 974 (Div. 3) - Codeforces

Aは言われたことを書く。Bはi^i\equiv i\pmod 2。Cはソートして\lfloor n/2\rfloor+1番目の値が\frac{x+\sum a}{2n}未満であればよい。この不等式を解く。ただしn\le 2のときは過半数と全体が一致するため不可能。Dは適当な尺取りですべての日程について計算する。

Eは頂点1とnからそれぞれ拡張dijkstraを行い、合流する頂点を全探索する。同じ馬を使ってしまう可能性があるが、このときはそもそも馬がいる頂点で合流するほうが得なので問題ない。Fは木dp。Gはシミュレーションで、同じ日に手に入れた牛乳を飲み続ける期間を算数によってO(1)で処理すれば十分高速。Hは各要素が偶数個ずつあればよく、これはZobrist hashで判定できる。

全完3位。

www.youtube.com

ラノベ「凶乱令嬢ニア・リストン」6巻を読了。面白かった。弟子の一人アンゼルに「外氣」を教えるシーンの主人公があまりにも格好良くて、ほんの数ページながら強烈な印象を残した。いまだ主人公は表に出ないし、暗闘でも強さの底は見えないが、さすがに慣れてきた。それでもなお面白いということで。

しばらく論文を読んでいたら猛烈な眠気がやってきたので布団に入った。しかしスマホを弄っているとなんだか目が冴えてきてしまい、起き上がってまたラノベを読んだ。「ネットの『推し』とリアルの『推し』が隣に引っ越してきた」3巻を読了。主人公とヒロイン3人で旅行に行く展開。アイドル声優もVTuberもその設定が活かせる出番はなく、有名人としての特別性が失われてしまっていた。

午後1時半就寝。

09/22(日)

午後6時半に目を覚まし、1時間ほどなろうを読んでからなぜか二度寝に入ってしまった。午後8時以降15分おきにセットしてあった目覚ましだが、止めてまた寝てを繰り返した結果、最終的な起床は午後8時45分までもつれ込んだ。危ないところだった。

午後9時からARC184。

AtCoder Regular Contest 184 - AtCoder

Aから難しかった。N-1回聞けば2種類に分割でき、サイズを見ることで特定できる。そこでもっと小さなブロック50個以上に区切り、同じことをしてみた。ブロックサイズを20にするとちょうど50個に分けられるからクエリは950回。しかしこれだと、ある一つのブロックに偽物10個が全部集まったとき区別できなかった。

サイズを少し変え、サイズ19のブロック51個とサイズ31のブロックを作るとうまくいった。偽物が二つ以上のブロックに集まれば、1ブロックには9個以下しかないため特定可能。一つのブロックに固まった場合も、10個と9個もしくは21個に分かれるから、これまた特定可能。ただしここの実装でミスして1WA。assertで落ちるはずなのにWAが返ってきたので戸惑った。

Bは面白かった。2でも3でも割れない数mに対し、2^a3^bmという形をした数のみを考え、これをすべてのmで行えばよい。また特に(m,N)=(1,\lfloor N/m\rfloor)として計算しても同じなので、O(\sqrt N)通りのn:=\lfloor N/m\rfloorで解いて、適切に係数を掛けて足し合わせれば答えが求まる。

nを固定したときにどう解くか考える。格子の座標(a,b)に2^a3^bを並べると、操作はちょうどL字型に並んだ3点をカバーすることとなる。これでn以下の点を埋め尽くせればよい。端から貪欲に置いていくのが良いと考えたが、出してみるとWAだった。

となるとルールベースで考えるのは筋がよくないだろう。幅が1+\lfloor\log_3 n\rfloor\le 19しかないため、bitDPできるのではないかと考えた。下位集合へのゼータ変換を使いつつ書いてみたらN=10^9でも1secしかかからなかったので提出、見事AC。計算量はわからない。

順位表を見るとDがたくさん解かれていたので、Cを飛ばしてそちらに進んだ。最初は選んだボールkも取り除かれるものだと勘違いしていたが、もしそうだったとしてもこのとき考えていた区間dpは役に立たない。しばらく考えて、残るボールの集合が一致するときにボールの選び方の重複を除くのが難しいことに気づいた。

操作するボールは左上から右下に並ぶので、その順にdpしていく。直前に操作したボールを状態として持ち、次に操作するボールへと遷移する。この遷移が可能かどうかというのを決めたい。選ぶボールを極小にする目的で「その操作で新しく取り除かれることになるボールがあるか」という条件を考えたが、これだとまだ重複してしまうようだ。サンプル2が強い。

面白いことに、極小ではなく極大だとうまくいった。つまり、遷移元のボールと遷移先のボールの間にあるボールで「それを選ぶ操作を加えても取り除かれるボールの集合が変化しない」ものがない場合のみ遷移を採用する。

普通に書くとO(N^4)で、取り除かれるボールの集合をbitsetで管理し定数倍高速化すれば十分間に合う。左上と右下に番兵を置くと実装がやりやすい。コンテスト中は左上にだけ置いていたので、最後の答えの集計に少し手こずってしまった。出したら一発AC。

残り12分でCの問題概要を読み、終了。ABDの3完で21位だった。BはO(\sqrt N)通りのnで解いたが、実際のところ2^a3^bという数にしか興味がないのでO((\log N)^2)通りでよいらしい。

www.youtube.com

その後CとEのupsolveをした。

Cは山折りと谷折りの0-indexedの列がOEIS A014707にある。コメントに「The regular paper-folding sequence」ともあるし間違いなさそう。このシンプルな定義を見れば、インデックスのbit列を見ることで山折りか谷折りか判定できることがわかる。あるいは、ほぼ同じ列であるA038189の説明を見てもよい。ここまではコンテスト中に考えていた。

A014707 - OEIS

A038189 - OEIS

実はもう考察の必要はない。i+A_kのbit列の下位桁が特定の形になっていてほしいという状況で、上位bitを弄る必要性は薄いのだから、「特定の形」を達成する最小のiを候補として計算すればよい。これは全体でO(N\log A)個存在し、それぞれfの計算にO(N)かかるため、間に合う。

Eは大変だった。一つのf(i,j)を求める方法を考えるのは役に立たない。とにかく実験。列の先頭要素を1とすると、すべての列はちょうど長さに対して定まる回数だけ操作することで元に戻ることが分かった。つまり同じ長さのサイクルがdisjointに存在し、同じサイクルに属する列たちが互いに移り合う。サイクルの中で一つ特徴的な列を決め、そこからの距離を求めたい。

辞書順最小の列を選んでみる。M=6の例を以下に書いたが、0-indexedで0,2^0,2^1,2^2番目が固定され、それ以外は任意となっている。ここからサイクルの個数が2べきだとわかる。M=6ではサイクル四つ、またサイクルの長さは8で、列の種類数は2^{M-1}=32=4\times 8とうまく成立している。

100000
100001
100100
100101

では任意の列からこの形にするにはどうすればよいか？これも実験によって見出した。i=0,1,\dotsの順に、列の2^i番目が1だった場合、操作を2^i回巻き戻せばよいのだ。これで同時にインデックスも計算できる。2^i回の操作がまとめてO(M)で行えるので、巻き戻しもやはりO(M)で可能。あとは適当にグループ分けして計算。

その後は日記を書いていた。この日は徹夜したので、日付はここで区切っておく。

週記（2024/09/09-2024/09/15）

09/09(月)

午後3時過ぎ起床。半からインターン先定例会に出席した。先週の進捗は、なかった。

勉強会はラムダ計算の話。勉強会では何度か扱われたことのあるテーマであり自分も前に一度発表したが、今日はそれらよりもかなり理論に寄った内容で、β簡約とそのチャーチ・ロッサー性の説明だった。自分が修士1年のとき同級生のセミナーで聞いていたものとほぼ同じ。懐かしい気分になった。

テーマは関数型言語で、ラムダ計算の導入、そのSKIコンビネータによる表記、またそれを用いたHaskellにおけるポイントフリースタイルへの書き換えを話した。

週記（2022/05/16-2022/05/22） - kotatsugameの日記

質疑応答がかなり盛り上がって、解散する頃には午後6時半を回っていた。急いで学食に向かい、食事。帰りにコンビニに寄ってパンやおにぎりを買ってきた。

帰宅してからはずっと先週の週記を書いていた。コンテストがいくつか穴あきになった状態で日付が変わる直前に投稿。そのあとしばらく追記していたが、急激な眠気に襲われて午前1時半ごろ布団に入り、即座に寝た。

09/10(火)

午後1時半起床。院生室で麻雀しないかという誘いがLINEに来ていたので、シャワーを浴びて昨日買ったおにぎりを食べたあと、原付に乗って大学に向かった。

午後6時までかけて2半荘打った。今日の戦績はかなりひどく、上がったのは中のみの1回きり。聴牌すらほとんどなかった。こんなにも手がまとまらないと、さすがに運ではなく腕前に問題があるのだろう。7月末に麻雀を始めたばかりの後輩たちは雀魂で特訓しているらしく、いつの間にかかなり強くなっていた。これからも卓に誘ってもらうため、自分も練習しなければならないのかもしれない。

学食で食事して帰宅。原付を置いてすぐまた出発し、今度はゲーセンに行った。

今日は手元動画を撮りつつ閉店まで25クレプレイ。14+のAJ狙いをして三つ出せた。狙ったのにAJを出せなかった「AMAZING MIGHTYYYY!!!!」は、繰り返し出てくる配置に癖がついてしまい、それ以外がいくら上手くなってもどうしようもなかった。最高スコアは14-1-0。帰宅してからAJを断念した2譜面も含めて動画をツイートした。

帰り道で油そばを食べた。タレが普段の倍くらいあってかなりしょっぱかった。ドンキに寄ったらフロアの中央部分が清掃中だった。退かした商品で通路を塞いでいたため、迷路みたいになっていて面白かった。

帰宅してシャワーを浴びた後、朝までハーメルンを読んでいた。「大文豪に私はなる！」と「大文豪に私はなる！　R18版」を読了。面白かった。作家活動をするため世界経済新聞社と深く付き合っていたり、金獅子のシキの元に身を寄せたりと他の二次創作ではあまり見ない展開ばかりだった。

ただ作者の趣味なのか、作中最強格の女オリ主なのになかなかひどい目に遭わされているのが辛い。R18版はそれが行くところまで行ってしまったIFストーリーだが、本編内でもインペルダウンに収監される章ではR17.9のタグに見合うくらいの扱いを受けていた。さらし者の刑は百歩譲るとしても、なんでガチの拷問シーンがあるんですか……？

syosetu.org

syosetu.org

午前9時過ぎ就寝。

09/11(水)

午後1時半から午後2時半、午後6時から午後10時にハーメルンを読んでいた形跡がある。

午後11時半直前に目覚ましで起床。Codechef Starters 151に出た。

https://www.codechef.com/START151A

書く

その後もずっとハーメルンを読んでいた。午前4時くらいに椅子で寝落ち。1時間くらいで起きて布団に移動し、また寝た。

09/12(木)

正午に目覚ましで起床。生協に行って用事を済ませるつもりだったが布団からの脱出に失敗し、2時間ほどハーメルンを読んでから二度寝してしまった。次に起きたら午後6時半だった。

「〝鬼の女中〟と呼ばれる女」を読了。面白かった。大海賊時代より前から活動し、ロジャー海賊団にも所属していた主人公が、原作開始前の海に君臨している。悪魔の実を食べず、武術と覇気のみで海賊の頂点に立つところが良い。ところで、これだけ強大になるといざ原作が開始してもルフィと絡めるのは一苦労だと思う。ワンピース二次創作の宿命かもしれない。そもそも原作開始までたどり着ける作品が少ないという話もある。

syosetu.org

別のハーメルンを開いて読みだした。午後11時前に寝落ちする直前、次に起きたら朝になっているだろうなと思ったが、なぜか午前2時半ぐらいに起きてしまった。午前6時半くらいになって、一週間丸々ハーメルンに費やす危機感を覚えたこと、また読んでいたハーメルンにそこまで引き込まれなかったことからついに読むのを止めることに成功した。

シャワーを浴びて先週も行っていたpreprintの英語の修正を始めた。午前11時半くらいになると、昨日済ませる予定だった用事のため生協に向かった。

まず来週火曜日に千葉県へ行くための新幹線切符を購入した。東邦大学習志野キャンパスで行われるセミナーに参加する予定である。そして学食・購買を巡り、最後に床屋で散髪した。

帰宅してシャワーを浴び、しばらくpreprintを弄って午後3時半ごろ寝た。

09/13(金)

午後9時に目覚ましで起床。20分からyukicoder 446に出た。

yukicoder contest 446 - yukicoder

書く

今日は久しぶりにラノベを読んだ。2冊読了。

1冊目、「黄金の経験値」5巻。非常に面白かった。この巻では主人公が現実で身に着けていた能力がクローズアップされており、それを駆使して倒すことが想定されていないボスに打ち勝つ様が描かれた。そのような能力の背景となる主人公の現実世界における事情は、なろうだと全くと言っていいほど明らかにならないまま完結してしまったはず。書籍版で何か新情報が出るのではないかと期待している。

またページ数に余裕があったのか、主人公の配下を視点キャラクターとした番外編が追加されていた。本編がほぼずっと主人公の一人称視点で進むため、他者の視点からの主人公は貴重。配下が普段何を考えているのかということも明らかになって、これも非常に良かった。

2冊目、「願ってもない追放後からのスローライフ？」。現代ダンジョンもの。日本最強の冒険者だった主人公の、金に糸目を付けない日常は非常に良かった。ただ主人公のバトルシーンがほとんどなかったことが残念。思ったよりスローライフ成分に全振りしていた。さらに追放パートでは、追放者へのヘイトを煽るだけ煽ったのに回収が不十分だったり和解してしまったりと中途半端な結末だったのが気になった。

午前11時過ぎに就寝。

09/14(土)

午後3時起床。両親が部屋にやって来た。水回りの掃除をしてもらいつつ、自分は読み終えた本を実家に持って帰ってもらうため段ボールに詰めていた。昨年2月に本棚を新規購入して以来である。その本棚も今年の5月に一杯になってしまったので、それからは部屋のテーブルに積み上げていた。しかしそもそも実家の本棚がとうの昔に一杯になっている以上、持って帰るのは問題の先送りにしかならない。

段ボール5箱分の本を車に積み込み、またプログラミングコンテストの賞品を主とする不要だが保管したいものも持ち出して部屋の整理は完了。夕食のため午後5時くらいに部屋を出発した。

仙台駅地下の海鮮丼屋に並んだら、どうやら席の半分近くが予約されていたようで、我々の前に3組しかいなかったのに1時間ほど待つ羽目になった。ようやく入店して注文してからも料理が出てくるまで30分ほどかかり、午後7時を過ぎてようやく夕食にありついた。店員が少ないわけでもなさそうだが、一体何が起こっていたのだろうか。

午後8時過ぎに帰宅し、いったん両親と別れた。明日は観光についていく予定。あまりに眠いので机に突っ伏して少しだけ仮眠を取り、午後9時からABC371に出た。

AtCoder Beginner Contest 371 - AtCoder

Aは実装方針が全然立たなかった。結局比較関数を書いてソートした。Bはよい。Cは頂点番号の対応を全探索。Dは二分探索。Eは各値に対し最初に出現するインデックスを見る、値の種類数クエリでよく使うテク。

FはまずX_i\leftarrow X_i-iとすることで条件を狭義単調増加から広義単調増加に書き換えておく。すると用事を完了するためには邪魔になる人もろとも目的の座標までずらせばよく、邪魔になる人の範囲を検出するためには1点取得が、移動距離を計算するためには区間和が、更新のためには区間updateができればよいため遅延セグ木に乗る。

Gは先頭から貪欲に決めていけば常に操作回数kの条件がk\equiv r\pmod mと書ける。新たに長さ\ellのサイクルが出現した場合は、k\equiv r\pmod{\gcd(m,\ell)}のもとで最も先頭に近い値を最小化し、rとmを更新すればよい。普通に書くとオーバーフローするため、rとmは素因数分解した形で管理し、適宜中国剰余定理で戻した。

全完12位。コードゴルフのためAをNibblesで、EをPerlで書いた。Aは入力が6パターンしかなく、全部並べて観察したところS_{\mathrm{BC}}が入力中の何文字目に初めて出現するかでピッタリ分類できることが分かった。謎のハッシュで同じ長さを達成しているコードがあり、こちらはよくわからない。

www.youtube.com

午後11時半からはCF #972 div.2に出た。

Dashboard - Codeforces Round 972 (Div. 2) - Codeforces

書く

www.youtube.com

「小市民シリーズ」のアニメ第2期が制作されるらしい。TLを見る限り今期のアニメはロシデレがひたすら目立っていた感じだが、こちらも2期が出るくらい人気があったということで、めでたい話である。

ハーメルンを読んで午前4時過ぎ就寝。

09/15(日)

午前9時、迎えに来た両親に起こされた。朝食を摂って出発。まずは自分の用事で郵便局に寄ってもらった。

Universal Cup Semifinalsの賞品は、チームのうち一人が代表して受け取り、他の二人に分配するというシステムになっている。我がチームでは自分の住所を運営に伝えており、昨日寝ている間にスマートウォッチが届いていた。チームメイトの住所はすでに教えてもらってある。ブツだけ持って向かったが、郵便局で梱包材を売っていたので問題なく梱包でき、レターパックで発送した。

いよいよ観光。まずは鬼首かんけつ泉を見た。ここで最後に食べた温泉卵は、たった60円なのにお盆・皿に調味料2種がついてきてびっくりした。3倍くらいの値段でも何もおかしくない。ちなみに自分で茹でる場合は50円らしい。

【公式】間欠泉 鬼首かんけつ泉

次に近くの岩下こけし資料館。館内撮影禁止。資料館というよりはただの販売所かな……。一応、古文書の写真と古そうな木工品が置かれていたものの、照明がないためガラスの反射でよく見えないし、そもそもまともな説明がほとんどなかった。母はふくろうの置物を買っていた。昔似たものが実家にあったが、足が折れてしまったらしい。

岩下こけし資料館 – こけしの資料を展示・販売・絵付体験

「あ・ら・伊達な道の駅」で昼食。周囲のさびれ具合に見合わない人出で大混雑だった。横綱・白鵬の全勝優勝額が展示されていてびっくりしたが、震災の復興支援で関りがあったらしい。

あ・ら・伊達な道の駅

午後は「感覚ミュージアム」に行った。ここも撮影禁止の展示が多い。暗い通路を手探りで歩きつつ、穴の中に手を差し入れて中に置かれているものを触感で確かめる「闇の森」という展示が面白かった。

感覚ミュージアム

これで観光は終わり。イオンモール富谷で買い物をし、ココスで夕食を摂った。にじさんじコラボの期間だったので、対象メニューを注文してクリアファイルを手に入れた。四季凪アキラさんだった。

午後8時前に帰宅し両親と別れた。

AHC037が始まっていたので、1時間遅れで参加した。x=yという直線で点を二つに分け、それぞれX軸・Y軸から枝分かれさせるような貪欲を書き、点の分割を山登りして4200725105点。計算が重かったので焼きなましにする気力は失せてしまった。また順位表からとても強い貪欲があることはわかっていたが、それらしいものが何も思いつかなかった。

11th Asprova Programming Contest（AtCoder Heuristic Contest 037） - AtCoder

1時間半くらいで投げ出し、ハーメルンを読んでいたらコンテストが終了した。強い貪欲は「2点(a,b),(c,d)を除いて点(x,y)=(\min(a,c),\min(b,d))を追加する、ただしx+yが最大となるように選ぶ」というものだったらしい。マージすることは思いついていたものの、選ぶ基準が全然わからなかった。確かにこれだと右上から処理していきたい気持ちがうまく表現されている。

布団に移動して午後11時半ごろ就寝。

週記（2024/09/02-2024/09/08）

09/02(月)

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

先週は以前から関わっているツールについての調査を依頼された。念願のタスクだが、まだ稼働できていない。進捗報告はこれで終わりで、今週はちょっとした事情で勉強会がなくなったため、普段よりかなり早く解散となった。

まだ購買が開いている時間だったので、向かってお菓子とラノベを買い、開店直後の学食で夕食を摂って帰宅。それからはずっと先週の週記を書いていた。

午後7時にAHC036が終了した。自分は結局、初日に1回提出したきりとなってしまった。解法は適当な頂点を根としてdfs木を取りその上だけ移動するというもの。全域木としてdfs木を選んだのは、より長いパスがあると嬉しいと思ったからだった。配列Aは頂点をdfs順に並べて作成し、配列Bは毎回すべて書き換えることにして最も遠くまで進めるものを貪欲に選んだ。

シード0で試したらサンプルよりスコアが悪かったのだが、試しに提出してみたところ、順位表のサンプルそのままと思しき団体より上に位置していてびっくりした。シード0はL_B=5という点で少し特殊なケースだったらしい。感想戦をチラ見すると、初手で木を作る部分だけは当たっていたようだ。

RECRUIT Nihonbashi Half Marathon 2024 Summer（AtCoder Heuristic Contest 036） - AtCoder

午後11時半に先週の週記を投稿。Univarsal Cupを除いてすべて書き切ることができた。先週はハーメルンに捧げた週だった。今日も投稿後は朝方までずっとハーメルンを読んでいた。

「Game of Vampire」の「アンネリーゼ・バートリと幻想の守護者」章を読了。この章の敵は不死身のため勝った気がしない。彼女の思想に主人公が惹かれているのも、先週読んだ章と同じく好ましくない。しかしどちらの敵も動機は十分説明されており、それは理屈の上では理解できるものだった。自分が拒否反応を起こしているのは前半が重厚すぎて舌が肥えてしまったからかも。ともかくこれにて「Game of Vampire」のすべてのイベントは終了し、あとは少しのエピローグを残すのみである。

シャワーを浴びてゴミをまとめ、布団に入った。しばらくハーメルンを読んで午前6時半就寝。

09/03(火)

午前10時起床。今日はホスフィンの研究室にお邪魔して研究合宿を行う。昨日約束した時間は……午前10時。遅刻である。

今日は天気が悪いらしいが、雨合羽を持って原付で出発。太陽が出ておらず信じられないくらい寒い。購買でパンを買いつつ研究室に向かった。

合宿では春に公開したpreprintを加筆修正していた。昼食は午後1時に学食で摂り、その後大学図書館の工学分館で参考文献を借り出した。夕食は午後6時半ごろ、地下鉄で街に出て「隠れ家洋食の店 ぴかぴかぶー」に入り、サラダと大盛りのペペロンチーノを食べた。スーパーで買い物をして戻った。

午後10時半に解散。今日は加筆修正のうち加筆部分をひとまず終わらせることができた。明日も午前9時から集まる約束なので、そこで修正部分を進めていきたい。早い時間から合宿を始めるのは、午前の時間を長く取るのが良いだろうという考えからである。

帰宅してシャワーを浴び、午後11時半からCF #971 div.4に出た。

Dashboard - Codeforces Round 971 (Div. 4) - Codeforces

A、Bはよい。Cは\lceil x/k\rceilと\lceil y/k\rceilを見て算数。Dは特殊な直角三角形がちゃんとサンプルに用意されていて優しい。Eは絶対値を外した値の符号が切り替わるところを二分探索で求めた。Fはf(r)-f(l-1)にして計算。

Gは、まずすべての幅kの区間についてfを求める。a_i\leftarrow a_i-iとすれば最頻値の出現回数が分かればよく、区間をずらしながら求めていける。これでG1は解けた。幅kより広い区間に対するfは求めた値の区間MINだから、lを降順に見ながら右向きの累積MINをstackで管理するテクと区間更新区間和取得の遅延セグ木でG2も求まる。

G3は大変だが、これもまあ見たことがないではない。G2の区間更新の代わりにlを掛けて区間ADDを行い、また更新される区間については-lを掛けて再度区間ADDを行うことにすると、その値が出現してから消えるまでの寄与の和が得られる。こうして更新した遅延セグ木の区間和はだいたい答えになっている。

ところがG2のコードを流用してG3を書いたら作用素でオーバーフローしてしまった。区間更新ならint型でよかったが、区間ADDだとlong long型にする必要がある。ジャッジが詰まりまくっており、結果が返ってくるまで10分ほど待たされるこの状況で1ペナは非常に大きい。次の提出でちゃんと合わせたものの、残念ながら2位となった。

www.youtube.com

午前4時過ぎ、ついにハーメルン「Game of Vampire」を読了した。およそ2週間弱で駆け抜けたことになる。後半の章についてはどれも嫌いな点をあげつらってしまったが、それでもぐいぐい読み進めていけたのは確か。またちょくちょく挟まれるホグワーツのシーンだったりゲラート・グリンデルバルドとのシーンだったりは常に良いものだった。前半については言うまでもない。やはり最高だった。

syosetu.org

これを読んでいる間に「とある黒猫になった男の後悔日誌」が読みたくなってきていたので、次にそれを開いた。昨年3月に最新話まで追いついて以来読んでおらず、一年半分の更新が溜まっている。量も少ないので最初から読み返すことにした。

syosetu.org

主人公の慇懃な口調とはっちゃけた内心に面食らったが、そういえばそういう文章だった。展開は文句なく面白い。読み進める手が止まらず、午前6時になってようやく寝た。

09/04(水)

午前9時起床。今日も遅刻。スーパーで買ってきたパンを食べて出発した。昨日とは異なり少し天気が良く、暖かい。暑くはない。

今日はpreprintの英語の修正をしていたが、全然進まなかった。昨日の時点でかなり眠気に負けていたのにうっかりさらに睡眠時間を削ってしまって、輪をかけて使い物にならなかった。昼食は午後1時ごろに農学部のほうの学食で摂った。

午後6時解散。合宿はこの二日で終わりである。数学棟近くの学食で夕食を済ませたあと院生室に顔を出したら友人が二人いて、かなり長い間雑談をした。午後10時帰宅。

眠気でぼんやりしつつTLを眺めていたら午後11時半になったので、久しぶりにCodechefに出た。今日はStarters 150。

https://www.codechef.com/START150A

書く

ハーメルンを読んで午前5時半就寝。

09/05(木)

正午起床。今日が締め切りの書類を提出するため、この日は日付が変わるまで指導教員とメールのラリーを続けていた。メールとメールの合間は、午後2時から午後5時までは寝ていて、それ以外はハーメルンを読んでいた。

日付が変わってからはハーメルンに没頭。午後0時半に寝落ちするまで読みふけっていた。

09/06(金)

午後6時半起床。

ハーメルン「とある黒猫になった男の後悔日誌」を読了した。非常に面白かった。前回自分が読んだところより先では話がどんどんどんどん大きくなっていき、海軍とも世界政府ともぶっといパイプを築き上げ、その上海軍大将を一騎打ちで撃破して懸賞金が跳ね上がった。この二つを両立させた展開というのもまた面白い。

syosetu.org

午後9時20分からyukicoder 444に出た。

yukicoder contest 444 - yukicoder

書く

少しだけ日記を書いた後はまたずっとハーメルン。今度は「ヒエヒエの実を食べた少女の話」で、1年ちょっと溜めていた更新だけ読んでいた。午前7時くらいに読了。

この作品の主人公はかなり昔に王下七武海入りし、自身並びに配下の懸賞金が一切更新されないまま二十年ほど経過していた。ところがここ数話でついに脱退。現在の彼女たちの危険度がどう評価されるのか、かなり気になる。そのほかにも今ちょうどいくつかの大きなイベントが同時並行で起こっているようで、なんとももどかしいタイミングで読んでしまったなと思った。

syosetu.org

また、いつの間にか番外編「ヒエヒエの実を食べた少女の話エクストラ」が生えていたため、こちらも読んでおいた。

syosetu.org

ワンピース原作の二次創作がまだ読み足りない。ハーメルンを漁って「大文豪に私はなる！」を読み始めた。冒頭から主人公の故郷が滅ぼされたり奴隷として売られたりで大変な目に遭ってばかり。貞操の危機に陥ったときはかなり冷や冷やしたが、このときは何とかセーフだった。

syosetu.org

午前10時前に寝落ちした。

09/07(土)

午後1時半起床。午後2時からUniversal Cupに出た。今日は9回目、Xi'anセット。

https://qoj.ac/contest/1784

書く

今日のABCはG問題が650点となっている。コンテスト中に全完できるかかなり怪しく、録画時間は振り返りまで含めれば確実に2時間を超えるだろう。つまり午後11時からのTROCも一緒に録画することになる。

このコンテストサイトは、ページのボタンをクリックして開いたエクスプローラーから選択するという形式のファイル提出しかできない。しかし今、エクスプローラーを録画に映り込ませたくない事情がある。解決策は非常に簡単だった。エクスプローラーが開く位置は前回のものを記憶しているようだから、前もって録画しているモニターの外に追いやっておけばよいのだ。

そういう準備を整え、午後9時からABC370。

Toyota Programming Contest 2024#9（AtCoder Beginner Contest 370） - AtCoder

Aは面倒。Bはやるだけ。Cは1文字ずつ揃えていく必要がある。辞書順最小を達成するのは簡単。Dは縦と横それぞれsetで壁を持つ。Eはdp。

Fはかなり手間取った。円環をどこかで切り開き、質量が\min(w)以上となる最低限の区間をどんどん切り出して一周するまでにK人分用意できるか確かめたい。二つ目の出力のことを考えると、N種類すべての位置で切り開いてそれぞれチェックしなければならないが、これにはダブリングが使える。判定問題がO(N\log K)で解けたので、OK。

手間取ったのは「一周」の判定だった。無理やり値域を[0,N)にしたら、ピースを一つも切り出していない状態と一周丸々切り出した状態が区別できなくなってしまったのだ。気合いを入れて実装すれば回避できると思っていたのに失敗してタイムロス。結局値域を[0,2N)にして解決した。

Gは惜しいところまで行ったと思ったが、有名手法が使える形にはできておらず、自分で実装したことのないライブラリを弄る必要が生じて手が出なかった。6完18位。

午後11時からはTROC #38に出た。

https://tlx.toki.id/contests/troc-38

書く

ABC-Gのupsolveをした。基本方針はBlack Algorithmというやつで、頂点n\gt 1について最大素因数をp、その重複度をeとすると親がn/p^eとなるような木を考えた。降りるときに\left(1+p+\dots+p^e\right)\bmod{3}を見て、n=\prod Aが良い整数かどうかを判定。

乗法的関数のprefix sum | Nyaan’s Library

このとき、\lfloor N/n\rfloor以下の「素数」の個数と「素数かつ3で割って2余るもの」の個数が必要になる。前者は普通の素数カウントで手に入るから、後者も同様の手法で計算できるだろうと思った。ここまでがコンテスト中に考えられたこと。素数カウントは自分で書いていないのみならず、以下のページにある丁寧な解説も読み解いたことがなかった。

素数カウント( $\mathrm{O}(\frac{N^{\frac{3}{4}}}{\log N})$ ) | Nyaan’s Library

今日改めて読むと、h(x,n):=\#\{2\le v\le n\mid v\in\mathrm{Prime}\lor\mathrm{lpf}(v)\gt x\}であるらしい。h(x,n)はh(x-1,n)から\{v\le n\mid v\notin\mathrm{Prime}\land\mathrm{lpf}(v)=x\}を除いたものになり、xが素数かつx^2\le nならばこれは\{v\times x\mid v\le n/x\land\mathrm{lpf}(v)\ge x\}と一対一対応する。そのサイズはh(x-1,n/x)-\pi(x-1)=h(x-1,n/x)-h(x-1,x-1)であり、確かに解説の漸化式を満たす。

これを応用して、さらに(v\bmod 3)=2という条件を加えたい。漸化式がどういう理屈になっているか考えると、x\bmod 3に応じて(v\bmod 3)=1という状態から遷移してくることもあると分かった。というわけで、両方管理すればよい。\sqrt Nで分けるのが面倒だったので\sqrt{10^{10}}より少し大きな定数を使ったら、結構実装が楽になった。

二つのコンテストの振り返りまで終え、6時間に渡る録画が完了した。普段ならすぐアップロードするが、今日は途中で誤クリックによりTwitterのタイムラインを映してしまったので、確認の必要がある。該当箇所を探し出すと、なんとも間の悪いことに鍵アカウントのツイートが見えてしまっていた。AviUtlで編集してモザイクをかけねばならない。

何しろ動画が6時間もあるから、ソフトへの読み込みだけで長大な時間がかかってしまった。しかも動画のフレーム数上限を突破していたため、設定を更新して再度読み込む羽目になった。編集で数秒だけモザイクをかけ、今度はエンコードに2時間半。動画が公開できたのは午前8時のことだった。

www.youtube.com

その作業の待ち時間ではずっとハーメルンを読んでいた。午前9時半就寝。

09/08(日)

午後5時半くらいに目を覚ました。今日はコンテストがない……と思っていたら昼過ぎにyukicoderがあったらしい。がっくり。逃したものは仕方ないとして、夜何もないのは確かだからゲーセンに行こうと考えていた。

しかしハーメルンを読むのが止められない。しかも、寝転がったままスマホを凝視していたら午後7時半くらいにうっかり寝落ちして、気づいたら3時間が経過していた。もう外出するような時間ではなくなってしまった。仕方がないのでそのまま延々とハーメルンを読んでいた。

日付が変わり、午前10時くらいになってようやく布団を脱出。まともな食事をせず、水分もあまり摂らずにずっと横たわっていたせいか、頭はぼんやりするし体は重いしかなり辛かった。もしかしたら眠気もあったのかもしれない。何とかシャワーを浴びて洗濯しつつ日記を書き、午後1時過ぎに就寝。