09/29(月)

午後3時起床、半からインターン先定例会に出席。今週も報告することは何もなし。

勉強会ではWeb Audio APIが扱われた。信号が生成されてから出力されるまでの間に、通過したノードによって処理が加えられていくという設計らしいが、関数型言語のような雰囲気を感じて面白かった。

大学生協に行ってラノベを購入した。店員さんが、レジに通したものをカウンターに積む際、表紙イラストが過激なものだけ裏向きにしていたところに細やかな気遣いを感じた。

学食で食事して、帰宅した後は日付が変わるまで週記を書いていた。土日部分まで手が回りきらないまま投稿。

9月初めに十六並列で回し始めたプログラムがまだずっと動いており、最近排熱で暑くて参っている。PCの挙動にラグが見られたので確認すると、メモリ使用量が限界に達していた。一つ一つのプロセスが一桁パーセントしか使わない様子だったので問題ないなと思っていたのだが、冷静になるとこれが十六倍されるわけで、結構まずいようだ。とりあえず放置。

午前1時半就寝。

09/30(火)

午前8時過ぎ起床。午前中は先週の週記に内容を書き足していた。午後からはラノベ。

午後3時過ぎ、例年より数日遅れて学振の結果が出た。結果は……不採用B。不採用者のうち上位20%～50%に位置していることになるが、Tスコアという申請者全体での指標は平均を下回っているため、ほとんど不採用Cとのボーダー上にいたことがわかる。とはいえもう正直、三連続不採用Cではなかっただけで満足。

昨年度と比較すると、研究計画はかなり具体性を増して記述できたと思うものの、評価はほとんど変わらなかった。一方で研究者としての将来性の評価はまあまあ伸びた。書類をほぼ一から書き直しているため確実なことは言えないが、まあ文章の内容ではなく成果物だろう。7月の国際会議が大きかったのではないか。

学振、不採用B。C×3じゃなかったことが嬉しい。三年間お疲れ！
— こたつがめ (@kotatsugame_t) 2025年9月30日

午後5時から5時間ほど寝ていた。起きてからまたラノベを読み、三冊読了。

一冊目、「地味なおじさん、実は英雄でした。」4巻。かなり面白かった。1巻から3巻でそれぞれ登場したヒロインたちが集合し、彼女たちの配信に主人公が自分から登場するというこれまでの集大成みたいな展開。主人公の過去も明らかになりつつあり、昔ともに戦ったキャラが数名登場して、主人公を取り巻く環境が一変しつつある。楽しみ。

二冊目、「稼ぎの少ないオカルト事務所所長、VTuberになる」2巻。Web版で読んだ範囲を少し越えた。ちょうど越えてすぐのところの展開には非常に驚かされた。このストーリーでVTuberモノと言っていいのか、あまりよくわからないまま進んでいくが、相変わらずクスッと笑えるやり取りが至る所にあって軽快に読み進められた。

三冊目、「転生して霊媒師になった俺、やたらと退魔師や妖にビビられる」。自身の特異性を過小評価している主人公の一人語りで進み、空気感は同作者の「カードゲームで世界が滅ぶ世界に転生してカードショップを開店したら、周囲から前作主人公だと思われている」とかなり似ている。しかし主人公の精神構造に由来する特殊さと言われても、読んでいて実感しづらい。

午前9時就寝。

10/01(水)

午後6時起床。

プログラムの進捗を確認したらログ出力の一部が更新されていなかった。走っているプロセスを数えてみると、なんと十六個中十一個しか残っていない。メモリが足りなくなったら適当に待ち時間が発生したりして、稼働時間が若干短くなりつつも満遍なく進んでいくものと勝手に期待していたが、そうではなかったらしい。

先々週のABC424が予選だったオンサイトコンテストに無事通過していたため、ホテルを取った。学生最強コンと同じ会場なのでホテルもいつもの西鉄イン新宿。後泊のため三連休初日の夜になってしまい、学生最強コンのときから値段が倍以上になってたまげている。これまでの経験上新宿である必要はあまりないが、まあどこで取っても高いだろうから許してほしい。

