06/16(月)

午前11時に気合いで起床。昼から大学で用事があったため登校した。1時間もかからず終了。

院生室に移動してMidnight Code Cupのお土産を設置した。空港で買ったチョコ2種類。ナッツアレルギーの後輩がいるためアレルゲンを含まないものも探し回り、ヴィーガン向けのチョコを見つけて買ってきたのだが、ダークチョコレートであることを見落としており、そちらはかなり苦くて微妙だった。

ベオグラード土産を院生室に設置 pic.twitter.com/H56UIdl3yz
— こたつがめ (@kotatsugame_t) 2025年6月16日

少しだけボドゲで遊んで帰宅。途中で生協に寄りラノベを受け取ってきた。新刊コーナーに「サイレント・ウィッチ」9巻extraが並んでいてびっくり。それまでの巻を一切置いていないが、いったい誰が買うのだろう。生協が我々の注文とは別に入荷するラノベ新刊は、よくわからないセレクションであることが多い。自分が買った本と同じものが入っていることも頻繁にあり、もしかして参考にされているのでは、とこっそり思っていたりする。

午後3時半からインターン先定例会に出席。セルビアからロストバゲージしつつ帰ってきた報告をした。勉強会は電力メーターなどのメーターの構造について。例えば電力量は「アラゴの円盤」の原理を用いて回転する動きに変換され、それが歯車などの物理的なシステムを通してメーターの表示となるらしい。全部デジタルに処理しているものだと思い込んでいたためびっくりした。

解散後、かなり眠かったので3時間ほど仮眠をとった。起きて先週の週記を書き投稿。それから朝までラノベを読んでいた。

「天嬢天華生徒会プリフェイズ」を読了。読みは「てんじょうてんげ」で、プリフェイズ（prifaes）は作中の造語。タイトル・あらすじといった購入前に確認できる情報や、なんなら口絵を見てもどんな話か全く分からない中で、超巨大な学園を舞台にしていること、著者が「神様のメモ帳」「生徒会探偵キリカ」で有名な杉井光さんだったことのみを手がかりに購入を決めた作品。

読んでみるとしっかり面白かった。それと同時に、確かにあらすじに書けることは少ないなと思った。というのも、主人公が何者で一体何をするのか、ということが1巻全体を通して徐々に明かされていくストーリーだったから。よってここから先の感想はネタバレを含むことに注意しておく。

まず主人公は詐欺の天才。これは杉井光さんの他作品でもよく登場する設定のため、求めていた通りのものが出てきた感じで満足感を得た。ストーリーも人を騙すイベントの繰り返しで進んでいくが、しかし最も大きな詐欺はやはり叙述トリックだろう。これがあるからあらすじに何も書けなかったのだなと納得した。

ちょっとした描写の違和感は最初のころからずっとあったと思う。しかし自分で勝手に文脈を補うと無理のないシーンが想像できたため、あまり気にせず先に進んでいった。真相に気づいたのは8章に入ってからだったはず。

それでもラストの種明かし前に自力で気づけて嬉しかったが、直後に再読してみたところ、これでなぜ分からなかったのかと思うほど露骨な描写があちこちにあってびっくりした。真相を知った後では些細な単語、句読点、ダッシュの意味がガラリと変わっている。これには感服。実のところ、再読するということが少なくて知らなかっただけで、ほかの叙述トリックの作品でもこういう仕掛けが随所に施されていたのだろう。

午前11時就寝。

06/17(火)

午後8時に目を覚ましたあと、長い間布団でゴロゴロしていた。午後11時半からCF #1032 div.3。

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

Aはよい。Bは $|b|=1$ とする。Cはすべての最大値を一斉にデクリメントできるかチェック。Dは $a$ と $b$ をそれぞれソートしたあと、 $a_i\lt b_i$ を満たすようにswapすると条件を満たす。Eは桁dp。Fは $\max\le x$ から $\max\lt x$ を引けばよく、使ってはいけない数で列を区切るとZero-Sum Rangesになる。

