11/24(月)

午後7時起床。今日は祝日。夜中まで先週の週記を書いて、投稿した。

あとは次の日の昼までハーメルンを読んでいた。正午、就寝。

11/25(火)

午後7時起床。

ハーメルン「ハスターなオリ主と米花町」を読了。面白かった。この作者はコナン世界にチートオリ主を放り込む作品をいくつも手掛けている。事件など意にも介さないほどの超越者をいい塩梅でストーリーに絡める手腕は素晴らしいもの。完結しないまま途切れがちなのは、そもそも原作がずっと続いている以上仕方のないことだと理解できる。

syosetu.org

午後11時就寝。

11/26(水)

午前3時起床。

ハーメルン「転生したら創世滅亡輪廻の神だった件」を読了。昨日読んだ作品と同じ作者で、桁違いに強大なオリ主が原作主人公たちに混ざってワイワイ過ごすという骨格は同じ。そもそも転スラ世界でリムルより圧倒的に強いキャラというものの存在がなかなか受け入れにくかったが、しかしそれが気になるくらいでおおむね面白く読めた。主人公最強モノの二次創作に対する向き合い方は難しい。

syosetu.org

来週月曜日のセミナー発表の準備を始めた。アブストラクトを送り、スライド作成に着手。なんとスライドを英語で書くことになったため、過去のものを使い回すのは難しいかもしれない。本当は英語で発表できないかとも聞かれたのだが、さすがに準備時間が足りなすぎて原稿を用意できないだろうから、喋るのは日本語で勘弁してもらった。

午後3時過ぎから4時間ほど昼寝。起きたらセミナーの案内が組合せ論のメーリングリストに流れていてひっくり返った。てっきり内輪向けの小さな集まりだと思っていたので覚悟ができていない。Zoom配信でオンラインでも聴衆を集めるようだ。案内から開催まであまり間がないのは、アブストラクトを出すのが遅かったからなので、申し訳ない。

Yandex Cupの前泊のホテルを決めて確保した。結局現地での移動が面倒そうだったので、運営が用意したホテルをそのまま使うことに決定。Rubikunさんと同室にして割り勘してもなお、現地のそこそこ良いホテルより高い。実際に予約する段になって表示価格に各種税金・サービス料が乗ってきたが、もうここまで来ると誤差かなという気分になる。カード番号だけ渡して決済は現地で行うらしい。不思議なシステム。

それからはずっとスライド作成を続けていた。徹夜。

11/27(木)

スライドは三章で構成するつもり。朝方とりあえず一章が完成し、それで気が抜けてハーメルンに集中力を吸い取られてしまった。

正午過ぎに登校、学食で食事し午後1時半からセミナー。このセミナーは定例のものである。今日は作ってきたスライドで発表練習を行った。

以前似た内容を15分の枠で話そうとして時間がまったく足りず、構成ごと変えて全部ボツにした苦い経験がある。それで今回のスライド作成にあたってはとにかく内容を圧縮することを意識してきた。その甲斐あって、というよりは単純に持ち時間が長いので、急いで話す必要は無さそうだ。ただ喋りが辿々しいので、発表練習はもっとすべき。

午後3時過ぎに終了。そのあとは院生室に行って爆睡した。午後6時半ごろ一度起きて学食に行ったが、そこでも眠さのあまり食欲がわかず。午後10時まで寝ていた。

残っていた人とボドゲで遊んだり会話したりしているうち日付が変わった。小腹が空いたのでカップ麺で食事。熊との遭遇を避けるためこのまま日が昇るまで院生室にいるつもりだったが、やはり自宅で寝るべきだと思い直し、帰宅。

午前3時就寝。

11/28(金)

午後1時起床。

「1/nのワトソン」というラノベの宣伝ツイートが流れてきた。もともと今年の7月に発売予定だったのがのっぴきならない理由で延期され、ようやく今月、発売に漕ぎ着けた作品。7月の時点で予約していたはずなのにまだ生協に届いていない。不思議に思ってメールを確認し、予約自体がキャンセルされていたことに気づいた。ただの延期ではこうはならない。いつまで延期になるか不明だと、発売未定という扱いになるらしい。

