週記（2024/12/30-2025/01/05）

12/30(月)

午後1時半起床。昼食を摂ってから先週の週記を書き始めたが、夕方用事で携帯ショップに行ってきたあとはこたつで寝ていた。午後7時に夕食。

食後はまた週記の執筆に戻ったが全然はかどらなかった。入浴を挟んだりしつつ、日付が変わる直前にUniversal CupとCF Good Byeを残して投稿。AGCは真っ先に書いたのでちゃんと埋まっている。かなり劇的なコンテストだったから、実況動画にできればよかったなと思う。

ハーメルンを読んでいるうち椅子の上で1時間ほど寝てしまったので、布団へ移動。しかしそこからまた3時間以上スマホを弄ってしまった。午前7時半就寝。

12/31(火)

午後3時半に目を覚ました記録があるが、布団でスマホを眺めているうちにまた寝てしまった。

午後8時起床、夕食は年越しそば。このとき紅白ではtuki.さんが「晩餐歌」を歌っていた。歌い始めのほうは声が少し細いように思えて、緊張だろうかと心配したのだが、曲が進むにつれて声量がしっかりしてきて安心。良いパフォーマンスだった。

近年、紅白にはGReeeeN（現GRe4N BOYS）、Adoさんと顔出ししていない歌手が出場している。tuki.さんもその一人ではあるが、彼女は実際にスタジオに来ていたし、歌い終わりのコメントのときはスクリーンを通さない後ろ姿が映ってかなりびっくりした。

食後すぐ部屋に引っ込んで、年末恒例の各種ツイートを行った。レート変動、AC数、読書記録。

CHUNITHMは高難度の譜面を詰めているときにもっと上まで到達した記憶があるのだが、レートシステムが変わってCHUNITHM-NETから確認できず、また写真にも残っていなかった。競プロのほうは上振れしたときの記録を抜かせていないという感じか。AtCoderでは赤から陥落せず、また最近CFでLGMを維持できているのは、highestには現れずとも成長した点だ、ということにしておきたい。

昨年はTopCoderが取得できずに11015問、今年はCodeChefが取得できずに12450問。その二つは大体同じだろうから1年で+1500問くらいと言えて、昨年・一昨年とほぼ同じ。精進もupsolveもろくにせずコンテストにだけ出続けているとこのくらいになるようだ。週29問弱、4コンテスト強で、まあそんなものかという感じ。

12月は、新刊をチェックした時点で分かっていたが、購入した本がそもそも少なかった。年間でみると昨年よりちょっと多く買って、ちょっと多く読んだらしい。購入した本の過半数を積んでいる状況は変わらず。

論文に関する作業をしているうち、年越し。この作業は年内に完了させるつもりだったのだが、着手するのが遅すぎて全然間に合わなかった。年が変わった後もずっと続けていた。

午前5時に切り上げて布団へ。ハーメルンで「無声慟哭」を読んだ。

syosetu.org

この作品はふるつきさんが大絶賛していたもの。10万文字ある短編だし、バンドリというほぼ知らない原作の二次創作だし、さらに「チラシの裏」区分になっていて、自分で見つけられることは絶対になかっただろう。

メンバー一人ひとりの抱える問題がそれぞれ導入され、絡み合い、それぞれ一定の解決を見て綺麗にまとまったので満足感があった。調べてみるとこの「問題」自体が二次創作で付け加えられたものだったらしい。かなりえぐい設定もあったので仰天した。自分が普段読む作品と比べると、必須タグ「アンチ・ヘイト」の重みが段違いだ。

ふるつきさんは毎年、その年に読んだネット小説をまとめている。自分も昔似たことをしたのだが残念ながら継続できなかった。リストを見ると、自分が読んだものとあまり被っていなくて面白い。共通しているのは「『星天』」「強めのモブウマ娘になったのに、相手は全世代だった。」「高1を12回ループしたクラスメート達が賢者モードになっている件」の3作。これらは確かに面白かった。

