11/03(月)

正午前に起床。今日は祝日。夜中まで先週の週記を書いていた。

午後1時からはNyaanさん作の5hコンテスト「FPS 24 題」が開催されていた。

FPS 24: 24 Problems on Formal Power Series - AtCoder

ei1333さんのライブラリを全面的に窃盗し、tester時は5hでRまでの65点。その後Sの満点とT、Uの部分点だけは取れた。後半はFPS云々の前にそもそも問題が解けない。また、Tの実装では $A_1$ による除算を行ってしまっている。改題後のチェックが不十分だった。

testerとしての貢献は、Rにおいて $X=1,2^N+1$ のケースを入れるべきだと指摘したくらいだろうか。tester陣で引っかかってしまったのは自分だけだったが、提出を見ているとちらほらここで落ちている人がいるようだ。

あとはOの $f(x)=xg(f(x))$ という式を逆関数で解こうとして、TLEしたのでTLを2secから3secに引き上げてもらった。50点の壁となる問題だからFPSにおける最後の基本知識として逆関数が出てくるんだなあ、とか考えていたが、全然そんなことはなかった。

hosさんによるX問題の解法は衝撃的。またHoMaMaOvOのお二人だけが100点以上を獲得されるという結果も、出来すぎなくらいで感動していた。

・FPS が得意な人 : 80 点
・HoMaMaOvO : 100 点
↑完璧な得点の目安 pic.twitter.com/nSExfrQVxr
— ポテロング (@potato167_long) 2025年11月3日

日曜日の観光パート以降を書ききれないまま、日付が変わる前に週記を投稿。そのあとさらに少し書き進めて、午前3時前に寝た。

11/04(火)

午前9時半起床。午前中のうちに先週の週記をある程度埋めて午後からゲーセンに行こうと考えていたが、全然集中できず、夕方までかかってもUCとYandex Cupの話まで手が回らなかった。

間に10月の読書記録をツイート。先月読んだなろう「ラケッティア！　～異世界ゴッドファーザー繁盛記～」は本当に面白かったので、多少積読が増えたのは仕方のないこと。

https://ncode.syosetu.com/n9866fb/

10月の集計
買った：20冊
読んだ：6冊
積読：+14冊
積読（累積）：+124冊
— こたつがめ (@kotatsugame_t) 2025年11月4日

シャワーを浴びようとしたが、部屋が寒かったので布団へ引き寄せられてしまった。ゲーセンに行くという話も、もういい。そのまま午後7時就寝。

11/05(水)

午前1時に目を覚まして4時間ほどハーメルンを読んでいたらしい。そのあとまた二度寝して午前11時起床。シャワーを浴び、今日こそ外出した。

昨日外食するつもりが結局家から出られず、空腹で目が回りそうになっていたので、まずは大戸屋で腹ごしらえ。味噌汁を秋季限定の「いろいろ茸となめこ汁」に変更した。豆腐が大きく切られていて嬉しい。通常メニューの「たっぷり野菜の麦みそ汁」もそうだが、健康志向に見えても味は濃く、塩分がしっかり含まれていることに注意しておきたい。

食事 pic.twitter.com/RGKyHOn1Ob
— こたつがめ (@kotatsugame_t) 2025年11月5日

午後2時から7時間半ほどゲーセンで過ごし、45クレプレイ。成果は13+のULTの理論値三つ。高速鍵盤のある「Invitation」が一番大変そうだったが、これはスッと出て、逆にそれ以外の二つでドブりまくってしまった。捨てゲーを含めるとそれぞれ50回くらいプレイした気がする。低難度で捨てゲーばかりしていたから、一日で45クレも使えたという面もある。

「ハルシナイト」はフリックを擦りきるのが難しくてまずAJが出ない。また、この時代になって始点が黄タップではない言の葉カルマ配置があるのが許せない。意識しすぎて毎回Lateを出していた。

「First Twinkle」は繰り返しプレイするうちにできないところがどんどん変わっていくタイプの譜面で、ずっと噛み合い待ちしていた。成功テイクではラストの運指が頭からすっぽ抜け、フリックスライドを両手でわしゃわしゃして取った。抜けなくて本当に助かった。

今日は45クレ pic.twitter.com/X4VcEJBDC5
— こたつがめ (@kotatsugame_t) 2025年11月5日

油そばを食べ、ドンキに寄って帰宅。

Yandex Cup 2025のPVがTwitterに上がっているのを見つけた。毎年開催地にちなんだテーマがあって、2023年は「芸術」、2024年は「文明」、そして今年2025年は「職人」のようだ。こういう趣向は素直にかっこいいと思う。問題文に無理やりねじ込まれたストーリーも、時間に追われていなければ面白く読める。

В декабре Стамбул встретит 180 программистов из разных стран — лучших из лучших. Там пройдёт финал и награждение Yandex Cup 2025 — международного чемпионата по программированию от Яндекса. https://t.co/JVAwnkfXdF pic.twitter.com/mKn4sZqXiV
— Яндекс (@yandex) 2025年10月21日

