10/06(月)

午後0時半起床。登校して学食で食べ、午後1時半からセミナー開始。久しぶりだったが導入から今日の本題まで2時間で綺麗に話し終えることができた。

帰る前に院生室に寄ったら、最近北海道旅行をしてきた後輩からお土産をもらった。出発前に激推ししておいたカルビーのお菓子を買ってきてくれて大変嬉しかった。

北海道土産もらった♥ pic.twitter.com/f5tdpniBds
— こたつがめ (@kotatsugame_t) 2025年10月6日

帰宅してすぐインターン先定例会に出席。進捗報告フェーズは終わっていたので勉強会だけ参加した。今日はKaggleで評価にLLMが用いられたコンペ、特に優勝者がLLMのハックをしていたものの紹介だった。

そういえば今年初めのUniversal Cup FinalsのHuaweiチャレンジは、数学の問題の答えを出力してLLMで採点されるコンテストだった。サンプルを手で解いて埋め込むより、理由づけて解けないと言ってしまったほうがスコアが高くなったことを覚えている。それで我々のチームはハック系の解法も投げておいたのだが、結局上位入賞者はみんな工夫して解いていたのだった。

その後は先週の週記を書いていた。途中どうしても眠気に耐えられなくなって、午後7時半から2時間ほど仮眠。これで時間が足りなくなり、週末部分がスカスカのまま公開することになった。

午後11時半からECR183。

Dashboard - Educational Codeforces Round 183 (Rated for Div. 2) - Codeforces

Aはよい。Bはできるだけ上から取った場合と下から取った場合を見ればわかる。Cは $\pm 1$ の区間和を見る。

Dは隣接する二項が転倒している箇所だけが重要。inversion valueにカウントされないペアは、転倒していない区間の長さに対する三角数の和になっているので、長さの合計を $n$ として作れるかを考えることになる。貪欲でよいと思っていたら落ちてしまったため、最適な詰め込み方をすべて前計算した。

Eは設定が面倒。結局 $\max(a-ac,0)+\max(d-dr,0)$ を昇順に並べた列について、値が0-indexedでの添え字を初めて超える箇所を求めればよい。出現する値は $O(n+m)$ 通りなのであらかじめ列挙しておき、値と添え字の差を遅延セグ木で持って区間ADDで処理した。値を直接セグ木のインデックスに使えば先読みは不要だったらしい。

Fは幅 $L:=\operatorname{lcm}(1,\dots,10)=2520$ だけ移動するためのターン数を開始ターン $\bmod n$ と終了ターン $\bmod n$ それぞれについてdpで求め、min-plus半環上の行列累乗で集計する。

しかしトラップの扱いで大変苦労してしまった。ターン開始時にトラップ判定があるというから最初のスタートだけ別で計算したが、実質的にはターン終了時にトラップ判定を行っている。前者の書き方でゴールマスにもトラップ判定があるのは本当に意味不明。ここの誤読にも苦しめられた。

またdpの際には $n$ で割ったあまりを求める計算が $O(tn^2L)$ 回ほど発生する。定数倍もそこそこ大きい。そのまま実装すると1999msとギリギリになってしまったので、可能な限り場合分けによる $\pm n$ を使うコードを出しなおしておいた。

Gは操作の逆順に見ると、色1以外は最終的な状態と操作した行・列の集合が一対一で対応する。色1が塗られたマスは適当に行と列を並び替えると必ず $h\times w$ の長方形領域になっていて、ここを塗るのに最短 $\min(h,w)$ 回かかるため操作回数は合計 $n+m-\max(h,w)$ とわかる。この $(h,w)$ を全探索する。

あとは残り $n-h$ 行・ $m-w$ 列を、色2から色 $k$ をすべて使って塗り分ける方法を数えればよい。とりあえず包除原理で $O(k)$ の式ができ、よく見ると $h+w$ にしか依存しないので、 $O((n+m)k)$ で前計算ができて間に合う。