Gは01を $\pm 1$ に置き換え、区間和の絶対値の総和を求める。これは典型問題で、累積和を取って値をセグ木のインデックスにすればよい。そこから答えを求めるのは算数。HはLISのdpで、末尾の値に対して長さの最大値を持つタイプのものを考える。不要な箇所で値を大きくするのは無駄なので、末尾の値が $l_i$ のところだけ真面目に区間MAXで計算、他は単にインクリメントでよい。最初に $l_i$ を集めて座圧しておく。

32分で全完して4位。Gでうっかりlong longをlongと書いてしまい1WAしたが、これがなくても順位は変わらなかったようだ。

www.youtube.com

それから、夜中から朝を通り越して昼になるまでずっとセミナー準備をしていた。昼前に学食に行って食事し、午後2時前に就寝。

外はバカみたいに暑かった。夜は夜でそこそこ蒸し暑いが、昼よりはよほどマシである。よって昼夜逆転こそが大正解の生活リズム。ただ、ちゃんと逆転したところで止めておかないと、今日みたいに寝る時間が暑さのピークになってしまう。

06/18(水)

午後8時起床。

セミナー準備がヤバい。そもそも話す予定だった内容の理解が追い付かない。資料を前日までに送信することになっていたが、当然間に合わず、夜中もずっと取り組んでいたのに全く先に進めず、午前8時くらいになってついに諦めた。分かっていないところを分かっていないと書いた資料を、さも前日作ったものを朝起きてから送りました、みたいな顔して送信。

このくらいの時間、外は土砂降りだった。登校するのに原付が使えないなら少し早く起きなければならないな、と憂鬱な気持ちになったが、天気予報を調べるとすぐ晴れるようだったので一安心。

布団に入ってからはなかなか眠る気になれず、ハーメルンを漁っていた。午前11時くらいにようやく就寝。

06/19(木)

午後0時半に気合いで起床。無事晴れていたので原付で登校し、学食で食事した。

今日のメニューは油そば。以前食べたときはただでさえ量の少ないタレが細い中華麺に吸収されきってしまい、味ムラができて美味しくなかった。しかし懲りずに注文してみると今日は美味しかった。盛り付け前に調理スタッフが麺とタレを絡めるのだが、そこが上手だったのではないか。

学食で「にんにく油そば」を食べた。前から気になっていてようやく出会えた期間限定メニューだが、タレが少ないため素の中華麺の味が目立ち、美味しくなかった。
週記（2024/07/01-2024/07/07） - kotatsugameの日記

午後1時半からセミナー。準備は大炎上していたがセミナー自体は和やかに終わった。理解できなかったところを話したら聴衆からいい感じのコメントが来て、雰囲気で計算してみると論文に書いてある内容とほとんど整合してくれた。符号の食い違いだけ残ったので、後でちゃんと整理しなおす。そういうことをしていたため、長引いて3時間ほどかかった。

院生室に移動して雑談。月曜日設置したお土産は順調に減っており、またうれしいことにホワイトボードにお礼のメッセージが残されていた。学食で食事して午後7時前に帰宅。

すぐ眠ればいいものを、なぜか眠気に抗いペンシルパズル「波及効果」と格闘していた。1問に2時間かけたりしていて意味不明。

しばらく日記を書いて午前10時くらいに就寝。

06/20(金)

午後6時起床。気力がなく、布団でYouTubeを眺めて過ごしていた。

ようよう起きだして午後9時20分からyukicoder 471。

yukicoder contest 471 - yukicoder

Aからちょっと悩んだ。バブルソートをする。Bは上のbitから揃えていく。Cは片方の切れ目を固定し、もう片方をデータ構造で処理する。

Dは面白かった。素因数分解できれば、 $p^a\mid A$ と $p^c\mid C$ について $\lfloor aB/c\rfloor$ というふうに簡単に計算できる。しかし制約がデカすぎて素因数分解できない。そこで小さい $B$ に対する結果から答えを求めることにする。 $B=0,1,2,\dots$ に対する答えの増分は必ず周期 $c$ を持っており、 $c$ は十分小さいので、計算可能。

$A^{2c}$ くらいの数もそこそこ桁数が大きいが、 $A^0$ から順に求めていくとすれば、 $A$ をかけ、 $C$ で目いっぱい割ったあとは $C$ との $\gcd$ を取っても次の計算に影響を与えない。これで入力と同じくらいの桁数の数だけ扱う解法が得られた。多倍長整数が必要なためRubyで実装し、出したら通ってFA。後から試したら $\gcd$ を取らなくても普通に間に合った。

