12/15(月)

午後3時過ぎ起床。半からインターン先の定例会に出席した。Yandex CupとAtCoder Japan Openに行ってきたという報告をした。

勉強会は全方位木dpの話。普段木dpを雰囲気で書いているのでライブラリ化できるほど整理した考え方には慣れない。しかしフルスクラッチで実装するたび面倒だなと感じているのも確か。

週記をかなり溜めてしまっている。三週間前の分を書き上げ、その次の週に手をつけ始めたくらいで耐え難い眠気に襲われた。とりあえず書けた週だけ投稿して布団に倒れ込み、就寝。午後10時だった。

12/16(火)

午前3時起床。

剣持刀也さんと月ノ美兎さんによる「水流のロック」の歌動画が公開されていた。てっきり半年前の3Dライブの切り抜きだと思っていたので、改めて歌ったものと知りとても嬉しかった。

www.youtube.com

昨日あった剣持刀也さんの3Dライブのアーカイブを見ていた。月ノ美兎さんとのデュエット「水流のロック」が最高。
週記（2025/06/02-2025/06/08） - kotatsugameの日記

週記を書き進めていたが途中で集中が切れてラノベに移行。「じゃあ俺だけネトゲのキャラ使うわ」を読んだ。

同一人物だと知られていない複数の人間を演じ分ける設定が非常に好み。テンプレ要素も良かったが、ざまぁパートだけは気に入らなかった。あんまり大したこともされていないのに恨みすぎではないか。強者としての余裕をもっと出してほしかった。

午後4時ごろ大学生協へ向かった。先週注文した本のうち、すでに発売されていたものが14冊届いたので受け取った。生協のプリペイドカードの残高が足りなくてチャージする際、上限だと思っていた五万円を超えないように調整していたら、今はもっと多くチャージできると言われた。いつの間に変わったのか。

学食で食事。度重なる値上げの末、ついに川内キャンパスの学食からも牛乳が姿を消してしまった。今は100mlパックの野菜ジュースが売っている。牛乳が飲みたければ購買で買えとのことである。

帰宅してすぐ寝てしまった。午後6時。

12/17(水)

午前1時起床。小刻みな睡眠を挟みつつ、今日はラノベを四冊読んだ。

「特級探索者、配信者となる」。カクヨムで大好きだった作品の書籍化。ダンジョン攻略以外には目もくれない主人公のストイックさが好みだった。しかし改めて読み返すと、特別面白いとも言えない。Web版を初めて読んでから3年近く経つ間に、ダンジョン配信ものにたくさん触れたからかも。

「1/nのワトソン」。Vtuberが動画で提示する「依頼」に対し、リスナーが何らかの形で解決を与え、その相応しさを競う話。二件目までは知り合いを頼る一方で主人公の貢献が薄いように見えたが、三件目は自分でいろいろ動いてくれたので満足。生成AIが背景にあった「依頼」では出力の再現性について補足されており、エンジニアを主人公に据えるだけはある細やかな気遣いが伺えたのも良かった。

「一生働きたくない俺が、クラスメイトの大人気アイドルに懐かれたら」8巻。面白かった。7巻同様にヒロイン三人とのラブコメイベントが偏りなく描かれていたが、今巻では新キャラが登場し、また各ヒロインについてこれまでのイメージと異なる新しい姿を発見するという目的があったためか、単調さは感じなかった。8巻以降はアイドルのマネージャー業務にも関わっていくようで、非常に楽しみ。

「無限魔力の異世界帰還者」。町中にいきなりモンスターがポップして社会が大変なことになるタイプの現代ダンジョンもの。主人公の無限魔力チートを際立たせるためか、魔力運用がかなり難しい設定になっており、普通の人がダンジョン攻略に踏み出すのはほとんど不可能だろう。主人公一人が活躍するのはいいが、それで社会に平和を取り戻すまでの途方もない道のりを思うとちょっと絶望してしまう。

日付が変わるころ就寝。

12/18(木)

午前2時半起床。

「夜隆くん家の六姉妹」を読んだ。面白かった。六姉妹という設定が非常に良い。多彩なヒロインが登場し、互いに家族愛という好意を抱いているもののしかし決して恋愛感情には発展しない心地よさ。当然それだけでは小説にならないわけで、この作品は「魔女」というちょっと突飛な装置を組み込んでいる。悪くないことは確かだが、自分にとってはやはり六姉妹であることがメインだった。

うっかり水曜日を溶かしてしまったが今日はセミナーがある。慌てて準備を開始した。正午を回って登校。食事して、午後1時半からセミナー開始。

一応話すことは二つほど考えてあったのだが、一つ目で全ての時間を使い果たした。ほとんど以前の内容を振り返っているだけだった気がする。隔週以上の間隔でやっているのだから、ちゃんと毎回独立して聞けるよう準備すべき。

夜は院生室で駄弁ったり学食に行ったり。先月の集中講義のレポートは、問題を解いただけで清書しないまま期限が近づいてきている。TeX打ちを始めたが早々に飽きて寝てしまった。