残り20分ちょっとしかない中、これらの考察と実装をギリギリで終えて提出。しかしブザービートに成功したと思っていたらREで落ちてしまった。長さ $k+1\le n+m$ だけ必要だった配列を長さ2000ちょっとで確保していたのが原因。非常に悔しい思いをした。

6完65位。Fに時間を取られすぎたのが痛い。またsolved数的にGを20分で解けるとは思えず、考察を確かめるためと言ってのんびりdpを書いていたのもよくなかった。Fの1999msの提出はopen hacking phaseでHackされた。

www.youtube.com

ハーメルンで「異世界から持ち帰った相棒をオタク沼に落とそうと思う（いせぬま）」を読んだ。タイトルにあるようなオタク沼云々にはあまり惹かれないが、それ以外の要素がどれも好みだった。異世界帰りの常識外れっぷりが随所ににじみ出ている。

syosetu.org

ゴミを出して午後1時就寝。

10/07(火)

午後7時半起床。ハーメルンを読んで、日付が変わってすぐ寝落ちした。

10/08(水)

午前5時起床。

ハーメルンで「あなたの能力は時間停止です」を読了。かなり面白かった。主人公の感情の薄さと淡々とした語り口が殺伐とした環境にマッチしている。時間停止能力以外に現地で手に入れた精霊の力もあって、どんな状況に陥っても安心感があった。

syosetu.org

続いてラノベ「アラサーがVTuberになった話。」7巻を読了。前半はヒロインたちとの関わりが多く、振り回されまくる主人公を見てニヤニヤできた。後半の炎上騒動については、火種も他所から延焼してきたものだし主人公が何かする前に周囲の人たちが解決してしまったため、蚊帳の外という雰囲気。

昼まで先週の週記を更新していた。この間にARC207Cの解法も再検討。詳しい内容は先週のほうに書いたが、貰うdpを配るdpにするだけで $O(N\log N\log\max A)$ になりびっくりした。区間取得と区間更新の比較ではなく、実は1点更新で十分だったという話。

それから夕方までPuzzle Square JPで「へやわけ」を解いていた。残り三問となった「美術館」から逃げて、最近はこちらを解き進めている。星2を中心に200問以上解いたはずなのに、星3になった瞬間全然解けなくてびっくりした。

午後4時過ぎに学食で食事。牛乳が一パック130円になっていてびっくりした。二年前の値上げは+18円で、今回は+22円。いよいよ入学時のほぼ倍の値段になってしまった。

学食の夜の部に行ったら牛乳が値上がりしていてびっくり。自分が入学したころは68円だった。
週記（2023/10/09-2023/10/15） - kotatsugameの日記

ハーメルンを読んで午後8時就寝。

10/09(木)

午前0時半に目を覚ました。

Nyaanさんが作成したコンテスト「FPS 24 題」のテスター作業をした。このコンテストは少し前にAtCoderのコンテスト予定に掲載されて、TLでも話題になっていた。Nyaanさん肝いりのコンテストなので皆さんもぜひ。

FPS 24: 24 Problems on Formal Power Series - AtCoder

4時間ほど二度寝して午後6時起床。ホスフィンと待ち合わせ、台湾料理屋「福星門」に行った。酢豚定食をチョイスし、追加で「茄子の台湾風香り揚げ」をシェア。

食事 pic.twitter.com/rRb9MFzO7l
— こたつがめ (@kotatsugame_t) 2025年10月9日

食後はすぐ解散し、ゲーセンに行って閉店まで23クレ遊んだ。

「Tuatha Dé Danann」を含むLUMINOUS ep.VIマップの楽曲が通常解禁されていたので、まずEXPから触ってみたところ、一発で理論値が出た。全ラン入り。譜面動画を見たことがあったはずなので完全初見とは言えないが、覚えてはいなかったのでほぼ同じだろう。Lv.14の理論値四つ目にしてまさかこんなことが起きるとは思わなかった。