furutsuki.hatenablog.com

午前8時前に就寝。

01/01(水)

午前10時過ぎ起床。食事はお雑煮とおせち。母は毎年おせちの何品かを手作りしてくれていたのだが、今年はついに丸ごと購入したらしい。ということで写真をパシャリ。またお雑煮に入れる餅を3個にしてほしいと頼んだら丼で出てきて、正月からフードファイトじみた食事になった。

ちなみに昨日の年越しそばも今日の正月料理も、起きるのが遅くて家族とタイミングが合わず一人で食べることになった。この性分は治らないな……。

食後は初詣。今年、平野部にはちっとも雪がないが、山あいに行くとさすがにいくらか積もっている。ただ昔に比べるとかなり少ない。

例年帰りに道の駅で昼食を摂っているところ今年はスルーして、午後2時半に帰宅。部屋に戻って論文作業を続けたが、眠くてどうしようもなかったので3時間ほど仮眠をとった。午後6時半に夕食、しゃぶしゃぶ。昨年もしゃぶしゃぶだった。

今年分の読書記録と買った本の記録を投稿し、論文作業に戻った。日付が変わるくらいでひとまず完了。風呂に入ったあと、紅白の録画を見た。特に良かったのはこっちのけんとさん「はいよろこんで」と米津玄師さん「さよーならまたいつか！」。

「はいよろこんで」はモールス信号の最後の一音とサビの入りが重なっており、THE FIRST TAKEだとモールス信号のほうを発音していなかった。当然の扱いではあるが、ちょっとスッキリしない。一方紅白だとライブ仕様ということか、サビを音響に任せモールス信号のほうを最後まで発音してくれた。

「さよーならまたいつか！」はドラマパートから歌唱パートへの繋ぎが好き。作中世界に米津玄師さんが溶け込んでいるというわけではないのだが、その微妙な異物感に引き込まれた。最後、決めポーズする米津玄師さんの横に飛び出してきた主人公っぽい女性は司会の方だったらしい。

2026/01/12追記：先日、米津玄師さんの公式チャンネルに紅白の映像がアップロードされた。

www.youtube.com

午前3時半就寝。

01/02(木)

午前11時起床。今日の昼食は幼馴染二人と食べに行くことになっている。秋にも会った彼に車を出してもらった。

午後6時から幼馴染と飲み。

週記（2024/10/21-2024/10/27） - kotatsugameの日記

もう一人は成人式以来。そのときの話では一浪しており、さらに噂では大学院に進んだらしいので、ちょうど今が修論シーズンのはずなのに、試しに呼んだら来てくれてびっくりした。事情を聞くと、別にどこかでもう+1年したわけではなく、すでに学会発表をこなし書く内容も固まっているので切羽詰まってはないとのことである。

店ははま寿司。中学の同級生がその後どうなったかをひたすら聞いた。地元にいると駅で会ったり職場関係で噂が流れてきたりして、同窓生のつながりというのは緩やかに保たれ続けるようだ。自分の話もどこかでされていたら嬉しいな。今日聞いた中では、博士課程に進んだ人は他にいなかった。

食後すぐ解散では寂しいと主張してドライブに繰り出し、マンガ倉庫まで行ってデュエマ・フィギュア・ガンプラ・漫画の棚を眺め歩いた。

「聖霊王アルファディオス GS」は「G・ストライク」のぶん我々が知る「聖霊王アルファディオス」の完全上位互換になっていると話し、キーワード能力「G・ストライク」の説明をしたのだが、「相手クリーチャーを1体選んでタップし、次のターンアンタップしない」という誤ったことを伝えてしまった。これだと強すぎる。

dm.takaratomy.co.jp

午後3時半帰宅。寝っ転がってなろうを読んだ。午後6時に夕食、鍋。食後はまたなろうを読んだ。