昨日の反動で夜中までずっと布団にいた。ハーメルンを読んだり、寝たり。午後11時半、ECR185の時間になってようやく身を起こすことに成功した。

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

Aは頭を使うことを拒否し、全探索した。面倒だった。Bは $b_i\gt 0$ なる $i$ の個数が上界で、 $\sum\max(b_i-1,0)$ が $n-1$ より小さい場合はその差だけ減ってしまう。Cは $(q+1)(r+1)-1\le k$ となるペアをたくさん作る問題で、適当に貪欲すればよい。

Dはかなり大変。まず、IとVだけで考えてよい。Iを使えば使うほど得なので、使える個数に応じて答えを前計算する。すべての?がIの状態から一つずつVに切り替えてみると、実はどれを切り替えるかは貪欲に決められる。まずIIIの真ん中、次にIIVやVIIの真ん中、最後にVIVの真ん中の順。左からチェックすることを三回繰り返した。

Eは簡単。指定された区間が複数のブロックにまたがるようにすればよく、ブロックを配置するという遷移の貰うdpが区間和を取ってくる操作で書ける。

Fは解けなかった。値に対して $k$ の最小値を持つdpは一点追加が $O(\max a)$ 、二つのテーブルをマージして一点取得するのも $O(\max a)$ 。分割統治のようにクエリを分けると $O((n\log n+q)\max a)$ になるが、当然TLEした。

5完。順位表が大変カラフル。コンテスト終了直後は170位近くだったが、しばらく経ってから確認したらBANが進んで二桁前半まで上がっていた。Fはdpの値が12以下であることに注目するとよかったらしい。値を状態に押し込むとbool値のdpになって、それは無駄だからもうちょっと凝った情報を持たせる。

www.youtube.com

朝までスライド作成。数値計算も少ししていた。セミナーでちらっと言われたことを実装したら大成功で、根本的に不可能だと思っていたケースにも対応できるようになり感動した。

正午前に就寝。

11/29(土)

午後2時前に起床。Universal Cup 7回目、Grand Prix of Zhengzhouに出た。

https://qoj.ac/contest/2661

書く

午後9時からはABC434。

Ｓｋｙ Inc, Programming Contest 2025 (AtCoder Beginner Contest 434) - AtCoder

Aは単位の変換をした後、注意深く割り算。毎回考えてしまう。Bはよい。Cは達成可能な高度の区間を管理。Dは雲に覆われていないマスと、雲 $k$ に覆われていてかつちょうど一つの雲に覆われているマスをカウント。

Eは数直線上で考えてもよくわからない。全然違う解法だろうと思うと、 $X_i\pm R_i$ の片方を選んで種類数を最大化する話になり、これはChokudai SpeedRun 002-Kで既出。

K - 種類数 β

Fは $A_1$ を求めるのが有名問題で、 $S_i+S_j\lt S_j+S_i$ という比較関数でソートするとよい。 $A_2$ はそこから一回隣接swapを行って作れる文字列であり、 $S_i+S_{i+1}=S_{i+1}+S_i$ となる箇所があればそこ、そうでなければ末尾のペアとそれより一つ前のペアの二通りを試せば十分。しかしそもそも比較関数が愚直だとソートの計算量がよくわからないことになるので、SA+LCPで頑張って $O(\log N)$ にした。

Gは解けず、平方分割の $O(Q\sqrt N)$ を提出して当然TLEしていた。全完がいなくて6完3位。

www.youtube.com

CF div.2をサボって2時間ほど仮眠を取り、午前3時からMHC R3へ。R2の結果が確定したのはつい昨日だったように思う。結局BANは全然されていなかった。

Meta Hacker Cup - 2025 - Round 3

Aは $K=2$ だけ二部マッチング。他は下界が達成できるだろうと思い、いろいろ実装してチェッカーで判定していた。最終的にうまい戦略を発見。上からジグザグに埋めていくと、下段右端の1マスが非連結になるパターンだけ問題となる。そこで次のようにswapを行う。

aaaabbb  -> aaaacbb
dddccccb    dddcccbb