Tuatha Dé Danann赤初見理論値！？ pic.twitter.com/ACuvTVBXwG
— こたつがめ (@kotatsugame_t) 2025年10月9日

同じく通常解禁された「LibrariA」もプレイ。99小節から105小節までが最難所という認識だったが、それっぽく押したら案外通った。それよりも107小節から109小節が苦手。タップでミスが出ているようなので、おそらく左端まで擦りきれていないのだろう。しかしいくら意識しても直らず、肘エアーするのが最も失点が少なかった。117小節にある短いタップスライドは「田中」同様トリルに合わせて餡蜜したら通る。

29回プレイして最高スコアは8900点。肘エアーで出したアタック一つがなければSSS+だったことになる。このスコアが出たのはかなり最初のほうで、それ以降は99小節から先がどんどんボロボロになっていった。縦連が何打なのかとか一切考えずにいたので、初見ボーナスタイムが終了すると一気に崩れて戻らなくなる。

LibrariA SSS+寸 pic.twitter.com/0IdOGYDRHD
— こたつがめ (@kotatsugame_t) 2025年10月9日

帰りに立ち食いそば屋で食事。7月から始まった夏季限定メニュー・薬味そばが終了していた。それからドンキにも寄って帰宅。

午前2時就寝。

10/10(金)

午前8時半起床。ずっと布団でハーメルンを漁っていた。

R-18「インペルダウン性拷問部門部門長『ナルイト・ホーテンス』」を読了。設定は良いと思ったのだが相手役が合わなかった。ロリもふたなりも好みではない。また実は麦わら海賊団の描写が原作から大きくズレるのも苦手で、女性クルーがR-18二次創作の対象になることに留まらず、一般の二次創作でもいくつか食わず嫌いしているものがある。

syosetu.org

「魔法使い♯ちゃんの世界最適化計画」を読了。大変面白かった。魔法を科学する話というだけでも好みだが、この作品は今のところ明かされている設定がどれもありきたりではなく、この先どんな発見があるか大変ワクワクできる。主人公が頻繁に子供っぽすぎる振る舞いをしてしまうところはちょっと合わない。

syosetu.org

5時間ほど二度寝して、午後11時半からCF #1057 div.2に出た。

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

Aは種類数。Bはbitごとに見て、1がちょうど二つなら無理。

Cは基本的に同じ長さの辺をペアにして使う必要があるが、対称軸上に二本まで自由における。使った辺の長さの最大値が他の長さの和未満になるように構成。対称軸上に辺を二本置く場合、短いほうはできるだけ長くすべきなので、試すパターンは $O(n)$ 通りしかない。

Dは長さ2か3の区間に分割できれば十分、かつ必要でもある。これによって適当に切り開いた後のdpが $O(n)$ になる。切り開く位置は連続する三ケ所を試せばよい。

Eは $k$ として素べきしか考えなくてよい。また $n$ 以下の最大の素数を $p$ とすると、 $x\lt p$ なら $w_p(x,n)=0$ になる。したがって真面目に計算する必要があるのは $x=p,\dots,n-1$ のみ。素数砂漠が十分短いので、制約の範囲内では高々153個である。また $k=q^e$ について、 $q$ は $n!/x!$ の素因数のみ試せばよい。これで十分高速。

Fはcuteの条件から、同じ値を持つインデックスの両端を見て区間としたときに交差が発生しない、いわゆるラミナー族となっている。ここから木構造を作っておくと、クエリで指定された区間の内にも外にも含まれるような値は木のパスに対応する。

さらにパスのLCA以外では、クエリで指定された区間の内があるprefixまたはsuffixに対応する。分割位置はパスの端点以外なら子の値だけで一意に定まるため、あらかじめ根まで遡ったときの答えを集計しておくと、端点からLCAまでの答えが差分から求まる。LCAはその場で計算し、指定された区間に完全に含まれる値は二次元セグ木で求めることで解けた。