実は今日の日付が変わったころに一度検索をかけていて、その時すでにシングルルームは満室になっていた。ところが改めて調べると一つだけ空きが出ていたので、そこにすかさず予約。いつの間にかAmazon Payが使えるようになっていたので、アマギフで支払うことができた。ここで、なぜか支払いリンクが表示されず一敗。モタモタしている間に取られてしまうのではないかとひやひやした。

9月分の読書記録をツイートした。後半で失速。特に先週一冊も読めなかったのが痛い。一応大阪にも三冊持って行ったのだが、まったく手を付けられないまま持ち帰ってきてしまった。やはりスマホで読めるWeb小説が手軽すぎる。それでも、電子書籍に切り替えるつもりはない。

9月の集計
買った：24冊
読んだ：16冊
積読：+8冊
積読（累積）：+110冊
— こたつがめ (@kotatsugame_t) 2025年10月1日

午後9時半就寝。

10/02(木)

午前1時半起床。

今年のMHCの情報が出ていた。予選は例年午前2時からだが、今年はもろもろ遅れたこともあってRound 3がシアトルのサマータイム終了後になり、午前3時からとなっていた。日付だけ見ると自分の用事といくつか被っていて、時間が時間なのでどこで睡眠を取るか難しい。

Meta Hacker Cup 2025 Schedule - Codeforces

昼前まで論文を読んだりプログラムを書いて走らせたりしていた。メインで使っているWindows機にもWSLを使ってSageMathの環境を整え、そこで実行したのだが、計算が信じられないくらい遅くて仰天。学部入学のころから使っているし、もうさすがに世代遅れすぎるスペックなのかもしれない。

二度寝して起きたら午後4時過ぎになっていた。大学生協に行ってラノベを購入、加えて食事。

プログラムの出力を確認していたら計算が遅かった原因を発見した。有理数体上で計算させているつもりが、有理数係数の多変数多項式環上での計算になっていた。定数項しかないが、四則演算のオーバーヘッドが重すぎたのだろう。

また3時間弱寝たあと、日付が変わるまでラノベを読んでいた。

日付が変わってからは論文を読んだり考え事をしたり。Geminiにも聞いてみたが、堂々と「こういう研究がある」「こういう例が知られている」と言うくせ具体的に出せと問い詰めると存在しない文献を提示してくるので、肝心なところで役に立たなかった。

昼に学食に行ってからもしばらく続け、午後4時過ぎ就寝。

10/03(金)

午後8時半起床。

ハーメルンで「よう実　最速Aクラス卒業RTA Aクラス綾小路籠絡ルート」を再読した。三年前に読んだときは「よう実」のストーリーをほとんど知らなかったが、今は数多くの二次創作を読んだのである程度の知識があり、そこからの改変をより楽しめたものと思う。

syosetu.org

CF combinedに備えてPCの前に座ったらyukicoder 485が行われていたので、最後の40分程度だけ参加した。後ろから解いてHとGのみ。

yukicoder contest 485 - yukicoder

Hは $C_{i,j}$ の最大化をそれぞれ試す。関係する $B$ の最小値を集めてきて行和のインクリメント、列和のインクリメント、二つ同時のインクリメントそれぞれにかかるコストを求めると、実際にはそのうち二つしか使わなくてよい。各パターン立式すると二次関数になっているので、 $O(1)$ で最大値が求まる。

Gはまず縦横に分解する。始点の候補を各マスとその正反対の位置の $O(N)$ 個に絞り、それぞれに対して距離の和を求めたい。始点の位置に対する一次関数なので目的地ごとに区間ADDで処理できそうだが、そのままでは左右どちらから行くのが早いか考える必要があったりして収拾がつかない。

ここで、列を三倍くらいしておくと区間二つで表現できるようになる。サンプルを試して初めて答えの最小化ではなく最大化を求められていることに気付いたが、幸い始点の候補は変わらないため、単にMAXをとるだけで済んだ。