全ケースをチェックして提出した。40分。

Bは連続長のmaxを状態に持ってdpするとすぐ $O(N^2)$ になった。15分。

次は順位表を見てD。後から約数包除することにして、 $i\mid u$ かつ $i\mid v$ なる点の距離の和を求めるが、これはAuxiliary Treeを構成するだけで終わり。30分。

もう一問解くとして、Eは何らかの発想が必要そうだったのでCに取り組んだ。Z-algorithmでどれだけ重ねられるか全列挙したのち、それを使ってbitsetで部分和問題を解く。文字列の周期を考えると可能な重ね方は等差数列いくつかに分解できて、それぞれ二分累乗法っぽくシフトすると愚直よりはマシな計算量になる。まあええやろと思って実行したら間に合った。70分。

残り時間ではEは何も思いつかず、祈るようにコンテスト終了を待った。結果は……Cが落ちた！ABDの3完で39位、Final進出ならず。

Cは重ねたときに直前の文字列より左にはみ出すパターンを許してしまっていた。パターン文字列と判定対象の文字列を連結してZ-algorithmに投げると、そういう正しくない位置の値も取得できてしまうので、注意が必要だった。

昼までスライド作成。また数値計算も進めた。これまではノートブックを複数立ち上げて並列処理を行っていたが、multiprocessingというモジュールを使うとよいようだ。いろいろ用意されているものの、軽めの操作を大量に繰り返すならPoolとmapで十分であり、そのときは標準出力でのログが取りにくいことも問題にならない。

午後2時半就寝。

11/30(日)

午後8時半起床。寝る前に実行を開始した並列処理は無事完了していた。

午後9時からARC211 div.2。

AtCoder Regular Contest 211 (Div. 2) - AtCoder

Aは「 $i\ne 5$ と $10-i$ しかない」「 $5$ が $\lceil\sum A_i/2\rceil$ 個より多い」のどちらかに該当する場合、それを回避する。たったこれだけの問題で2WAしてしまい、我ながらあきれ返った。

Bはどうせ $\max\le 1$ でできるだろう。 $\max=0$ が $X=Y$ のときのみであることを確認したのち、手でいろいろ試していたら、公式解説にあるadmin/tester解と完全に同じものを思いつけた。 $X=Y$ のときの場合分けが消えて感動。

Cは答えの上界を達成するために $\max R$ を使うか、次に $\max R$ を使える状態にしたい。初手から $\max R$ を使える場合は後者の操作は損だと思っていたが、サンプル3が合わなくて間違いに気づけた。

Dは有向木を二つ取る問題。とりあえず橋で切ってから考えてみるも、二辺連結性を活かす方法がわからない。サイクルを取り出してチマチマ決めるのではなくもっとスマートに構成する方法があるはずだと考え、dfs木を見出した。考察の流れで二辺連結成分ごとにdfs木を作ってしまったが、実際はグラフ全体で一気に作ってよいらしい。

Eは $P$ から木の候補を一意に決めることができ、あとは実際に $P$ が返されるかチェックするだけとなる。これは部分木の頂点の次数を並べた列の大小関係が頂点番号と整合しているか見ればよく、列自体はdequeのマージテクで管理できて、比較も同様の理由で愚直に行ってOK。

111分3ペナで全完、6位。立ち上がりは酷かったが、それで肩の力が抜けたところはあるかもしれない。その分深く考えずに提出していたので、BからDまでノーペナだったのは運がよかった。

www.youtube.com

またしてもスライド作成。午前9時くらいに何とか内容が出来上がった。結局過去の内容を使いまわせたところはほとんどなく、一から書くことになった。作成中にも英語の文章を圧縮してもらうためGeminiに聞きまくっていたが、改めてTeXファイルを丸ごと渡して添削してもらい、完成とした。

スライドの微調整を兼ねて一回だけ発表練習をしておいた。じっくり喋ってみたところ、ちょうど持ち時間である一時間くらいになったので、長くも短くもなかったようだ。この調子なら明日はあまり時間を気にせず発表できるだろう。

正午、就寝。