ところがバグらせてしまい修正が間に合わなかった。LCAで値をカウントする際、元の列におけるインデックスの差を見ていたのが原因。ただFを解けた人は少なく、5完でも11位だった。FのTLは10secだったのでcuteを無視して平方分割しても通ったらしい。自分の解法は後から提出すると2.8secだった。

www.youtube.com

日記を書いて朝方布団に入ったが、そこから「謙虚、堅実をモットーに生きております！」の読み返しを始めてしまった。記憶を頼りにお気に入りエピソードを探し、登録していたら飛ぶように時間が過ぎていった。やはり面白い。

なろうに「お気に入りエピソード登録機能」が実装されたらしい。お気に入りのシーンだけ読み返すというのをよくするので、非常にありがたい。作品によっては章立てがなく、各話タイトルからも内容が一切わからず、探すのに難儀することがあった。謙虚堅実のこと。
週記（2024/07/29-2024/08/04） - kotatsugameの日記

https://ncode.syosetu.com/n4029bs/

午後0時半就寝。

10/11(土)

午後1時半起床。寝た気がしない。睡眠時間が短すぎるので起き抜けは逆に眠くないが、しばらくしたら地獄を見ることになるだろう。

午後2時からUniversal Cup 2回目、Grand Prix of Paris。RatedとUnratedがあるという話なのに初っ端から二回連続Rated。

https://qoj.ac/contest/2551

書く

午後9時からABC427。

Panasonic Programming Contest 2025（AtCoder Beginner Contest 427） - AtCoder

A、Bはよい。Cは部集合をbit全探索。Dはメモ化再帰。それぞれ350点、425点と少し高めの配点になっているが、やることは非常にシンプルで実装も難しくないから、知識に付けられた点数なのだろう。

Eは残っているゴミが初期状態における矩形領域とどれだけ移動したかで書けるので、 $O(H^3W^3)$ 状態のBFS。矩形領域を縮めるパートの算数で手間取った。Fは半分全列挙。計算量の見積もりをせずに実装を開始し、完成してから $N=60$ で間に合うことを確認した。

Gには手も足も出ず、6完17位。

www.youtube.com

ハーメルンを開いたら、8月に完結した作品に更新が来ており、同時にタイトルが「【書籍化】告知事項（隣人がVtuberです）【進行中】」に変わっていた。大変めでたい。ところで、匿名設定にしている投稿者にどうやって連絡を取ったのだろうか。

syosetu.org

午前0時半就寝。

10/12(日)

午前6時半起床。シャワーを浴びて日記を書き、午後2時過ぎにもう一度寝た。

一時間後に両親が部屋にやってきて起床。しばらく部屋の掃除をしたり荷物の整理をしたりして、夕方出かけた。まずココスで食事。

食事 pic.twitter.com/7jjt7rLB7v
— こたつがめ (@kotatsugame_t) 2025年10月12日

その足で10/08にオープンしたばかりのイオンモール仙台上杉へ行った。駐車場へ向かうルートに大行列ができていてギョッとしたが、右折待ちの列だったらしく駐車場自体は十分空いていた。ルートを選べば同じ交差点を左折して向かうこともできて、そちらならスムーズに入れるようだ。

壊れてしまったスーツケースの新しいものを買ってもらった。

なんとスーツケースのキャリーバーが引き出せなくなっていることが判明し、頑張って持ち上げて運ぶ羽目になった。
週記（2025/07/14-2025/07/20） - kotatsugameの日記

三階にゲーセンが入っていたのでちょっと偵察。チュウニズムは金筐体が二台設置されていた。イオンの閉店に合わせてラスクレは午後8時半設定。店内では写真や動画の撮影が禁止されていたが、もしかしてリザルト画面すら撮ることができないのだろうか。

イオンモール仙台上杉に来たよ！

