08/26(月)

午後3時起床。昨日のARC183は学生5位だったらしく、賞品のアマギフ2万円分がもう届いていた。順位に対する賞品は久しぶりな気がしたが、調べると7月初めに貰っていたので2ヶ月も開いていない。また土曜日のオンサイトの賞金に関するメールも来ていたので、手続きを済ませておいた。

半からインターン先定例会。先週は1on1をした以外にもちょこちょこ稼働していたので、進捗報告で話すことがある。ついでに学生最強コンの話もした。勉強会はゲーム理論の話。自分の戦略に対する相手の行動を焼きなますことでゲームを解析していたのが面白かった。サイズ的には頑張って計算すれば厳密解が求まるのかもしれないが、焼きなましでもそれらしい結果が出ていた。

解散後は先週の週記を書いて、日付が変わる前に投稿。相変わらずコンテストはスカスカだが、1泊2日の東京旅行については何とか書き切った。そのうち常体を敬体に直して参加記にしておきたい。

ハーメルンを読んで午前3時過ぎに寝落ち。

08/27(火)

この日は一日中布団の上でハーメルンを読んでいた。ツイートすら1件も存在しない。ブラウザの履歴からは、正午から午後4時、午後6時半から午前3時過ぎに起きていたことが伺える。

「Game of Vampire」の「アンネリーゼ・バートリと幻想の郷」章を読み終えた。ヴォルデモート卿との因縁が決着する章である。個人的な評価を言うと、ここまでは迷いなく100点満点中の100点以上を付けられるが、ここから先についてはそうでもない。それは原作から大きく離れたストーリーが始まるからではない。なんというか、主人公陣営のキャラクターたちがどんどんポンコツになっていくのだ。

まず受け入れがたいのはアリス・マーガトロイドが主人公に向ける感情の変化。初恋の人とだけ言っていたはずが、いつの間にか倒錯した愛情を抱いていた。過去話の「アリス・マーガトロイドとグラン・ギニョール座の怪人」章でもその様子が見られるから、時間経過による深化ではなく設定の変更が行われている。もう一つは守矢神社陣営の存在で、主人公が手綱を握るのに失敗し振り回されてしまう。

syosetu.org

08/28(水)

午後1時起床。2時間半ほどハーメルンを読んでから、久しぶりに布団を脱出してシャワーを浴びた。

先週点検に出した原付を受け取りに行き、帰りに大学生協に寄ってラノベ購入・食事を済ませてきた。曇り空で天気が怪しかったため焦っていたが、幸い雨は降らなかった。

帰宅後はまたハーメルンに没頭。1時間ちょっと読んで、3時間ほど寝て、その後は午前5時半まで読んでいた。「サクヤ・ヴェイユと七つの杖」章まで読了。

昨日挙げたマイナス評価のポイントはまだほとんど表れていないが、現在進行中のストーリーはそれ以外の理由で好きになれない。敵役とは大した因縁もないのに、人外側の存在だからやたらと強大で、はた迷惑。ここ以降はほとんど読み返したことがないからどんな決着だったかすっかり忘れてしまった。スッキリ終わることを願う。

シーンとしては、主人公がゲラート・グリンデルバルドにちょっかいをかけたり振り回したりするところがどれも好み。結局この作品のプロローグから連綿と紡がれてきた関係性に惚れ込んでいるということなのだろう。ダンブルドアが死に、レミリアとパチュリーが幻想郷へ引っ越した今、残っているのはこの二人だけになってしまった。

08/29(木)

午後2時前に起きて5時間弱ハーメルンを読んでいた。シャワーを浴びて閉店ギリギリの学食に滑り込み、食事。帰宅してまた午後11時くらいまで読んだ。

「アンネリーゼ・バートリと人形の戯曲」章を読了。ついに主人公とハリー達がホグワーツを卒業した。感慨深い。その少し前に敵との決着もついたが、こちらは自分好みの結末ではなかった。とても「スッキリ」とは表現できないものだったし、何より自分が全く共感できず許せなかった敵のことを、主人公たちがどこか認めている風だったのが嫌。

布団を出て数値計算に取り組んだ。先週挑戦した際は何もかもがうまくいかなかったが、今日試した手法は結構手ごたえがある。先週は全体を一気に求めようとしていたのに対し、今日は徐々に徐々に計算範囲を広げていってみた。これだと進捗が見えやすく、少なくとも一部の計算に成功していることが明らかになって嬉しい。また失敗するときもすぐ落ちるため、試行錯誤がやりやすい。