夜になってワインが登場。ホスフィンとの家飲みなら大丈夫だったからと思い、勢いで一瓶開けたが、今日はペースが速く、また間にチェイサーもつまみもほぼ挟まなかったため、てきめんに酔っ払ってしまった。

日付が変わって家族が寝静まったあと、気分が悪くなってこっそり吐いた。お酒でこういう事態になるのは初めて。部屋に戻る元気もなくこたつに潜ろうとしたが、それすら力及ばなかったようで、気づいたら突っ伏した状態で頭だけこたつに突っ込んでいた。

01/03(金)

午前8時起床。二日酔い。塩気が欲しくなって、朝食のお雑煮を汁だけおかわりした。気分がまだ悪いので一日寝ていたいが、今日は仙台に帰る予定であった。

乗車券は往復切符を学割で買ってあったが、帰りの日を特に決めずに来たため、新幹線特急券を買う必要がある。シャワーを浴びて、近くの駅員がいる駅に出向いた。当然帰省ラッシュで満席であり、富山駅から大宮駅までは立席になった。

昼まで横たわったままなろうを読みつつ過ごし、昼食にそばを食べて親の車で富山駅へ。午後2時過ぎのかがやきに乗車した。

立席は思ったより辛かった。まず足腰が弱っている。さらにデッキにはキャリーバッグが置いてあったり、子供を抱いた人が景色を見に来たりして、なかなか角に身を落ち着けていられなかった。必死に耐え大宮にたどり着くと、そこからのはやぶさはスカスカ。3人掛け席に自分ひとりだった。しかし疲れ果てており、席も倒さずに寝入った。

午後5時過ぎに仙台到着。本屋で「新 謎解きはディナーのあとで」2巻を手に入れた。ちゃんと初版本。

そのまままっすぐ帰らず、ゲーセンで20クレ遊んだ。理論値と14+のAJが一つずつ、さらにチュウニズムクエスト完走。「ウニの歌」はラストがフリックを無視しても押せないので、それっぽく手を動かすだけで完全にお祈りだった。

ラーメンを食べて午後11時帰宅。シャワーを浴び、なろうを読んで午前4時半就寝。

01/04(土)

午前9時半から1時間ほどなろうを読んでいた記録がある。

午後2時前起床。新年一発目のコンテスト、Universal Cup 24回目・Polandセットに出た。

https://qoj.ac/contest/1890

書く

急いで食事して、午後9時からABC387。

AtCoder Beginner Contest 387 - AtCoder

A、Bはよい。Cは桁数と最上位桁を決めれば算数できるだろうと思ったら、そこから桁ごとに見ていく必要があって大変だった。Dは直前の移動も状態に入れてBFS。Eは桁和が小さいと嬉しそうなので、適当に上位桁と下位桁を探索すれば見つかるだろうと考えた。最終的には上位4桁と下位1桁を全探索した。Fはまあ、やるだけ。

Gはまず、許されるグラフの形を考える。閉路がパスを共有しているとダメで、さらに頂点を共有していてもダメらしい。つまり、2辺連結成分が1頂点あるいはサイズ素数のサイクルになっているグラフだと言うことができる。ここでサイズ2のサイクルが不可能であることに注意。

2辺連結成分がk個あり、それぞれの頂点集合がU_1,\dots,U_kであるときに、グラフが何通りあるか数える。まず連結成分内での辺の張り方は、|U_i|=1なら1、|U_i|\ge 2なら数珠順列で(|U_i|-1)!/2になる。連結成分の外については実は既出で、N^{k-2}\prod_i|U_i|となる。この式はk=1でも成立するのだが、コンテスト中は気付かず場合分けしてしまった。

与えられた森を含むラベル付き木の数え上げ公式

週記（2024/09/30-2024/10/06） - kotatsugameの日記