集中講義のレポート問題を解いていた。簡単すぎるもの、記述があまりに面倒すぎるもの、わからないものを除くとちょうどよい分量になった。ノートPCを持ってきていないので、TeX打ちはまた今度。
週記（2025/11/17-2025/11/23） - kotatsugameの日記

午後11時を過ぎて目を覚まし、帰宅。午前1時就寝。

12/19(金)

午前4時半起床。寝たり起きたりしながらラノベを読んでいた。

「黄金の経験値」8巻を読了。大陸大戦の序盤を描く巻で、各勢力がどのように大戦に臨むか説明された。主人公たちは暗躍してばかりで表立っての活躍はなし。恒例となっていた見開きの挿絵もなかった。でも、それでもよい。面白かったというよりは満足したというのが近い。

午後11時半からCGR31に出た。

Dashboard - Codeforces Global Round 31 (Div. 1 + Div. 2) - Codeforces

Aは始点に戻るまでシミュレート。Bは毎回小さい方を選んでよい。Cは $k$ が奇数のとき $(0,n,\dots,n)$ を出してまんまと1WA。うまく散らばらせると下のbitを立てられるようになる。

Dはある円の半径を決めたとき、それより左で最大から高々1しか損しない。まったく損しない半径がなす開区間を管理しつつ右に進んでいった。 $n\le 2\times 10^5$ だと思っていて配列サイズが足りず1WA。なぜこの制約になっているのか。

Eは $x$ の最上位bitを固定して、それが可能か判定する。下がすべて0またはすべて1というパターンのみチェックすれば十分。こうして得られた数は、可能な $x$ たちがなす空間のXOR基底となっている。

F1は各マスに到達する確率をdpで求める。マスの左下と右上がそれぞれ移動を邪魔する向きになっているか、という四つの状態を持てば遷移ができた。確率なので $n$ や $m$ の値に依らず、最初に全体を前計算できる。クエリごとに二次元累積和で必要なところだけ取り出せばOK。F2はこれを行列累乗にする。あらかじめ制約を見ていたので、F1の時点で書き直しやすい実装を意識できた。

Gはそもそもゼロ除算がなぜ発生しないのかわからない。solved数を見てH1に進んだ。

パラメータは四つあるが、とりあえず $(r,d):=(x-c,b-a)$ の二つで書ける。これでGrundy数を実験してみると、かなり規則的なパターンが見えた。まず $d$ が2べきの場合に帰着でき、 $r$ に対して周期 $2d$ を持つ。あとは $d/2$ のケースから帰納的に求められる。

必要なのは、 $r$ が区間をなす場合の総XORである。ここでパターンを眺めていて気づいたが、 $r\lt 2$ 以外は同じ数が二つずつ登場している。つまりXORを取る場合、端以外はほとんど消えてくれるようだ。1点に対してGrundy数を求めるのは、先程の議論ですでに $O(\log d)$ になっている。

残り5分で提出すると無事通った。システスでも無事で8完、なんと全体3位。レートはこれまでで最大の上がり幅を見せ、2900→3138(+238)で一気にLGMに戻ってきた、どころか初めて3100を超え、二年ぶりにhighestを更新した。

さらにCGRの年間成績上位者に配られるパーカーが貰える見込み。Yandex Cupでturmaxさんが着ているのを見かけ、いいなと思っていたところだったのでかなり嬉しい。

www.youtube.com

午前9時就寝。

12/20(土)

正午前に起床。この時間からUniversal Cupを走る予定だったが、まだコンテストの準備ができていなかった。

しばらくハーメルンを読んでから二度寝し、起きると午後8時半。午後9時からABC437に出た。

UNIQUE VISION Programming Contest 2025 Christmas (AtCoder Beginner Contest 437) - AtCoder

Aはよい。Bは $B$ を後から入力されるのが少し面倒。Cは $W+P$ を見て貪欲。Dは答えが大きくなるのでmodを取る必要がある。Eはtrie木。Fは符号の付け方四通りそれぞれでセグ木を持った。

Gは各頂点に対して、周囲の辺をどの順番で消すか考えるのがポイント。実はどんな順序にしても、全頂点でそれを同時に達成するような方法が存在する。また消すタイミングにおける色がわかるので、可能かどうかの判定もできる。この言い換えをすると、隣接する頂点に対して適切な順番を予約するようなマッチング問題を解くことになる。サイズ $N-1$ のマッチングが見つかったら、構成から自動的にすべての辺が一回ずつ使われる。構築は一本一本消せる辺を見つけても $O(N^2)$ 。

最大流の計算量がわからないままDinicは速い！と叫んで投げたが、今回は流量が $N-1$ なのでそれで抑えられる。各頂点に対して次数の分だけ頂点を作るのではなく、三色分に圧縮しておかないと一回の探索が $O(N)$ にならないことには注意。

57分で全完して2位。後から見たら1位はBANされていた。

www.youtube.com