しばらく回していたら、以前の麻雀で卓を囲んだ修士課程の方からDMが届いた。何やらBibTeXがうまく動いてくれないらしい。常々プログラミングが得意だと吹聴している自分を頼ってくれるのは非常にありがたいことだが、TeX関連だと自信は全くない。ただせっかくだから、Zoomの画面共有を通して少しばかり取り組んでみることにした。

相談された問題に関しては一瞬で解決した。エクスプローラーに表示された.bibファイルのアイコンが真っ白でない、つまり既知のファイルタイプだと認識されていることに疑問を抱き、試しに拡張子を表示してもらったところ、.logファイルになっていたのだ。

これを修正して一件落着……とはいかなかった。しばらくBibTeXの挙動を確かめる作業に付き合っていたところ、\bibliographystyleが効いていないことが判明。これは純粋なTeXの問題だった。学科で配られた修論テンプレートにも入っているamsrefsパッケージは、使用するとこのコマンドを無視するようになるらしい。

この事実にたどり着くまででかなりの時間を消費し、残念ながら完全な解決方法まではわからなかった。彼の手元の環境だと、このパッケージを抜くとエラーが出てしまう。Overleafだとうまく動いたので、そちらに移行してはどうかと勧めておいた。

午前5時に解散。なんとグダグダと3時間も通話していた。その間回しっぱなしだった計算は、見事動き続けている。どうやら「当たり」のパラメータを引き当てたようだ。ただこのままだと計算が終わる前にメモリを使い切ってしまう恐れがあり、また実行時間もかなりかかりそうだったので、高速化を試みることにした。

思いつく箇所に手を加え、また途中経過もファイルに保存するようにしてから再度実行してみると、明らかに速い。満足して、経過のログ出力をチラチラ見ながら昼前まで日記を書いていた。PCを動かしたまま午前10時過ぎに就寝。

08/30(金)

午後4時起床。PCを確認すると全体の計算に成功していた。7時間かかったようだが、ともかくも先月からチャレンジしていたことだったので、何とか結果が出てくれて非常に嬉しい。

布団に戻ってYouTubeを見つつゴロゴロし、購買が閉まる午後5時直前に原付で向かおうとしたが、いかにも雨が降りそうな曇り空だったため、諦めて傘を持ち徒歩で向かった。当然購買には間に合わず、学食で食事して帰宅。

数値計算の結果をまとめていたら午後9時20分になった。yukicoder 443に参加。

yukicoder contest 443 - yukicoder

A、Bはよい。Cはレベル49までで十分。Dは上の桁から決めていくいつものやつ。Eは重さ $-10000$ まで管理するナップサックdp。Fはsuffixが4、40、それ以外の3状態で桁dp。Gは先頭の文字が展開されない点でCとは大きく異なる。最初にyが $N$ 文字並ぶため、そこに入っているケースを別で処理した後、その分を適切に飛ばしてレベル25以下の問題に帰着する。GはbitDP。

33分半で全完して1位。2位とはタイムで見れば結構な差があるが、序盤少し手間取ったせいでスコアはほとんど変わらない。また、GのFAだったらしい。

次の月曜日（09/02）になって、Eが落ちていることに気づいた。計算途中で重さが $W$ を上回るケースに対応できていなかった。荷物を重さの昇順に処理することで対応できる。

せっかくコンテストがかなり早く終わったのに、空いた時間でずっとTwitterを見てしまった。午後11時半からCF #969 div.1。

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

Aは根と葉の値が異なるときに重み1となる。根の値が決まっているときは簡単。そうでないとき、根の値を書き込んでから葉の値を書き込むべきだが、その前に真ん中の頂点を使ってパスしたほうが良いケースも存在する。サンプルが優しくて助かった。

Bはパス上の辺重みがすべて決定済みならばその和、そうでないなら「パス外の決定済み辺重みの和」を $w$ から引いたものがdistになる。後者もやはりパス上の決定済み辺重みの和から求まるから、これとパス上で重みが決定済みの辺の数を、各パス $i\rightarrow i+1$ について管理できればよい。頂点番号がdfs順であることからすべての辺は $n$ 本のパスに計2回ずつ出現するため、特別な工夫なく可能。