今度は頂点集合のサイズに対して\{1,\dots,N\}の分割を考えてみる。ありうるサイズの集合をP:=\{1\}\cup\{\text{奇素数}\}とし、サイズp\in Pの集合がc_p個あるとすれば、\sum_p c_p p=Nに対して\frac{N!}{\prod_p(p!)^{c_p}c_p!}になる。多項係数から同じサイズの集合の区別を取り除いたものである。

まとめると、a_1=1,a_p=1/2\;(p\ne 1)として\sum_{\vec c}\frac{N!}{\prod_p(p!)^{c_p}c_p!}\times N^{\sum_p c_p-2}\left(\prod_p p^{c_p}\right)\prod_p (a_p(p-1)!)^{c_p}=\frac{N!}{N^2}\sum_{\vec c}\prod_p(a_pN)^{c_p}/c_p!。多項式で書き直すと\frac{N!}{N^2}[x^N]\prod_p\sum_{i\ge 0}(a_p N)^i x^{pi}/i!=\frac{N!}{N^2}[x^N]\exp\left(\sum_p a_p N x^p\right)が得られる。

ここまでたどり着いたが残り2分しかなく、そこからFPSを窃盗してくるのはさすがに間に合わなかった。ライブラリの整備の大切さを実感。6完12位。今日はA・B・C・Eが2025の性質を題材としていて面白かった。Fの制約の2025は、無理しなくても……という感じ。

午後11時半からはCF Hello 2025に出た。

Dashboard - Hello 2025 - Codeforces

AはMEXが2以上になれる行・列が高々一つ。Bは最初問題文が壊れていてかなり詰まった。修正されると単に要素の種類数だとわかり、あっけない。Cはa,b,cですべて一致しているbitのみ答えに寄与できない。lとrが食い違う最上位bitを2^kの位としたとき、下位k+1桁で2^k-1と2^kを使うと上界が達成でき、残り一つは何でもよい。

Dでかなり詰まってしまった。MAX・MINが変わらない間区間を縮めてもよいので、a_lとa_rがMAXとMIN・MINとMAXになると思って計算でき、それぞれ(-a_r-r)-(-a_l-l)、(a_r-r)-(a_l-l)になる。rをfixしたときの最大値をセグ木に乗せようとして1時間ほど苦しみ、最終的に平方分割したが、この平方分割自体がよく見るとセグ木に乗る。前半を典型で処理したのに後半がそうできないのは意味不明。反省。

Eは二分探索を考えると、重み0または1の辺からなるグラフ上での最短距離を求める問題になる。並列二分探索しながら全点対間最短距離を管理すると、O(n^2)で一つの辺を重み1から重み0に更新できるので、まずO((q+mn^2)\log m)が手に入る。そして、もともと重み0の辺で連結になっていたら更新しなくてよいため、m=n-1とできる。これでE2まで通ったが、実は並列二分探索はいらない。

solved数を見てGに進んだが間に合わず、E2まで遅解きの317位。しかもDで一度Judgement Failedが出ており、仕様を知らずリサブしたら普通に点数を減らされて踏んだり蹴ったり。レートは3063→2919(-144)。残念。

www.youtube.com

CF-Gのupsolveをした。基本的には十字の中心に置きたいため、まずi+2j\bmod 5に応じて敷き詰め、それで置けずにカバーできなかった部分は貪欲で処理してみた。敷き詰め方は5通りあるので、連結成分ごとに最適なものを選ぶ。コードはコンテスト中にほぼ書けていて、最後vector<vector<int> >がMLEするのを1次元に潰して回避したら通った。実は連結成分ごとに見なくてもよいらしい。

ABC-Gの\expを用いた解法は準備時に見落とされていたようで、TLが12secもあるため2辺連結成分を遷移のたび一つずつ追加していくO(N^2/\log N)のdpが通る。コンテスト中は素数だけ集めたリストを作っていなかったので遅く、気づけなかった。その方針でコードゴルフをした。最初のコードはGCCで5secだったのに、そこから定数倍を悪化させすぎて、最終的にClangですら11secかかっている。

