02/09(月)

午後3時半前に起床。昨日のTROC-Hに書いておいたコードを投げたら通った。

半からインターン先定例会に出席。木曜日に1on1を設定した。勉強会はクラス分類で、階層構造のあるラベルを学習する話だった。内容とは全く関係ないがPowerPoint製スライドの数式が少し崩れていたので、入力後にスペースキーを押すと体裁が整えられるという小技を伝授した。

しばらく週記を書き、午後8時からAWC0001 Betaの生配信を行った。今回は枠を立てるという行為に挑戦。生配信は久しぶりすぎて、昔使っていたはずのコメントを画面に表示したり自動で読み上げたりするアプリが動かなくなっていた。

https://atcoder.jp/contests/awc0001

www.youtube.com

AWC0001おつかれさまでしたー！コンテスト中もどんどん呟いていいよ！
作問のやり方：お察しの通りです。ちゃんとどっかで発表します。
配点の付け方：NoviSteps基準で10Qを100点、1Qを400点として、等間隔に設定してます
今後の予定：とりあえず現状のストックで0025までは開催出来る予定
— chokudai(高橋直大)@AtCoder (@chokudai) 2026年2月9日

思ったより長引いて午後11時くらいに終了。そこから急いで週記を仕上げて投稿した。穴あきが多い。

午前1時過ぎ就寝。

02/10(火)

午前6時起床。

ラノベ「不死を求める者、これを道士と呼ぶ」2巻を読んだ。面白かった。自ら学び鍛え、後輩の指導をしつつ主人公自身もどんどん強くなっていく、チートなどがほぼ介在しない真っ当な成長譚はこんなにワクワクできるものだったのか。一門の実力者たちからその才能を認められつつある今、周囲の妬み嫉みももはやあまり気にならなかった。

しかしどうも3巻が出るのか怪しい。2巻を買ってからしばらく積んでいたので、今はもう3巻が出ていてもおかしくないくらいの時期なのに、まだ何の情報もないようだ。カクヨムにあるWeb版ではかなり先まで話が進んでいて、今も連載が続けられていたが、「カクヨムネクスト」というサブスクリプションサービスに加入しないと読めないタイプだった。

昼に学食に行き、ラノベを買って帰宅。五時間昼寝して、今日も午後8時からAWC0002 Betaの生配信をした。

今日は普段のコンテスト振り返りでも使っているホワイトボードアプリを使用。さらにコメント欄のURLがYouTubeから直接手に入ることを知り、それをブラウザとしてOBSでキャプチャすることでコメントを配信画面に流すことに成功した。

https://atcoder.jp/contests/awc0002

www.youtube.com

またしても三時間ほど配信していた。

岩井星人さんがAtCoder Conferenceでの発表を再現して投稿されていた。どのネタもとても面白かった。「スタックロール」が一番好みで、「二部ジラフ」と「感想戦」も大好き。一方サムネのネタはdpではなく分割統治に見えてピンと来なかった。

先日のAtCoder Conference 2025の発表スライドをアップロードしました。
みなさまのコメントをお待ちしております。
拡散よろしくお願いします。

競プロerにしか伝わらないフリップネタ／AtCoder Conference 2025 発表ネタ https://t.co/bvQjrnavF9 via @YouTube pic.twitter.com/JN7EgDAnkN
— 岩井星人 (@yiwiy9) 2026年2月10日

ラノベ「テスターですけど、このネトゲ学園が難しすぎるとか言うのやめれる？」を読了。かなり面白かった。ネトゲ学園という設定がまず好み。圧倒的アドバンテージを隠しきれていない主人公に対し嫉妬する同級生などいそうなものなのに、そういった人の悪意は全く描かれなかったためストレスフリーに読めた。主人公の無双に対して全く悪い反応が返ってこないのも違和感だが、目を瞑ってもよい。主人公の実力をクラスメイトが勘付きつつある、という程度の距離感はちょうど良かった。