朝方までずっとPuzzle Square JPで「へやわけ」を解いていた。ひと月近く、ちまちま星2と星3を解き進めてきたが、相変わらず星3には解けないものがある。記憶すべきパターンが多すぎて手に負えない。「ペナルティ理論」という手法を勉強する必要もあるようだ。

午前5時半就寝。

11/06(木)

午前11時起床。寝たり起きたりしながら夜中までラノベを読んでいた。

「推しにささげるダンジョングルメ」4巻を読了。Web版でも大好きだったエピソード、アメリカのスタンピードが収録された。超かっこ良くて超面白かった。決めるべきシーンであれほど粋なセリフを連打されるともう最高。ところで、主人公が他より二つ三つ抜きん出た人類最強だと明言されているのは少し珍しい気がする。他の作品だと表舞台に出ていない同程度の実力者がいることが多い。

次に「純情ギャルはカノジョじゃないのに」を読了。完全に官能小説なので美少女文庫に行くべき。そういう観点では、おりょうさんのイラストがもともと好みだったこともあり結構良かった。最近のスニーカー文庫だと「女友達は頼めば意外とヤらせてくれる」もほぼ官能小説だが、本番シーンの描写の有無で本作のほうが一段と過激だったように思う。

午後11時半からCGR30に出た。

Dashboard - Codeforces Global Round 30 (Div. 1 + Div. 2) - Codeforces

書く

www.youtube.com

朝になって「先生……キスは授業の範囲外です」を読了した。ダーツバーに通ったりする大人びた趣味の主人公がいいなと思っていたが、ラストで急にヒロインの姉に対しヒロインを娶る宣言をしたのにはちょっとついていけない。流れ的にその場の勢いという感じがして、誠実さに欠ける。また幼馴染からの好意に対しては、もはやきっぱり振るしか道は残されていないように見えて残念。

午前10時就寝。

11/07(金)

午後2時半起床。夕方までなろうを読んでから大学生協に行った。

ラノベを購入したあと、学食。カレーの提供方法が変わったらしい。夜の部では特にトッピングが並んでいるような様子はなかったが、昼の部の話だろうか。唐揚げとカレーの抱き合わせ商法が廃止され、カレー単品を頼めるようになったならば良いことだと思う。

なにこれ！ pic.twitter.com/HfClUlcKUV
— こたつがめ (@kotatsugame_t) 2025年11月7日

午後9時からyukicoder 487に出た。構築だけ六問集めた三時間セット。

yukicoder contest 487 - yukicoder

非常に難しかった。難易度もそうだが、まず実装量が途轍もない。自分が解いたABEについてはBで5813bytes、Eで7558bytesのコードを提出している。ライブラリを一切使わず、フルスクラッチしてこの量となった。

Aは未証明。ソートした $C$ をRow-majorで並べた $B$ だと思い、さらに $A$ の一行目・一列目をすべて $0$ としていったん復元してみると、どうやら奇数行奇数列の成分のみが負となるようだった。そこで行ごとに適当な $a$ を選び、 $+a,-a,+a,\dots$ を一斉に足して補正を試みたところ、ランダムケースでうまくいってくれて、提出すると通った。FAだった。一応想定されていた別解で、正当らしい。

Bは気合いを入れてやればできる。敷き詰めのベースケースは想定解とほぼ同じで、再帰については主に下数行だけ追加する遷移を使った。ペンシルパズルとしてはT型のみで5x5のパターンを発見するのにちょっと苦労した。最初の提出がWAで卒倒しかけたが、小さいケースの出力を眺めると $K$ の値が間違っていた。これだけ修正したら通ってくれて助かった。

Eの考察は典型的。解法も想定解とおおむね一致したが、最初に各四つ組の置換のパリティを揃える際同じ行・列を二回操作して操作回数を稼げることに気づいておらず、適当な実験で見出したつもりの謎の操作列を使っていた。パリティさえ合っていればなんでもよいのでうまく動いてくれた。

四つ組を揃える操作については、最初に2x2のケースを全探索で求めて、そのテーブルを毎回引いた。操作2から始まるケースも別で作っておけば対応可能。 $\{i,N-i+1\}\times\{j,N-j+1\}$ の値を取り出して、 $1,2,3,4$ にマッピングしてテーブルを引くまでの操作を関数にしておいて、値の集合が正しいかの判定にもそれを用いた。

3完で優勝。Dは埋め込む必要のあるパターンがほとんど唯一で、それが見えさえすれば実装もそこまで大変でないから狙い目だったのかもしれない。

少し日記を書いてからラノベ「ダンジョンに閉じ込められて25年。救出されたときには立派な不審者になっていた」3巻を読んだ。主人公が身体の頑丈さに任せた戦い方をするので、なかなか血の気の多いバトルシーンが続く。分かりやすい無双ではないが、こういう強さもあるのか。また、ダンジョンの隠された真実が立て続けに明らかになっていくので、ストーリーの進みが速く感じた。

午前5時半就寝。

11/08(土)

午前11時起床。しばらく日記を書き、午後1時からUCのチームでSTPC2025に参加した。

東京科学大学プログラミングコンテスト2025 (Div. 1) - AtCoder