午後11時半からCF #1055 combined。

Dashboard - Squarepoint Challenge (Codeforces Round 1055, Div. 1 + Div. 2) - Codeforces

Aはuniqueして $2n-1$ 。

Bは難しかった。 $m$ ターンでKrugが移動でき、Doranが移動できないマスがあればよいとして二分探索。Krugが移動可能な範囲と盤面の共通部分の「端」をチェックする。実装もかなり手間取った。移動としてはまずどれかの辺に向かい、その後盤面の角を目指すことになるので、それぞれ最も進んだ先の八通りについて調べれば二分探索の必要はなかったらしい。

Cは同じ数字が隣接しているところを使えばコスト最小で操作を進めていける。よく考えると操作後にもそのような状態を必ず作れるため、コスト2になり得るのは最初の一手のみ。

Dは雰囲気だけで解いた。各数への操作だけ見たときも先手後手交互になるだろうと思い、先手が先に操作したときのスコア $x$ と後手が先に操作したときのスコア $y\ge x$ を求める。最後の操作が必ず先手のため一つだけ $x$ 、残りは $y$ 寄与するものとして提出するとWA。先手が最後まで操作しきる必要はないことに気づき、 $y\gt x$ について半分ずつ $x$ と $y$ で寄与するとしたら通った。

Eは面白かった。残っているインデックスすべてでクエリを投げ、返ってきたものを削除するという操作を繰り返す。このどこかで $n+1$ 個以上返ってきていればOK。そうでないとき、 $n$ クエリ後に残っているインデックスが必ず一つ以上存在し、 $n$ クエリ目の返答にはそれよりも「左上」にある要素が必ず含まれている。あとは同様に一つずつ辿ると単調減少な列を取れる。

Fは $O(n)$ で解くなら末尾二つを持って貪欲するのが正当。この貪欲をダブリングで高速化する。始点を $(l,l+1)$ として、それぞれ $z+1$ 以上大きな値を辿っていくが、途中で被ってしまうことがある。しかしこの場合一つずらすはずで、すると $(l',l'+1)$ となりまた別のクエリに帰着される。この $l\rightarrow l'$ でもダブリングを行う。

Gはまずモンスターのフラグを親との差に置き換える。これによってクエリが1点flipになる。出力はモンスターがいる頂点であって、自分の部分木にほかにモンスターがいないものを数えればよい。根からのパスに関する条件と、直接の子に関する条件と、孫以下すべての頂点に関する条件があるが、1点flipに対してはそれぞれ部分木更新・1点更新・パス更新となっており、HLD＋遅延セグ木に乗る。

Hは解けず、7完57位で3048→3019(-29)。あとからH1が単なるdfsで解けると聞いて、適当に根を決めて浅い頂点に重みを集めるようなコードを書いたら通った。なぜ根をすべて試さなくてもいいのかすらよくわかっていない。

www.youtube.com

その後朝までずっとハーメルンを読んでいた。

JetBrainsのパーカーと靴下が届いた。これは6月のMidnight Code Cupにおいて、JetBrainsが作問した問題で最高点を記録したことに対する賞品である。正確にはJetBrainsのWebストアで使用できるクーポンコードが賞品で、それをパーカーと靴下に換えた。

一人100ユーロ配布されたが、Webストアは送料が高いため、それぞれで買おうとするとあまりいいものは手に入らない。以前Constructor Open Cupという謎の大会で60ユーロ分もらったときもそこで挫折したはず。今回はrisujirohさんに三人分まとめて購入してもらい、個別発送までお願いした。感謝。

JetBrainsのパーカーと靴下 pic.twitter.com/q0dknd7dS2
— こたつがめ (@kotatsugame_t) 2025年10月4日

午前11時就寝。

10/04(土)

午後2時前起床、Universal Cup 1回目のKorolyovセットに出た。今シーズンからRated回とUnrated回に分けられており、今日はRated。どうやらこの場合タイトルが「Grand Prix of 地名」という形式になるようだ。Open Cupの伝統が息づいている。