続いて「貧乏家族の長男はやがて『魔王』に成り上がる」を読了。冒険者として稼いで家族を養うことと、魔法を自在に創造できる才能を持つことがタイトルに盛り込まれている。ここの関連がよくわからなかった。両親に関するトラウマが氷系統の魔法に関係しているようだが、それと魔法創造とは別の話に見えた。主人公の強さの理由を説明しないならしないで良いのに、重要でないところに設定がくっついているようで違和感。

しばらく日記を書き、2月の新刊チェックをして午後2時半に寝た。

02/11(水)

午後7時半起床。午後8時からAWC0003 Betaの生配信をした。

https://atcoder.jp/contests/awc0003

www.youtube.com

昨日一昨日より少し早めに切り上げ、準備して午後11時半からCF #1079 div.1に出た。

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

書く

www.youtube.com

CF-E2をupsolveして午前8時就寝。

02/12(木)

午前11時前起床。1on1に臨んだ。

なんの話をすることになるか想像がつかず若干怯えていたら、数年前に携わっていたプロジェクトの説明を求められ、薄れ去った記憶を頑張って復元することになった。当時の資料がわかりやすい場所に残っていてよかった。一時間で終了。

一昨日の新刊チェックでピックアップした本はまだ注文していない。改めて確認し、新シリーズについては本当に買うかどうかも再度考えて、21冊注文した。最近はむやみに新シリーズに手を出すのを控えており、これは購入する数にも顕著に表れている。すでに持っているシリーズの新刊を無条件に買うのは相変わらず。

学食に行き、ついでに散髪してきた。会計の際にバレンタインチョコレートを配られてびっくり。そういうキャンペーンを行っていることはどこにも告知されていなかったはず。

帰宅してシャワーを浴び、二時間昼寝。午後8時からAWC0004 Betaの生配信をした。明日は用事があるのでこれで一区切り。生配信欲も満たされたので来週また行うかどうかは未定である。

https://atcoder.jp/contests/awc0004

www.youtube.com

今日は二時間で終了。そこからラノベを三冊読んだ。

まず「クラスで2番目に可愛い女の子と友だちになった」7.5巻、8巻。7.5巻は特典SSまとめと書き下ろし中編三本。中編は主人公がほぼ不在で、サブヒロインにフォーカスした話だった。8巻は前半が一年前と同様のクリスマスパーティー、後半が修学旅行。次巻では高校三年生になっていそうで、時間がどんどん進んでいくのにびっくりする。

ヒロインと付き合い始めてから周囲にも主人公の良さが伝わるようになったのか、女性から意識されるような展開が多い。しかしそれを含む関係性の変化やヒロインの嫉妬心のほうが圧倒的に多く描写されていて、軽さではなくむしろ重さを感じた。主人公も一途で非常に真剣。

続いて「俺はSSSレア転生特典をひた隠す」。変身能力でかなり完璧に正体を隠しつつ、人目を憚らずに大活躍する様子が好みで面白かった。ただ家族にまで隠しているのは不誠実に感じられる。虐げられていたりすればその点は気にならないのだが、この作品だとスキルがないと思われている主人公のことをそれでも見放さず、期待と愛情を込めて接している様子が伺えて心苦しくなった。

正午就寝。

02/13(金)

午後7時前起床。Universal Cup 16回目、Grand Prix of Warsawに参加した。明日から二日連続で有志コンに参加するため、参加ウィンドウを早めるようお願いしていたが、準備がギリギリだったようで今朝方まで走れるかどうかわからなかった。

https://qoj.ac/contest/3347

書く

しばらく日記を書いて午前5時半には布団に入った。明日は東京に行くため朝早い。しかし横になってから何故かなろうを読み始めてしまい、寝たのはさらに一時間先だった。

02/14(土)

午前9時前起床。素早く荷造りして出発し、駅前で立ち食いそばを食べて新幹線に乗った。車内ではあまり眠れなかった。

正午くらいに東京駅に到着し、そこから今日のUTPC会場まで徒歩で向かった。丸の内という一等地に高層ビルが立ち並ぶ中、赤レンガ造りの背の低い建物「三菱一号館美術館」が堂々と構えており、眺めていて楽しかった。