チュウニズム金筐体2台
・店内撮影禁止
・ラスクレ20時30分
・マイマイ、オンゲキ、タイタツあり pic.twitter.com/MYC10VxPWM
— こたつがめ (@kotatsugame_t) 2025年10月12日

帰宅し、両親と別れて午後9時からARC208 div.2。

AtCoder Regular Contest 208 (Div. 2) - AtCoder

Aは全然解けなくてサンプルを眺めていたらNimからの連想でXOR＝ORが降ってきた。あまりにもそれっぽい解法だったので深く考えずに提出し、AC。証明もNimと同様にできる。

Bは $(A_{i+1}\bmod A_i)=A_{i+1}-A_i$ としてできるだけ「損」しないようにするのが良い。また $K$ 以上の値が作れるなら先頭を調整することで $K$ ちょうどにもできる。 $A_N$ の値で二分探索し、 $A_i=\lfloor A_{i+1}/2\rfloor+1$ によって残りを定めて判定。

Cは $n\oplus C=n+C-2(n\;\mathrm{AND}\;C)$ より $C-X\equiv 2(n\;\mathrm{AND}\;C)\pmod{n}$ 、ただし $X\lt n$ 。bitとして $\frac{C-X}2\subset C$ ならこれで $n$ が得られた。そうでないケースについては $C-X-2(n\;\mathrm{AND}\;C)$ が $0$ でない $n$ の倍数になり、特に $n\le X+C$ が得られる。これで全探索してみると $X\oplus C$ も解の候補になった。これらで対応できないケースは探した範囲には見つからなかったため、提出。

Dは辺 $(i,j)$ を色 $A_{i,j}$ で塗るものと捉えて考察した。色 $1,\dots,N$ それぞれ自己ループとマッチングで $N$ 頂点すべて覆い、かつ使った辺が被らなければよい。 $N$ が偶数のとき、自己ループ以外の辺を色 $2,\dots,N$ の完全マッチングに分解することができるので、そのうち色 $1$ で使う辺を自己ループ二つに置き換えることで構成できる。分解は以下の記事を参考に実装した。

physics0523.hatenablog.com

$N$ が奇数のときは各色に一個ずつ自己ループが必要。自己ループを頂点 $N+1$ との辺だと思うと、 $N+1$ 頂点の完全マッチングになっているため、先ほどの構成が使える。最後に $Y$ を再現するよう頂点番号を入れ替えればよい。

完全マッチングへの分解を自力で導出しようとしてしばらく苦しんでいたため、手間取ってしまったという印象だったが、Dはそもそもあまり解かれなかった。またノーペナだったことも効いて107分4完で4位。

www.youtube.com

振り返りを手早く終えて、午後11時半からCF #1058 div.1。

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

Aはインデックスを昇順にクエリで聞く集合に追加していき、答えが0でなかったら取り除く。これで各値についてそれぞれ二回目の出現が特定できるので、逆方向も行えばすべてわかる。逆方向については聞かなくてよいクエリが $n$ 回発生するので、合計 $3n$ 回になる。しかしクエリ上限を $3\times 2n$ だと勘違いしてこの改善を入れなかったため1WA。

Bは解けない！矩形chminを $O(n^2m)$ 回行う解法に帰着されてしまい、まともに解けるわけがないので問題特有の改善を探していたが見つからなかった。仕方なく $\log$ を付けて提出。この解法すら思いつくのに苦労している。なんとかpretestは通ったものの最大ケースが入っていなかったらしく、システスでTLEした。おそらくMLEもするはず。

Cは $(i,a_i)$ と $(a_i,i)$ が対応していることが必要だと考えたが、大間違い。定数項に限りいくらでも大きくできる。勝手に $a_0\le n$ だと思っていたため全探索しても最後のサンプルの答えが2にしかならず、長い間苦しんでいた。

書く

AとCの2完で511位、レートは3019→2805(-214)。夢見心地。動画は即ゴミ箱行きとなった。

午前4時就寝。