Cはいろいろ手で試して $\gcd(b_i-\min(b))$ が0または2べきであることが必要十分条件だと分かった。0のケースを別で計算するため数列をランレングス圧縮した後、尺取り。区間gcdの計算にはセグ木を使った。

Dは $\sqrt k$ 以下の要素とそれより大きな要素を、積が $k$ 以下となるようペアにして、それを大きな要素の降順に並べると大体うまくいく。 $\sqrt k$ 以下の要素はそのまま、そうでない要素は $\lfloor k/b\rfloor$ ごとに管理することで値の種類数が $O(\sqrt k)$ となり、一種類ずつ見ながら貪欲にペアを作ることが可能。区間幅が偶数ならこれでよい。

奇数の場合は一つだけ要素が余る。それが $\sqrt k$ より大きい場合が面倒。もしそうなるなら、その要素は $\sqrt k$ より大きい要素のうちの最小値であり、かつどの $\sqrt k$ 以下の要素と積をとっても $k$ 以下になる。コンテスト中は貪欲を微調整して処理したが、最初に判定してOKなら要素を一つ抜いておくのが簡単か。

そして最後に、クエリで与えられた区間に対して値の種類ごとに個数をカウントする必要がある。ここにも困難があった。 $O(\sqrt k)$ 本の累積和を持ったらMLEしてしまったのだ。平方分割の手法で改善した。メモリが足りればよいので、ブロックサイズはかなり小さめにしておいた。

Eにおいて求めるべきは、まずすべての頂点の次数が3以下であることを確認したうえで、「次数2以下の頂点とそこから最も遠い頂点との距離」の最小値である。まず、問題にあるクエリの下で直径の両端点を管理できるのが有名な話。そこからさらに木の中心もわかるから、その中心に最も近い次数2以下の頂点を発見できればよい。木を重心分解して、部分木に属する次数2以下の頂点を列挙すると、更新と取得が可能になる。

列挙の際は距離の最小値が求まるようにしておきたいから、setあるいは削除可能な優先度付きキューを用いる。定数倍を考えて後者を選択した。更新対象の部分木が $\log$ 個、さらにデータ構造の操作に $\log$ がつくが、一方頂点同士の距離は必要になるところが重心分解と一緒に計算できるため、計算量に影響しない。これで $O(n(\log n)^2)$ 。

重心分解のライブラリがないのでフルスクラッチしたらちょっとバグらせてしまったが、何とか修正まで間に合い、コンテスト終了3分前の提出がpretestを通過。TL 4secのところ3921msだった。システスではなぜか3624msとちょっと速くなってAC。Dまでもすべて通って5完33位、レートは2947→2967(+20)。Dまでかなり詰まっていたのを、何とかEを通して挽回した形になる。

www.youtube.com

このコンテストにおいて、touristが僅差で優勝を果たし、レート4009を達成した。LGMとは真逆の配色もカッコいいし、レート4000↑の称号「Tourist」もカッコいい。

Congratulations: Tourist has reached a rating of 4000! - Codeforces

計算結果をまとめる作業に戻り、午前8時くらいに完了して先生方にメールを送信。1時間ほどハーメルンを読んで寝た。

08/31(土)

午後1時半起床。涼宮ハルヒシリーズの新刊「涼宮ハルヒの劇場」が11月の末に発売されることを知った。昨年に書名が出てから1年ちょっとと、予想していたよりかなり速い動きでびっくり。ほとんど完成してから情報を出したのではないか。

🌟✨｡⋆*┈┈
　#涼宮ハルヒシリーズ最新刊

　　『涼宮ハルヒの劇場』

　　　2024年11月29日
　　全世界同時発売決定決定‼
　　　　　　　　　　┈┈:*･✨🌟

みくる＆長門のカバーイラストも公開‼
発売までどうぞお楽しみに‼
🔻『涼宮ハルヒの劇場』ティザーサイト🔻https://t.co/IvTJXvox4B pic.twitter.com/9O980VP2A6
— 涼宮ハルヒの公式 (@haruhi_official) 2024年8月31日

涼宮ハルヒシリーズの続刊が制作中らしい。
週記（2023/09/18-2023/09/24） - kotatsugameの日記

昨日送信したメールに返信が来ていた。返事を考えていたら午後2時になったので、Universal Cupへ。今日は8回目のCangqianセット。