街並みがあまりにキラキラしていてコンビニなど一切見当たらなかったが、会場の地下に降りてようやく発見できた。後から調べると通ってきたところの建物内にもいくつか存在はしていたらしい。また、日比谷公園とは逆の方向から来れば通りに面する店舗が見つかった可能性もある。

ゼリー飲料を飲んで会場に入り、一昨年来たときと同じく窓際の席を確保した。外部モニターが二枚用意されていたが、認識するのに画面が映ってくれず、結局使わなかった。

午後1時からUTPC 2025。会場Wi-FiのIPアドレスをAtCoderに伝えていなかったのか、コンテスト中頻繁に429 Too Many Requestsエラーが発生していた。

UTPC 2025 - AtCoder

まず下から問題を読んでいったが、すぐ解けそうなものが見当たらない。真ん中のほうまで読み進め、Hは最近ペンシルパズル「へやわけ」を頑張っているので少しだけ取り組んでみた。

何も情報がない大部屋を埋めるために「ペナルティ理論」というものが存在する。しかし履修を後回しにしていたので、ググってとりあえず最密充填の構成方法を発見した。密な行と疎な行があるのでこのまま使うのは難しい。とりあえず黒マスの数を計算してみたら、少し余裕があることが判明した。このあたりで逃亡。

sp1-puzzle.hatenadiary.jp

Aが得意そうという話を聞いたので考えてみた。 $A$ が $B$ より前にあると仮定して二回解く。交差しない場合は間を貪欲に埋めてよいので、交差する場合を考える。Z-algorithmを使えば可能な交差が列挙でき、二通りの交差の比較を高速に行うことさえできればその中での最小が求まって、候補が定数個になる。

交差の比較をする。 $A$ よりも前に置くべき要素を $B$ で使ってしまうと、 $A$ が前に出てきて辞書順で大きくなる。よって $A$ 以前が等しいもの同士の比較をすればよく、それぞれ残りは「 $B$ のsuffix」＋「余りをソートしたもの」になっている。 $B$ のsuffix部分で大小関係が定まらなければ、後ろはソートされていたほうが良いのでsuffixの短いほうが勝つ。

出したら半分くらいWAだった。冷静になると間を貪欲に埋めるパートが間違っていて、 $A_1$ と等しい要素を $A$ の前に置くかどうかは後ろの要素に左右される。修正したら二ケース落ちになってひっくり返ったが、 $A$ がすべて等しい場合さらに $B$ も見る必要があることに気づいてようやくACできた。FAだった。ランダムテストを書かなかったのは偉い。

Nyaanさんが「Jはやれば解ける」と主張したあとずっとDのTLEと格闘していたが、これはUCに収録されるときのペナルティ的によくないので、奪って通しておくことにした。考察を聞くと「AC数から適当にソートすればよいことがわかる」とのこと。

幸福度の増加量を $\max(a-a',b-b')$ から $a-a'+b-b'$ に変えると最終的に必ずゼロになるので、 $a-a'$ と $b-b'$ が正負に分かれていると嬉しい。つまり $(a-a')-(b-b')=(a-b)-(a'-b')$ の絶対値が大きいと嬉しい、というか絶対値の和がそのまま答えの二倍になる。よって食べ物を $A-B$ でソートし、大小交互に食べるのがよいだろう。

実際に順序を構成しなくても、ソート列の差分を取ったとき答えに寄与する重みが算数で求まる。サンプルを手で試すと合っていたので、PCを一瞬借りて通した。

次はGに取り組んだ。 $X+X$ に含まれる括弧列だけ考えればよい。 $X$ のsuffixとprefixを連結する場合、括弧のネストをできるだけ深くするとより長い括弧列が取れる。ここから狙うべき深さがわかり、長さは $S$ の左右両方からスタックを持って見ていくと求まる。

この状態で提出したが半分しか通らない。 $X$ に完全に含まれるケースをすっかり忘れていた。いかにも典型問題に見えたものの、相談しても誰も知らず、検索しても見つからなかったので、ちゃんと一から考えた。