Eはdp。 $a-(a\bmod b)$ と $a-1-((a-1)\bmod b)$ が異なるのは $b\mid a$ の場合だけなので、毎回その $b$ だけ列挙して寄与を更新すればよい。

FはSA+LCPを作り、区間を順にチェックしていった。細かい部分だが、prefixを指定したときにそれを含む区間がどれくらいあるかセグ木で取得できるようにするため、後ろから見て区間代入を行った。前からだと代入を戻す操作になってしまう。ちなみにこの問題の強化版がABC280Exで既出だったらしい。その回を見に行ったらG問題でドン詰まりしており、upsolveもしていなかった。

Ex - Substring Sort

Gはクエリ平方分割で通した。距離の取得やsetの操作で $\log$ がついているものの、なんとか3secくらいで通ってくれた。なかなかTLが厳しいなと思っていたら非想定だったようだ。

Hは $W_1,\dots,W_N$ が独立な確率変数でないから一斉に求めなければならないと思い込んでおり、この場合にも期待値の線形性が使えることを完全に忘却していたため、問題に取り組む土俵にすら立てていなかった。

7完3位。

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

06/21(土)

午前8時半起床。今日は夏至らしい。

午前9時からUniversal Cupに参加した。今日は40回目、Potyczkiセット。これがシーズン3の最終回らしい。チームメイトの都合により通常用意されている中では最も早いウィンドウで走ることになったが、現地チームのゴーストが入っておらず順位表情報がほとんどなくて、なかなか大変だった。

https://qoj.ac/contest/2135

書く

感想戦終了後、午後3時から1時間ちょっとAHC049に参加した。

Toyota Programming Contest 2025#3（AtCoder Heuristic Contest 049） - AtCoder

操作2を真面目に考えるのはかなりつらそうなので、なかったことにする。基本的には遠くにある荷物を拾い、戻ってくる行動を繰り返すこととした。これだけだと芸がなさすぎるので、道中で他の荷物を拾えるなら拾ってくることに。とりあえず帰り道だけ実装して、1617782点が最初の提出。ちょうど全く同じ点数の人がいて面白かった。

帰りに目いっぱい拾ってくるので行きには何も拾えないだろうな、と思いつつそちらもやってみたところ、高々1個だけ拾うとしたコードで1744898点が出た。その1個を重さ最大のものにしたところ少し点数が落ちて、1個ではなく無制限に拾うのを許すと少し改善され、1766150点が出た。ここまででおよそ1時間。

夜のABC+CF combinedに備えて布団に入り、仮眠。午後8時半くらいに起きたら肝心のcombinedがdiv.2オンリーになっていて仰天した。

午後9時からABC411。

UNIQUE VISION Programming Contest 2025 Summer (AtCoder Beginner Contest 411) - AtCoder

A、Bはよい。Cは左右を見て差分更新。Dはやけに難しいなと思いながらtrie木を書いた。Eは $A$ をdistinctだと思って全部まとめてソートし、最大値を決め打って数え上げ。0を含む数列の1点更新・全体の積取得が必要になったため、セグ木を持ち出した。

Fは各頂点から生えている辺をsetに入れてマージテク。頂点を縮約する度に辺の行き先もチマチマ書き換えて、常に代表元同士の辺としておくと、多重辺の削除が簡単に行える。しかし各駒が置かれている頂点も同様に管理しないといけないことに気づかず1ペナ。

Gはあらかじめ多重辺をまとめておき、始点・通った頂点集合・今いる点を持つbitDPをすればひとまず $O(N^3 2^N)$ になる。ところが $N$ が一つ少ないと思い込んでしまい深く考えずに実装開始。ただ重複削除と定数倍高速化のつもりで、始点が通った頂点のうち最もラベルの小さい頂点となるように遷移したところ、実は $N$ が一つ落ちる本質的改善になっていたらしく、それに無自覚なまま出したら通った。

34分・1ペナで全完し7位。

www.youtube.com