書く

午後9時からはABC431。

TOYOTA SYSTEMS Programming Contest 2025（AtCoder Beginner Contest 431) - AtCoder

A、B、Cはよい。Dはナップザック問題。

EはできることがBFSくらいしかなく、考えてみると同じマスの状態を二回切り替えるのは無駄だから考えなくてよい。これはUターンをしないこと、Uターン以外なら高々一回の切り替えで任意の方向に行けることから従う。よって過去の履歴を無視して探索できる。方向転換は頑張って埋め込み。ただのBFSを書いたらMLEが出て、01BFSが必要なことに気づいた。

Fは大きい値から順に挿入dpを考えるのがよい。 $A$ がdistinctの場合がすぐ解けて、少し考えると同じ要素も一気に挿入すれば数えられることが分かった。

Gは $l$ の値を昇順に決め打つと対応する $B$ が左端と右端から順に決まっていく。残っている要素のうち $A_l$ より小さい・大きい要素をカウントしたり、インデックスでタイブレークを入れつつ昇順・降順での $k$ 番目を取得したりする必要があって実装はそこそこ大変。後者には残っている個数を乗せたセグ木上の二分探索を使うのがよい。

44分全完、1ペナで4位だった。

www.youtube.com

STPC-Mのupsolveをして午前3時就寝。

書く

11/09(日)

正午起床。

午後1時からUniversal Cupに参加した。今週はXi'anセットで、ついにやってきたUnrated回・Extra Stage 1。定められた期間内ではいつから5hを開始してもOKという形式になっていて、我々のチームはSTPCとの兼ね合いもあり、今日、締め切られるギリギリでスタートした。どうやらもう数時間遅くスタートすることもできたらしい。Unratedだし、それほど厳密にはしていないのだろう。

https://qoj.ac/contest/2562

書く

シャワーを浴びて午後9時からARC209 div.1。

AtCoder Regular Contest 209 (Div. 1) - AtCoder

Aは後手勝ちの条件を考える。自明な条件を除くと、先手が正しいかっこ列の先頭か末尾を削除したときに後手が対応する括弧を狙って消せるか考える問題となる。両端の括弧が対応している間はどうとでもできて、そうでなくなったタイミングで両端に十分な量の()があればようやく後手勝ちとなる。括弧の対応関係を求めておけば楽だったろうが、自分は $\pm 1$ の累積和の区間MINを取得して無駄に $\log$ をつけた。

Bは一種類の文字が過半数を占める場合が問題。その文字が連続している区間の長さをできるだけ均等にするのが良さそうだが、xxyxxyxxのような回文ができてしまうと困るなあと頭を抱えていた。しかし実験すると、そもそも区間長が偶数のものはできる限り作らないほうが良いらしい。

その通りに実装し、愚直と合わせたあと提出。vectorのinclude忘れでCEを三回出しつつもなんとかノーペナで通ってくれた。後から、長さ偶数の区間二つを長さ奇数の区間二つに損せず組み替えられることを確認した。

Cはまず操作が貪欲で良いことに気づいた。このとき書き換え先の値は区間として表現することができ、例えば $L\le b\le R$ なら $P=+1$ のとき $b=R$ として $\lceil S/R\rceil\le a\le X$ 、 $P=-1$ のとき $b=L$ として $1\le a\lt\lceil S/L\rceil$ に遷移する。区間が空の場合はスコアの損を受け入れて $1\le a\le X$ となる。

クエリは平方分割で答えることにすると、各ブロックに対して $b=1,\dots,X$ で突入したとき最終的に $(L,R)$ とスコアの差分がいくらになるか計算できればよい。ここでほとんどの区間の端点が $\lceil S/b\rceil$ を使って表せることを考えれば、1ターンシミュレートするだけで状態数が $O(\sqrt S)$ になるので、そのまま $O(N\sqrt S)$ で前計算できる。

Dは $A_m=1$ となる最小の $m$ が重要。これが決まっていれば、残りの $A$ は先頭から貪欲に定めることができる。そもそも $A_i=-1$ なる $i$ が一個以下しかない場合は $m$ が存在しないことがあるようだが、そのケースは答えが $N$ 通りになって、一つ一つ比較することができる。

そうでないときは必ず $m$ が定まる。また、 $m$ が変わったときに $B$ で値が変化する箇所は限られているので、 $O(N)$ 通りを比較することができる。そう言うのは簡単だし結論もそれほど複雑なものにはならなかったが、かなり気を使って場合分けした。丁寧に実装し終えたあと愚直と比較したら一発で合ってびっくり。投げたらそのまま通った。

今日はかなり調子が良く、Cを通したタイミングでは2位だった。最終的に4完、4位。ノーペナなのはかなり偉いと思っているが、実際のところ順位にはあまり関係なかった。

パフォーマンスはギリギリカンストして3400、レートは2886→2949(+63)。半年分の負けをここ2回で帳消しにした。レートそのもののhighestでこそないが、ランキング54位はこれまでで最高らしい。

www.youtube.com

なろうを読んで午前6時半就寝。