01/19(月)

午後0時半起床。シャワーを浴びて大学生協に行き、食事と散髪を済ませた。

午後3時半からインターン先定例会に出席。勉強会は気象データ観測から気象予報までの流れについてだった。降水確率については、以前、過去のデータから同様の気象条件のものを探し、雨が降った回数を数えて出すと聞いたことがあって、大変な力業だが確実な方法だと感心した記憶がある。実際にそれだけなのかは知らない。

日付が変わるまで先週の週記を書いて投稿した。書ききれなかった部分について少し更新し、午前6時就寝。

01/20(火)

午後2時起床。

ラノベ「悪役令嬢はしゃべりません」5巻を読んだ。面白かった。いよいよ作中世界のもととなった乙女ゲームのストーリーが開始。原作主人公の振る舞いを過度に気にする様子は神経質すぎるようにも見えたが、用心深さはこれまで通りか。また、そうして受動的に動いてばかりではなく、これまでさんざん足を引っ張ってきた魔導省を婚約者が掌握するなど、着実に良い方向に向かいつつあるのは嬉しい。

読書に夢中になっていたら購買が閉店しかけていた。慌てて駆け込みラノベを購入。食事して帰宅した。最近、日が沈むと気温が氷点下となって非常に寒い。

布団に転がってスマホを触っているうち寝てしまった。午後8時だった。

01/21(水)

日付が変わったくらいから起きてラノベを読んでいた。

朝のうちに昨日買ってきた「モンスターの肉を食っていたら王位に就いた件」6巻を読了。前半の帝国攻めは面白かった。カサンドラの過去と、主人公マルスに一定の情を抱いている現在との対比が良い。マルスが振り回されているときは周囲の人はもっと被害を被っているので、相対的に主人公の格好がつく。後半ではマルスの妃候補選考会になんと自身が参加。表紙イラストはそのときの女装姿だったようだ。

午前8時半から6時間ほど寝ていた。

R-18ハーメルン「飢えた忌み子に命を分け与えたら、暴君女帝に育ってしまった。責任をとってお仕置きするしかない。」を読んだ。ストーリー説明と淫靡な描写の割合がちょうどよく、雰囲気のある作品だった。匿名投稿設定になっているが、作者名で調べたら同じ作者の作品を他にも読んだことがあったと判明した。そちらも良かった記憶がある。

syosetu.org

R-18ハーメルン「社会不適合者な幼馴染は体で家賃を払ってくれる」を読んだ。
週記（2025/03/10-2025/03/16） - kotatsugameの日記

夜中までかけてラノベ「崩壊世界の魔法杖職人」の1巻と2巻を読んだ。非常に面白かった。

魔法の杖というファンタジーな物品を扱っているが、動作機序などの設定がしっかり作りこまれていてシステマチックに扱われる。これを主人公たちが試行錯誤で解き明かしていくという大変ワクワクする流れは、作者である黒留ハガネさんが得意とするものと認識している。例えば昔なろうで読んだ「ノーライフ・ライフ」が思い出された。

今回は設定がよりシンプルで分かりやすくなっていた。特にその粒度について、例えば論理回路からコンピュータを作ると言われても現実感がないが、CPUを初めとしたパーツから組み立てるならついていきやすい。「ノーライフ・ライフ」は前者のようなことをしていて、途中で理解が追い付かなくなった記憶がある。

この作品はなろうでの連載開始当初から非常に高い評価を得ており、自分もハーメルンの捜索掲示板で紹介されているのを何度も目にしていた。いつか読もうと思って後回しにしており、期待だけが膨れ上がっていた状態だったが、その期待通りの面白さだった。なろうのほうではもう完結しているようだ。続刊を待たずそちらで続きを読んでしまうのも手か。

午前4時半就寝。

01/22(木)

午後0時半起床。小刻みに寝つつラノベを読んだりYouTubeを見たりしていた。

「エルフの渡辺」を読了。ヒロインのセリフ「（エルフの姿を偽る）魔法をかけ続けられる」なんて、まるで自分の意志ではないような言い方だなと思っていたら、後からそれがクリティカルに効いてきてびっくり。甘酸っぱいラブコメだけの話ではないようだ。最も、その要素にはあまり興味を惹かれない。

Minecraftのゆっくり実況を見た。メインとなっている工業化MOD「Create」は、物量には弱そうだが非常にロマンあふれるシステムで面白かった。「植林する」とか「露天掘りする」とか独立した機能を持つ装置は用意されておらず、ブロックを破壊したり右クリックを代行したりするパーツをいくつも組み合わせ、「からくり」としてひとまとめに動かすことでそれらの機能を再現している。巨大な構造物がヌルヌル動く様子を見て「UgoCraft」を思い出した。

www.youtube.com

02/14のUniversal CupはUTPC 2025と被っている。いつ走るか相談を持ち掛けると、Nyaanさんが翌日のKeioPC 2025に参加するとのことだったので、勢いでそちらにもチーム揃って出ることにした。もともとUTPCのオンサイトには行くつもりがあったので、KeioPCもオンサイト。connpassの定員ギリギリで参加登録に成功した。ホテルを探したら日吉駅周辺だけ何もなくてびっくりした。