求める括弧列の端点は先ほどのスタックに必ず現れている。なぜなら、そうでなければ両端を伸ばしてより深く長い括弧列が作れるから。スタックの操作をしつつ毎回最も長く取れる括弧列の端点に長さを記録し、区間MAXを求めることでほとんどは解ける。問題はクエリの区間に収まらないものを記録してしまった場合だが、これは最も深い位置でしか起こらないのでその度二分探索すれば求まる。

まだ通らなかったのでランダムテストを書いたら、なんと区間MAXセグ木が区間MINセグ木になっていたことが発覚。ブロックを分け、外側のセグ木をシャドーイングしていたつもりが、ブロック内でセグ木を作るのを忘れていた。修正してAC。

残り一時間はHとMに取り組んでいた。HはNyaanさんがほぼ想定解通りのパターンを得ていたが、空きマスの微調整が最後までうまくいかなかった。Mは $\max(X,Y,Z)$ が隣り合う回数を見て貪欲すればよいという大胆予想を提案し、PCを奪って実装を開始したものの、時間内には考えていた通りに実装しきれず、またロスタイムで少し取り組んだ結果サンプル3の $(0,6,7)$ で破綻していることが判明した。

チームでFENAJDCKGの9完2位。あと一問が遠かった。

コンテスト後の解説がなく、講評のみですぐ懇親会が始まった点は非常に良い。思い入れのある問題なら解説したくなると思うが、よくぞ我慢してくれた。しかし自分はもう眠気と空腹で無気力状態だったため、いつもの勢とすらほとんど話さず壁際で棒立ちしていた。

午後8時に会場を出て食事へ。最初は後発組に混ざっていたが、人数が多すぎる。途中で分かれ、noimiさん一行からDMで教えてもらった店「やきとん多吉有楽町店」にチーム三人で向かった。少し離れたテーブルに案内されてしまい結局三人だけの席となったものの、個人的にはチームメイトとさらに交流を深めたかったのでこれでOK。

食事 pic.twitter.com/U9v7PLol6O
— こたつがめ (@kotatsugame_t) 2026年2月14日

野菜類をつまんで話していたらすぐ午後9時が近づいてきた。自分とrisujirohさんはABCに参加、Nyaanさんは一部の問題を知っているため不参加。コンテスト開始直前になってようやく届いた大量の焼き鳥の処理をNyaanさんにお願いすることになってしまった。

ぞいぞいしてきた pic.twitter.com/AXoWgTom8u
— こたつがめ (@kotatsugame_t) 2026年2月14日

午後9時からABC445。

https://atcoder.jp/contests/abc445

A、Bはよい。Cはfunctional graphのループ検出かダブリングが必要に見える。さすがにそれで300点ということはないだろうとよく読んだら $i\le A_i$ という制約を発見した。Dは面倒。Eはosa_k法で素因数分解し、素因数ごとに指数のtop2を持った。

Fはトロピカル半環上の行列累乗。べき乗テーブルを作ったあと各 $s$ に対して行列掛けるベクトルを繰り返して解いたが、後から $K$ 乗した行列の対角成分を見るだけでよいと聞いてひっくり返った。

Gは二部グラフであることをお祈りして最大独立集合を求めた。グラフを陽に構築して部集合を求め、ACLでフローを流したあと、そこから独立集合を求めるパートで停止。何もかもを忘却していたが、ドキュメントを眺めて存在に気付いたmin_cutを使ったら一発だった。

51分で全完して10位。Gの典型パートに時間を使いすぎた。すぐできないならライブラリ化しておくべきというのは、本当に正しい。Gで苦しんでいる途中トイレに立ってnoimiさんたちの様子を伺ったが、誰も参加している様子がなかった。

途中でnoimiたち8人の卓見たけど誰もABCに参加してなくてありえない😠
— こたつがめ (@kotatsugame_t) 2026年2月14日

冷めてしまった焼き鳥を食べ、追加でいくつか注文して午後11時に解散。

日付が変わる少し前に「川崎グリーンプラザホテル」にチェックインした。土日祝日はチェックアウトが12時までと知って感動。部屋に入るとシャワーを浴びる暇もなく即座に布団に倒れこんで寝た。