atcoder.jp

日記を書いて午前9時半就寝。

01/05(日)

午後1時直前に起床。Universal CupチームでKUPC 2024に出た。UCに収録される予定はないとのことだが、念のためPC 1台ルール。今回チーム戦順位表しかなくなっていてびっくりした。

KUPC 2024 - AtCoder

せっかくだからFAが欲しいなと思ってOに特攻したら、最大化はよく知っている典型だったのに最小化が01 on Treeという未履修の高度典型で手も足も出ず、最初の1時間チームに全く貢献できなかった。その間EADJBがそれぞれNyaanさん、risujirohさん、risujirohさん、risujirohさん、Nyaanさんによって通された。Bは昨日のCF-Gが大ヒントだったらしい。

我に返って仕事を探し、NyaanさんがWAを出していたHを引き取った。誕生日攻撃をするという方針らしい。チェッカーを書いて確かに落ちるなあと言っていたが、このときクエリはA側を固定し、B側を全部聞くというものだった。risujirohさんにA側も動かせばよいと言われてやってみると、たしかに40回くらい間違えるようになった。

しかし出したら落ちた。手元で試すと確かに数回に1回落ちる。パラメータ調整をもうちょっと頑張って、もう一度出したら通った。実はA=Bとしてしまっており、使えないクエリがいくつかあったのが痛いようだ。

01/07追記：よく考えると、A=Bのときは意味のないクエリが大量に発生している。これが痛すぎるだけで、クエリ数が少し減ったのは全く問題ではなかった。

NyaanさんがPを通す間にほかの問題を眺めて、KとMを解いた。Kは2種類の包除原理を同時に行うと、KYOTOとTOKYOを適切に含むような文字列を数え上げる問題になる。重なるところが難しいのでKYOとTOに分け、それぞれいくつ置いたか、また「連結成分」がいくつあるかを持つと3乗のdpができて、連結成分の隙間に任意の文字をねじ込めば文字列が数えられる。Mは左右からシミュレートした結果を適切にマージ。

KとMの間にNyaanさんがOを通してくれた。ここから少し停滞。自分はIを考えており、risujirohさんはずっとLと格闘、NyaanさんはNに取り組んでいたはず。まずNの構築ができて、通った。

Iも解けた。まず01の問題にして、X_{i,j}=1となる場合の数を総和に対して数えてみる。するとiに依らないことはすぐわかる。ここでいったん実装して正しいことを確認した。書いたコードを眺めると、j-1のpopcountが共通していればまとめて計算できて、N-j+1の総和さえ分かっていればよいようだ。これは桁dpで可能。あとはちょっと畳み込みを使うとO(M\log M\log N)くらいになった。

残りの時間はrisujirohさんのLとNyaanさんのGを往復していたが特に貢献はない。答えの候補を半分にするクエリを乱択で探したLが最後の最後で通り2位に躍り出たものの、その1分後に3位だったチームがCを通し、部分点1点の差で負けて最終順位は3位だった。1時間半ほど感想戦をして解散。

note.com

謎のnoteが出ていた。現在の環境におけるデータ取得はかなり大変そう。「返信先」は取得ミスだと思う。また「講義室の机」と「机」は自分の中では別物で、後者は自室の机にしか使っていない。もっと細かい話をすると、自室の机に向かっているときでも椅子の背もたれに寄りかかって寝ていたなら椅子に、机に突っ伏して寝ていたなら机に突き刺さっているという判定である。

なろうを読んで、眠気に負けて4時間寝て、またなろうを読んだら午前7時になっていた。

2時間ほど論文作業をしてから先生にメール。毎月5日までに提出すべき書類（Googleフォーム）があって、指導教員の確認が必要なのだが、1日に送ったメールにまだ返信がなく困っている。

シャワーを浴び日記を書いて正午就寝。