ついでに研究集会二つにも参加登録した。「第22回組合せ論若手研究集会」と「第22回数学総合若手研究集会」。前者はKeioPCと日付も場所も近く、02/19-20に慶應義塾大学の矢上キャンパスで行われる。改めてホテルを探すと、和室の素泊まりで一泊6000円強というものを見つけた。少し怖いがものは試し、そこに泊まることに決めた。

ラノベ「君の先生でもヒロインになれますか？」3巻を読了。面白かった。同級生ヒロインとの偽装カップルを成立させるまでの展開は、主人公のメインヒロインへの一途さが蔑ろにされているようで気に食わなかったが、成立した後はヒロイン二人の駆け引きに注目が行った。長続きすることもなく3巻の内に別れ、本命と無事ゴールイン。一年経って新刊が出ていないし、どうやらシリーズ完結巻だったようだ。

昼過ぎに大学生協に行ってラノベを買い、食事した。まだ日が出ている時間ということもあったが、今日は防寒着を変えたので暖かかった。振り返ってみると、最近使っていた防寒着は少し薄いので秋用かもしれない。かさばらなくて便利だとばかり思っていた。

午後5時半就寝。

01/23(金)

午後11時起床。半からCF #1075 div.2に出た。

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

Aは $[1,\min(h,l)]$ と $(\min(h,l),\max(h,l)]$ をカウント。Bはまずそれぞれ $b-1$ 回使い、以降 $b$ 回ずつまとめて使ったとき最も遠くまで飛べるものを連打する。

C1は $p_i=i\oplus 1$ とする。 $n$ が奇数ならC2もこれで通る。 $n$ が偶数の場合はそこから微調整。 $n$ の最下位bitをおろした数を $x$ として $p_1=n$ と $p_x=x+1$ をswapするとうまくいく。 $n$ が2べきなら不可能。

D1はまず先頭と末尾が0。また挿入dpを考えると、先頭以外の0に対して $i-1$ 、1に対して $2$ の総積が $f(w)$ になる。D2は二文字目が?なら0に、奇数番目の文字が?ならどちらを選んでも偶数なので1にした後、残りの?を1にできるか考える。後ろから順に1にしていって、これ以上1が増えると $c$ の倍数になるというタイミングを探す。以降は奇数の因数をいくら増やしてもよいので、すべて0にしても詰まない。

Eは1が存在すればその左右を二手ずつかけて消すことができる。一手以下の判定は簡単。二手の判定は、 $\pm 1$ にして累積和を取り一手目の条件を立式すると $O(n)$ でチェックできる形になっている。三手については先頭または末尾の二文字に1があったり、1が隣接していると可能。それ以外は不可能と信じたら通った。初手で作れる文字列が01010...0100のような形をしていて、二手で処理できないことから示せるらしい。

Fはまず操作で選ぶ $v$ が常に等しいことをエスパー。このとき頂点 $u\ne v$ について $u$ 以下の部分木にあるナッツが一つずつ消えていき、頂点 $u$ にあるナッツは最後に消えるので、操作回数に対して頂点にナッツが残っているかを判定できる。 $v$ として木の重心のようなものを選べば、ナッツがなくなるまでの操作回数を同時に最小化できる。

ただし実は $a_u=0$ のケースだけ特殊で、ナッツを一切持たない子孫を取り除いて子が一つしか残らなかった場合、その頂点には常にナッツが存在しない。こういう頂点は適当に無視すればよい。正確には $v$ を決める前に無視しており、ナッツを一切持たない葉を取り除いていって次数が2になるかで判定している。

104分で全完して5位。

www.youtube.com

ラノベ「転生したら奴隷使役と回復のスキルを持っていたので遊び半分で奴隷だけの秘密結社を作ってみた」2巻を読了。文章や台詞回しが合わないのは1巻以来。1巻の終盤にあった秘密結社の活動シーンは面白かったはずだが、2巻ではあまりそうとは感じなかった。皇帝にいいように使われているような印象を受ける。新しく始まった学園生活でもテンプレ以上のことはなかった。

TLにおすすめツイートが流れてきたラノベ「自分をSSS級だと思い込んでいるC級魔術学生」のシリーズ既刊三冊を注文した。新刊チェックで買うかどうか悩み、主人公が強いわけではなさそうという理由でスルーしたが、どうやらそうではないらしい。

over-lap.co.jp

午前10時就寝。

01/24(土)

午後4時起床。数値計算をしていた。

午後9時からABC442に参加。

JPRS Programming Contest 2026#1 (AtCoder Beginner Contest 442) - AtCoder

A、B、Cはよい。Dは累積和の更新が簡単。Eは偏角ソートした後も面倒で苦しい。すべて整数で処理する比較関数をライブラリから引っ張ってきたが、後から試したらlong doubleとatan2でも通った。doubleは精度が足りない。Fはdp。