02/15(日)

午前10時起床。朝方に中途覚醒して二時間半ほど眠れなかったときは絶望していたが、チェックアウトまで時間に余裕があったので、それからまたじっくり眠ることができた。

シャワーを浴びて午前11時過ぎ出発。KeioPC会場最寄りの日吉駅に着き、大学とは反対側にある商店街で味噌ラーメンを食べた。朝昼兼用だしたくさん食べられると思って大盛りにもやしトッピングまで注文したらかなりギリギリだった。

慶応義塾大学は日吉駅の改札を出て右を向くとすぐそばにある。きれいに直立した並木道が見えて圧倒された。駅直結という観点では東北大学も負けていないが、大学のすぐそばに商店街がある点で便利さには大きな違いがあると感じた。

慶応義塾大学、初めて来た pic.twitter.com/GDlpcvrhGG
— こたつがめ (@kotatsugame_t) 2026年2月15日

コンテスト会場となる部屋にはあまりコンセントが用意されていなかったが、幸いrisujirohさんが延長コードを持参してくれたので助かった。午後1時からKeioPC 2025。

https://atcoder.jp/contests/KeioPC2025

HoMaMaOvOが参加しているので順位表情報はなくならない見込み。またUCに収録されないので、問題を解く順番を気にする必要もない。並列あり、十八問なので、序盤は六問ずつに分けて解いていこうという話になっていた。自分はM以降を担当した。

Qは簡単枠だが制約が大きい。オーバーフローを嫌ってRubyで解いた。するとよいこともあって、言語自体に指数探索が実装されている。これを使うと一切場合分けをしなくても答えを $X$ として $O(\min(M,X)\log X)$ で解ける。しかし若干怖かったので $M=1$ だけは場合分けした。

次にNに取り組んだ。真ん中を通る最大スコアからの差分で見ると管理するスコアが $O(N^3)$ になる。ただし遷移はまだ $O(N^2)$ 通りある。小さいケースで試してみると、どうも答えとなる値はかなり最小スコアに近いことが分かった。一分くらいプログラムを回して $N=1000$ で計算すると、およそ8万弱らしい。そこで余裕を持って10万と見積もった。

後から考え直すと最少スコアからの差分を持てばよかったのだが、そうしなかったため単に長さ10万のbitsetだけではうまく遷移できなかった。少し枝刈りを入れて長さ600万程度のbitsetを持つことにすると、最大ケースが5secで回るようになったので、全ケース計算して埋め込んだ。

埋め込みは本当に下手くそだった。 $N$ を定数として扱いたかったので、毎回オプションで値を変えながら999回プログラムをコンパイルしたが、後から確認すると定数である必要のある箇所は存在しなかった。またノートPCのコア数を超える数のプログラムを並列起動していたのもよくない。合計で一時間弱かかり、その間にFAも取られてしまった。後からやり直すと単一のプログラムで50分ほどだったので、やはりコンパイルは重かったらしい。

Nの計算を待つ間にOを解いた。 $x,y,z$ を固定して下の桁から見ると遷移先の状態が高々一通りになっていてかなりきれい。答えが0通りになるケースの存在判定で少しミスして1ペナ出したが、すぐ通った。

Nの計算が終わったあと、Rも以前から解けたと主張していたので書いた。最初は結果をキャッシュしつつ愚直に比較すれば $O(Q\sqrt Q)$ だと思っていたのだが、比較が区間数のMINではなく和なので、大量の区間と長い区間を比較されると非常に弱い。考え直すとすべてのハッシュが計算できることがわかり、通った。

次に取り組むべきはKLMのいずれか。このときはすべて1ACだったので、一番道具が必要なさそうなLを選んだ。

$\max f(x)\le T$ となるような場合の数を数えることにして、「これから先で負ける人」と「これから先で勝つことが決まっている人の並べ方」みたいなものを持つとすぐ5乗のコードが書けて、部分点は解けるようになった。単に「連勝が始まった人」を持つのではないことがポイントか。