早々に全完し動画を撮り終えたため、合間にシャワーを浴びる余裕があった。午後11時半からCF #1033 div.2。1問既出だと判明して消え、div.2に降格され、さらに時間が30分短くなったようだ。

Dashboard - Codeforces Round 1033 (Div. 2) and CodeNite 2025 - Codeforces

書く

www.youtube.com

夜中からずっと木曜日のセミナーでの計算を整理していた。教科書で該当するところを探し舐めるように読んだり、ChatGPTに聞いてみたり。教科書からは正確な定義や計算手法を、ChatGPTからはお気持ちを教えてもらえる。それでも理論的なところを分かった気にはあまりなれていないが、正しい計算を行えるようにはなった気がする。

昼前にコンビニに行って菓子パン等を爆買いし、食事。午後1時就寝。

06/22(日)

午後4時半起床。午後5時から3時間、ICPC模擬国内予選の内部コンテストを走っていた。

午後9時からARC201。今日は第六回日本最強プログラマー学生選手権の予選のため、divは設定されていない。

AtCoder Regular Contest 201 - AtCoder

Aは各writerがセットをできるだけ作ったとき、Div.1とDiv.2の数の和は定数になり、またその配分として可能なものは区間になる。これらの値を足し合わせる。細かい部分の算数でやたら時間がかかってしまった。

Bは上のbitから見ようとして大失敗。容量を $N$ でchminしてよいことを使うと思ったが、計算量が $O(N^2)$ になっても間に合わない。正解は下のbitから見ることで、 $W\bmod 2$ を埋めたあと二つの品物をペアにすることでサイズの小さい問題に帰着できる。

Cは簡単。良い集合の様子を考えると自然にtrie木が出てきて、 $S_1,\dots,S_k$ から構成したtrie木上でdpすれば求まることがわかる。文字列を追加する度、通ったパスの頂点だけdpの差分更新を行えばよい。

Dは大変。 $B$ をソートし、 $A+B$ と $M$ との大小を考えると、最適解において「 $A+B\lt M$ となるprefixと $A+B\ge M$ となるsuffixへ分割できる」「prefixの $A$ よりsuffixの $A$ のほうが大きい」「prefixとsuffixそれぞれについて、 $A$ は降順に並んでいる」ことが示せる。よって考えるべきパターンはprefixの長さ $\ell$ として $N+1$ 通りになった。

ここで二分探索を行うと、 $B$ の各要素についてペアとなれる $A$ の条件が定まり、そこから可能な $\ell$ の条件を計算できる。prefixのほうは緩いのでsuffixに対して真面目に判定することになるが、いずれにせよ $A$ と $B$ がソート済みならすべての $\ell$ をチェックするのが $O(N)$ になる。よって二分探索で $O(\log M)$ つけても間に合う。

Eは簡単だが、それ以上に自分が上手かったと自画自賛したい。バウンディングボックスの面積 $(\max x-\min x)(\max y-\min y)$ について、 $\min\bullet$ を $\max{-\bullet}$ に置き換えつつ展開すると、 $\max\pm x\times\max\pm y$ を複合任意で求めて足し合わせることになる。平面走査して $\max\pm x$ を固定し、 $\max\pm y$ のほうは遅延セグ木で取得。区間に一斉に値を掛ける操作で更新できる。13分で通した。

Fを読んで双対じゃないかと言っていたらコンテスト終了。5完30位で無事決勝進出。

www.youtube.com

今日も朝まで計算。昨日の理解をもとに再度実行してみるとちゃんと論文と一致する値が出てきた。符号が反転していた原因は、自然に定まるらしい群作用の定義を間違えていたから。常識がないので、ちゃんと言ってくれないとわからなくて困ってしまう。

唐突にハーメルンの日間ランキングを開き、「超有能な幼なじみを堕落させたんだがなんかおかしい」を読んだ。4話で完結済み。道中の雰囲気はかなり好みだったものの、ラストで勘違いしたまま別れそうになったところにはヒヤッとした。結局縒りを戻してからも勘違いしたままだったし、ちょっとスッキリしない気持ち。

syosetu.org

日記を書いて午前10時くらいに布団に入ったあと、眠れず少しラノベを読んでいた。正午過ぎに就寝。