https://qoj.ac/contest/2539

書く

コンテスト中に自動音声で世論調査を名乗る電話がかかってきた。まず個人情報を照合するとのことだったので言われた通り郵便番号と性別を入力したが、ふと電話番号が050から始まっていることに違和感を持ち、検索。すると詐欺電話であることが判明した。慌てて通話を切ったが、一度入力した情報は向こうに取られてしまったことになる。

そもそも世論調査で個人情報を照合するなんてあり得ないのだが、そのあたり無知だったのでうっかり応じてしまった。おそらく自民党総裁選に合わせたタイミングでの詐欺だったのだろう。

午後9時からABC426。今回からAI使用に関するルールが一部更新された。プログラミング言語の翻訳やCopilotが禁止されたことは自分には無関係で、Google検索時のAI要約の回避だけが若干面倒。

AtCoder Beginner Contest 426 - AtCoder

Aは少し面倒。Bはよい。Cは古いバージョンからどんどん消えていくので愚直に求めても合計 $O(N+Q)$ になる。Dは一切操作されずに残る文字の区間を全探索。

Eは片方がゴールに到達する前後で分けて頑張って実装。なかなか合わず大変だった。誤差で負の値の平方根を計算してしまう可能性があるようで、これがサンプルにあったのはありがたかった。

Fは一目見てSegment Tree Beatsと叫んだが、それからライブラリを窃盗して128bit整数に書き換えるまでかなり手間取っていた。 $\sum A$ がlong longに収まらないのを不審に思うべきだった。

Gは $N$ が小さかったので何をしても通ると思い込み、セグ木・平方分割・Mo's Algorithmと一通り試してしまった。冷静になるとdpテーブル二つのマージをクエリごとに行った時点で間に合わない。ここで1点取得ならテーブルサイズの線形でできることを思い出し、DSTにたどり着いた。実装自体はライブラリを使わず、関係するクエリをすべて持って分割しながら降りていった。

68分で全完して25位。Fの解説を読んで反省した。ライブラリを窃盗してくるよりこれを思いついて実装するほうが速かったのではないだろうか。

www.youtube.com

MHCの参加登録を済ませた。久しぶりのセミナー準備をしばらく行い、午前5時就寝。

10/05(日)

午前10時半起床。夕方までかけてセミナー準備を終わらせた。セミナーは明日、月曜日の予定である。

午後6時半から2時間ほど仮眠を取り、急いで食事して午後9時からARC207 div.1。Ratedであるということ以上に、昨年行けなかったオンサイト「AtCoder Japan Open」の予選であるということが重要。録画を開始してから参加登録したが、個人情報を入力する必要があってボタン一発ではなかったためかなり焦った。

AtCoder Regular Contest 207 (Div.1) - AtCoder

Aはコストに関する状態を $O(N^2)$ にするところまではすぐだったが、そこからずっと挿入dpしか思いつかず苦しい時間が続いた。操作を前から見たり後ろから見たりしながら解法ガチャを引き続けることでようやく箱根駅伝dpっぽいものが思い浮かぶも、実装でもミスを重ねて大変だった。

Bはサンプル出力をチェックして $N$ が偶数なら $u$ と $N-u+1$ の距離を3にするのが良いことに気づき、また手で $N=6$ を構成できた。しかしそれがサイクルであるということに注目してしまい、 $N=8$ へすら一般化できない。諦めて全探索したら $N=7,8$ も見つかって、グラフを描いたら一発で偶数の $N$ における構成とそれを $N+1$ に拡張する方法が分かった。

Cはインデックスと末尾の値を持ってdpすると状態数が $O(N\log\max A)$ になる、よく見るやつ。もう解けたと思って書き始めたが、遷移できる範囲の制限がインデックスと値の両方にあるため、そのままだと二次元データ構造が必要になることに気づいた。