https://qoj.ac/contest/1780

書く

メール返信を済ませ、午後9時からABC369に参加した。

AtCoder Beginner Contest 369 - AtCoder

Aは $-100\le x\le 200$ で全探索。サンプルを試すうちに答えが1,2,3のどれかだと気づき、場合分け解法に思い至ったが、そのまま提出した。Bは何かの最適化問題だと思ったらそんなことはなかった。やるだけ。Cは長さ1を特別扱いした後、階差数列をランレングス圧縮して計算。DはdpのD。

Eは拡張ダイクストラだと思って半分くらい書いてから辺の数がやたら多いことに気づいた。冷静になるとワーシャルフロイドしてから辺を辿る順序・向きを $O(K!\times 2^K)$ かけて全探索できる。Fは行を下りながら実家dpしたら復元でバグらせて1WA。どのコインからどのコインに移動するかを考えるべきだった。Gはたまに見かける解法で、できるだけ長いパスを作りながら木を分解しておけば貪欲でよい。

34分1ペナで全完して14位。EFの失速が痛い。Gはかなり速く反応できたと思う。コードゴルフはAとCをNibblesで、DをRubyで。Aで $A=B$ のとき1、そうでないとき3を作りたくなって、 $1+\dots+\#\{A,B\}$ を思いついたのは我ながら冴えていた。Nibblesで書くと+,,`$_になる。

www.youtube.com

振り返りのときにB問題で押す手が決まっていない場合の疲労度最小化問題を考えたが、実はARC073Fで出題されていたらしい。解法はよくある実家dpなので後から通しておいた。典型ですねと豪語する様子が動画に残っているから、もし間違っていたら赤っ恥だった。

atcoder.jp

少し日記を書いた後は朝までハーメルンを読んでいた。「マリサ・キリサメと大魔女の月時計」章を読了。いよいよ守矢神社陣営が猛威を振るい始めたのは気に入らないが、この章のストーリーは好き。弟子に対する試練という仕立てであり、主人公視点ではその弟子に対する愛情も描かれるから、トラブルに巻き込まれても納得感がある。またタイムトラベルに関する設定が興味深い。

そういえば、咲夜も魔理沙もホグワーツに通う間にずいぶん原作と近いキャラクターになっていった。特に趣味嗜好や持ち物の面でそう思う。例えば魔理沙の箒好きはクディッチを通じて醸成された。そのように原作の設定を大事にしている作品だから、守矢神社の面々が「あんな感じ」なのもその一環なのかもしれない。

午前9時過ぎに寝落ち。

09/01(日)

午後4時起床。2時間ほどハーメルンを読んでから布団を脱出し、シャワーを浴びた。今日はAtCoderのコンテストがないのでゲーセンに向かう。

立ち食いそばで夕食を済ませ、午後7時から3時間・17クレプレイした。今日は結構指が動く日だったが、1落ちとか1アタばかりで大した成果がない。理論値一つ、14+のSSS+一つ。

ラーメンを食べて午後11時前に帰宅し、またシャワーを浴びて半からCF #970 div.3に出た。

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

Aは場合分け。 $a$ が奇数か、 $b$ が奇数かつ $a=0$ なら無理。Bは文字列の条件を利用しようとして少し考え込んでしまったが、実は不要。単に $\sqrt{n}\times\sqrt{n}$ に並べてチェックすればよい。Cは階差を考えれば $l+1+2+\dots+(n-1)\le r$ なる最大の $n$ が答え。

Dは順列からグラフを作ってループごとに見る。Eはインデックスの偶奇と文字種ごとに累積和を取っておいて、最終的な文字列を全探索。Fは自明。Gは数列を $\left\{i\times\gcd(a)\right\}_{i=0}^{n-1}$ とすべきで、あとは算数。ただし $n=1$ のときは $0$ が作れないため別で扱う。

Hは $a_i\bmod x$ たちの中央値を求める問題になって、 $n/x$ 個の区間に入る値をカウントすれば二分探索できるため、累積和によって $x$ に対する答えが $O\left(\frac{n\log x}{x}\right)$ で求まる。 $x=1\dots n$ で和を取ると、 $\log x\le\log n$ を用いても、 $\int\frac{\log x}{x}\mathrm{d}x=\frac{(\log x)^2}2$ を用いても、 $O(n(\log n)^2)$ になることがわかる。