ペナを嫌って提出せずずっと満点解法を考えていたが、まったく計算量が落ちない。残り一時間を切ったあたりで提出しさらに考え続けてもダメ。そのうち完数で抜かれてしまった。気づいたらKとMのほうが解かれているし、問題選択が下手。せめて部分点だけは拾おうと残り数分でMを考え始め、適当なエスパーを投げたら1点が得られた。

12完と部分点三つで全体3位、オンサイト2位。今日もあと一問が遠かった。

解説ののち、一時間弱の懇親会。主にrin204さんとペンシルパズルの話をした。昨日のUTPC-Hはペナルティ理論を使うと2x2に並んだ白マスの個数がわかるらしい。まず白マスのみからなるループの個数、正確にはサイクル基底のサイズがわかって、構築の条件から黒マスを中に含むようなものが存在しないためそうなる。条件の使い方に感動した。

分断禁からこの白グラフは連結、すなわちどの頂点からどの頂点へも辺を辿って結ぶことができなければなりません。

白グラフは画像のように輪っかを持つ場合があります。この場合３つです。
白グラフが輪っかを持たないために取り除く必要がある辺の個数としても同じなので、どちらの定義でもOKです。 pic.twitter.com/myLspr23Tj
— まり餡 (@agnomy) 2020年4月5日

ただ、そこから先も難しいように思う。rin204さんは、semiexpさんが開発しているパズルソルバーを使えば小さな例が機械的に構成できて、非常に規則的なものが見つかったと話していた。ソルバーの存在は知っていたが、謎の条件もカスタマイズして記述できるということは知らなかった。

zenn.dev

「へやわけ」のほかにも「美術館」の話をした。自分はDaily Akariから始めたのでマスの数字がどんどん減っていくのに慣れているが、一般的なエディタにそういう機能はないのでよく錯覚を起こす。rin204さんは逆にDaily AkariのUIに慣れないと言っていた。

また、この機会にDaily Akari No. 168やその強化版みたいな星5の問題をどうやって解くか聞いてみた。綺麗な配置をしているから特殊な理論があるかと思ったら別にそういうわけでもないらしく、絶望。この星5の問題はPuzzle Square JPに投稿された「美術館」でまだ解けていない残り三問のうち一つ。rin204さんは全埋めしていてさすがだった。

https://dailyakari.com/archive/168

puzsq.logicpuzzle.app

午後8時に解散。限界まで会場近くにいようとしてもあと一時間もないため、どこか店に行くのは諦めて一足先に帰ることにした。

経路検索で、武蔵小杉駅で四番ホームの列車に乗り換えればあとは一本で行けるということを確認した。降りたホームの向かいが四番ホームで、折よく急行列車がやってきたため、案内されていた列車より早く着けるだろうと思って乗車。

念のため次に停車する駅から東京までの経路を検索すると、なんと到着時刻が遅くなっていた。しかも一本では行けないらしい。案内通りに行動しなかったことを反省してすぐ降り、新たな経路にしたがって逆方向の電車に乗り武蔵小杉駅に戻った。

また四番ホームにやってきた。これだけ移動しても、最初に案内された列車はまだ来ていない。なぜこんなに待ち時間があるのだろうと思いつつしばらく立っていたが、電光掲示板に乗る予定の列車が表示されないのを見てようやく気付いた。そもそもここは私鉄のホームであり、正しくはJRのホームで待たなければならない。

慌てて移動を開始した。改札を通ってからなぜか別のホームを縦断させられ、そこからさらにしばらく歩いてようやく正しい四番ホームにたどり着けた。この移動があったから、乗り換え時間がやたら長く取られていたのだ。予定通りの列車には間に合わず、一本・十分遅れで午後9時に東京にたどり着いた。ギリギリで行動していたら即死だった。

東京駅の売店で「箱根西麓牛すき焼き弁当」を買い、車内で食べた。あとは爆睡して仙台に到着。

食事 pic.twitter.com/gGnXQVKVWr
— こたつがめ (@kotatsugame_t) 2026年2月15日

帰宅して午後11時45分からCF #1080 div.3に出た。10分こどふぉったので録画の準備を整えることができた。

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

書く

www.youtube.com

午前5時就寝。