少し考えて回避方法がわからなかったため、フルスクラッチ実装を決意。ヘトヘトになりながら $\log$ 三つのコードを書き上げたら、バグりはしなかったものの信じられないくらい遅かった。定数倍高速化を試みても、 $A$ がすべて2べきのケースでは14sec程度かかってしまう。

ここで、二次元セグ木にdpの値を乗せる際、ノードごとに持っているセグ木に1点更新をかけるのではなく、データがすべて求まったノードから順にセグ木を構築する方法でもよいことに気づいた。まだ構築していないノードに取得クエリが飛んでくることはない。

座圧があったりして結局オーダーは変わっていないものの、この改善はかなり効いて、手元で5secちょっとになった。サーバー上だともっと高速なことを期待して投げると、なんとか2.5secでAC。

残り10分でD問題に進んだが当然解けず。今年のJAG夏合宿day3-K問題と同じように、基本的には勝っている側の真似っこ戦略によって盤面の中央付近から決まりそう。しかしK問題のほうは中央を取り出したあともひと悶着あったので、それと同じならこちらを詰め切るのはさすがに不可能だと思って諦めてしまった。

138分3完で53位、パフォーマンス2843、レートも2842→2843(+1)。完全に予選落ちだと思っていたが、上位に海外の人が多かったようで、日本人順位だと17位だった。オンサイト進出！

C問題のdpは、各インデックスに対して長さが最長となるものだけ持てばよいらしい。区間の包含関係がORの大小関係になるので、それを経由して適切に組み替えることができる。

dp[i][j] の値の max を達成する j だけ残せばいい、の証明に苦しんだのでゆるふわ証明を置いておくことに
ようは列の分割であって、{最後の or,cnt} の pair であって first second ともに取りうる値の最適なものからなる pair も達成なことが言えればよく、以下のようにマージできる pic.twitter.com/XPLK9QBzTY
— PCT (@PCTprobability) 2025年10月5日

ただ、自分の方針ではこれを用いても二次元データ構造を回避できない。noimiさんのコードを読んだ結果、貰うdpではなく配るdpを行うことも重要な高速化だと気づいた。末尾の区間を一つ伸ばす遷移があれば、区間を一つ追加する遷移はORが末尾の値以上となる最左の位置へだけ配ればよい。検索をセグ木上の二分探索で行えば、状態数に対して $O(\log)$ 倍の計算量で解ける。

atcoder.jp

www.youtube.com

続いて、ARCに押し出されたのか午前1時半からCF #1056 div.2。

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

Aは問題文が長い。前計算しておいた。Bは $k=n^2-1$ のみ不可能。Cは隣接する $a$ の差から状態がある程度決まるため、高々二通りしかない。それぞれ構成して、最後に $a_1$ が正しい値となっていることをチェックする。

Dはバッテリーをグループ分けして、各グループに使えるものが高々一個しかない状態を作る。サイズが小さいグループを二つとってペアを全部聞き、マージする操作を繰り返した。この方法だとグループが $a-1$ 個になる瞬間のクエリ数がそのまま特定に必要なクエリ数となっており、上限の $n/a^2$ 以下であることが直接チェックできる。

Eは各トークンのGrundy数を求める。特に列番号にしか興味がない。 $n=1$ は手ですぐ求まる。 $n\ge 2$ なら $y$ 列目のトークンは $y-1$ 列目以前のトークンを好きなように生み出せるので、XORが張る空間のmexとなり、結局 $y\ge 2$ に対して $2^{y-2}$ だとわかる。

Fは制約が平方分割系を許していないと思ってしばらく考えたもののわからず、結局平方分割になった。色ごとに見て、頂点数が少ない場合はその色がカウントされるパスを全列挙しておく。多い場合はLCAを求めるダブリングに沿ってフラグも集計しておくと $O((n+q)\log n)$ で解けて、これは64bit並列で計算できる。後者を行うしきい値を小さくしておいたら通った。

104分で全完して12位。コンテスト後にFがHackされたが、しきい値をさらに小さくしたらまた通った。

www.youtube.com

布団に入ってハーメルンを読み、午前10時就寝。