Gは $V/W$ を見て貪欲に取った解を少し改善した。三種類の重みごとに「採用したアイテムで価値が低いもの」「採用しなかったアイテムで価値が高いもの」を抜き出し、適当な範囲でdpする。どのくらいの範囲を見ればよいかわからなかったので、計算量が許す限り大きくしておいた。

52分2ペナ全完で21位。Gではちゃんと採用したアイテムを抜く遷移を考える必要があることに注意。あらかじめ価値の低いアイテムをいくつか取り分けておけばどんな調整でもできるだろうと思い込んで2ペナ出した。

www.youtube.com

数値計算の続きをし、セミナー資料にまとめて正午就寝。

01/25(日)

午後5時半起床。シャワーを浴びて食事し、少し作業して、午後9時からARC213 div.1に出た。AGCでもAIが禁止された今、もうARC div.1は開催されないのかと思っていた。

AtCoder Regular Contest 213 (Div. 1) - AtCoder

Aは $P_i$ から $P_j$ にするために必要な操作回数が転倒数と同様にして求まる。特に $\binom{L}{2}$ 以上離れている場所には無条件で遷移できるため、dpが十分高速。 $2\times\binom{L}{2}$ 以上離れた場所に直接遷移することがないことを使えばもっと高速になる。dpの初期化をサボるとダメなことを見落として1WA。

Bは二部グラフの最大独立集合を求める問題なので、最大マッチングを考えればよい。といっても ${(u,u\oplus 1)}_u$ というマッチングが十分強いので、ほとんどの場合は $|S|=\lceil(R-L+1)/2\rceil$ となる。特にこのとき、二部グラフの部集合を片方出力するだけでよい。問題となるのは $L$ が奇数かつ $R$ が偶数で、マッチングの増加道が存在するとき。

増加道を辿るとどこかのタイミングで $L\oplus R$ の最上位bit $2^k$ をflipすることになるが、これが可能な必要条件として $(L\bmod 2^k)\lt(R\bmod 2^k)$ がある。十分性は信じることにして、増加道が存在しないケースのみ真面目に最大マッチングから最大独立集合を求めて出力した。この必要条件にたどり着くまで2ペナ、さらに最大独立集合を求めるのにミスしてもう1ペナ。

CとDを両方読んで、Cのほうが考えやすいと感じたためそちらに進んだ。かなり大変な解法を思いついて半信半疑のまま実装していたが、これはなんと公式解説とほぼ一致。ただし色の塗り替え戦略がよくなくて、サンプルを合わせたあとTLEが取れなかった。

各頂点についてlight childの下をすべて触ってよいことは知っていたが、heavy childの下の色をどうしていいかわからず、結局そのままにしておくことに。このとき、本来親の色で塗られているはずの頂点の色は常に高々 $\log_2 N$ 種類しかないため、上位 $4$ 件ではなく上位 $n:=3+\log_2 N$ 件を管理すればよい。

66分2完4ペナ、61位でパフォーマンス2701。レートは2905→2886(-19)となった。

CFのあとにCを通した。コンテスト中に書いていたコードは上位 $n$ 件の管理がバグっていた。ちゃんと書くと $O(n)$ でマージすることができて、色の塗り替えが $O(N\log N)$ 回、一回塗り替えるごとに $O(\log N)$ 回のマージが発生するため、計算量は $O(N(\log N)^3)$ 。3800msくらいで通った。

塗り替え戦略については、dfsを再帰関数と思って入ってくるときと出るときで色の分布を完全に揃えようとしたのが悪かった。入ってくるときはすべて親の色、出ていくときはすべてheavy childの色ということにしておくとうまくいく。DSU on Treeの履修をサボり、すべてマージテクで殴っていたのが裏目に出た。Universal Cupの感想戦でも指摘されていたのに！

時間は戻って、ARC終了からほとんど間を置かず午後11時半からCF #1076 div.3。

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

Aはよい。Bは $p_i=n-i+1$ でない最初の位置を合わせるための操作が一意。Cは $a_i\leftarrow\max(a_i,\dots,a_n,b_i,\dots,b_n)$ が同時に達成可能。Dは $x=a_i$ を全探索。Eは $a$ の重複を除いてdpすると $O(n\log n)$ 。Fは $x$ 座標ごと、 $y$ 座標の最大値に行ってから最小値に行くか、その逆のみ。

Gはいつの間にか $x=y$ を仮定して解いていた。 $n$ が偶数なら、木dpの要領で端点がdisjointな長さ2または3のパスを $n/2$ 本取れる。これをすべて聞くと候補が高々二つになるので、最後のクエリで特定。 $n$ が奇数の場合は葉を一つ取り除いて同様のことを行う。

Hはまず値が偶数の頂点を無視する。周囲にある値が奇数の頂点のうち、最後に削除するものの直前に削除することにすればよい。奇数の頂点のみが残るが、これは葉から決めていくことができる。親の直後に削除することにして、以降葉を無視するために親の値のパリティをflipする。葉の値が偶数になっていたら即座に削除してよい。

Gを手元でテストせず投げていたら、ジャッジ詰まりでしばらく待たされた上何度かREが返ってきてしまい時間を溶かした。80分で全完して14位。

www.youtube.com

作業の続きをして午前11時就寝。