午後11時からMHC Finalがあったので、順位表をチラチラ確認し、コンテスト後の結果発表ライブまで見届けた。なんだかWAの数が多いような気がする。validationが弱かったのだろうか。NyaanさんのC問題のWAは、二つとも入力が上三角行列ではなく下三角行列であることに気づかなかったことが主因と聞いた。validationに入っていたケースは成分がすべて同じ値だったらしい。とても気の毒。SRMが消えた今、このような一発勝負の練習を積む機会はないように見える。まったく、嫌な形式だ。

Scoreboard | Meta Hacker Cup - 2025 - Final Round

https://fb.watch/EjT3vk7UlQ/

ラノベを読んで午前8時就寝。

12/21(日)

正午起床。夜のAGCに備えてもっと寝ておきたいのに眠気が来ない。ラノベに手を伸ばした。

「汝、暗君を愛せよ」2巻を読了。難しい！読むのに時間がかかるし、時間をかけたうえで内容が十分読み取れているという感触はない。自分の理解は次のようなもの。

王としての責任に真っ向から向き合うか、受け流すかという選択がこの巻のメイン。主人公の持つ現代日本的な価値観（「ぼく」）では向き合わざるを得なかったが、その責任の重さに耐えきれず破綻しかけていた。そのとき子が生まれ、それをきっかけとして受け流す術（王の器）を身に着けた。よって帯にもある通り、「ぼく」が死んで「王」が生まれたのである。

責任に向き合うべきだというのではなく、向き合わざるを得ないというのがポイント。主人公はどちらが良い・悪いの判断を下していない。よって受け流す術を身に着けることは単なる逃避ではなく、一種の成長とも見なせる。こういう考え方をしておくと、ずっと重苦しい雰囲気だった2巻にも一つ救いがあったかなという気になる。

午後5時過ぎにようやく二度寝して、起きたらコンテスト30分前だった。急いで食事して、午後9時からAGC075。

AtCoder Grand Contest 075 - AtCoder

Aは……これはどうすればよかったのか。 $N$ が偶数の場合は上下半々に分ければよい。 $N$ が奇数の場合を実験したら大量に見つかったので、きれいなものを探そうとした。ここまでは良いとして、どのように探すかが問題。

同じ文字ができるだけ長方形をなすように固まっているものがきれいだと思い、幅と高さを固定して境界の凹凸を全探索してみた。しかし大きな $N$ では思うように見つからないし、たとえ存在したとしても構成は簡単ではない。境界を1文字flipすることによる差分が線形に作用すると思っていたが、flipした文字から別のflipした文字へ移動する経路のことを考えていなかった。

1時間ほど試してようやく諦め、別のきれいさを求めて対称行列だけ探すことにした。これが大正解。 $N=7$ で最初に見つかった例が、公式解説と同じ構成だった。半信半疑で一般化するとすべてうまく行く。これでようやくACすることができた。このA問題はすでに200人以上に解かれており、目の前が真っ暗になった。

次にBに進んだが、あまりまともな考察はできず。20分ほど消費したあと、順位表を見てDに移った。

末尾の要素を固定すると、他の要素はたかだか一つを除いてすべて $\sqrt K$ 以下になる。なんだかいけそう。その $\sqrt K$ を超える要素を固定してもなお $O(K^2)$ なので、残りの数え上げを高速に行えば間に合う。

具体的な上限 $m$ を数式で表し、いろいろ試してみると、 $m-1$ 以下はいくらあっても条件を破壊しないことが判明した。よって $m$ がいくつ、どこにあるかが問題。このあたりからは実装を進めながら、漏れが無いよう場合分けを進めていった。正しく計算することを第一目標として、すぐ閉じた形になりそうな $O(N)$ のループはガンガン使った。

残り20分を切る中なんとか書き上げ、サンプルを試す。残念ながら一発では合わなかったが、要素の個数に関する勘違いを修正するだけで直ってくれた。場合分けパートには一切ミスがなかったらしい。ここが間違っていたら流石に修正不可能だった。あとは $O(N)$ のループを書き直すだけ。Wolfram|Alphaをせっつきながら実装し、みごと $O(K^2(\log N+\log\mathrm{mod}))$ が出来上がった。

しかし最大ケースを試すと間に合わない！自分のPCが特別遅いことを信じ、pragmaやmint::rawを加えつつコードテストで実行してみると、TL 3secのところ4.2secほどかかってしまっていた。残り3分。ちょっとした定数倍高速化はなんの役にも立たず、そのままコンテスト時間が終わってしまった。

やはり $O(\log N+\log\mathrm{mod})$ を定数時間にしなければならない。落ち着いた状態でコードを読み直すと、 $K$ 以下の数の $N-3$ 乗や逆元を求めるばかりだったので、すべて前計算しておけることに気づいた。これで爆速になって、コンテスト終了から11分後にACした。

結果はAのみ遅めの1完、254位。パフォーマンス2004でレートは2949→2882(-67)となった。D問題はBMBMが通ったとかで、最終的に100人近くがACしていた。間に合っていてもパフォーマンスは500ほどしか変わらなかったらしい。負けが大負けになったぐらいなら、もういいか……。悔しさよりも虚無感があった。

www.youtube.com

日記を書いて午前11時過ぎ就寝。