週記（2025/07/21-2025/07/27）

先週日曜日から金曜日まで国際会議「FPSAC」参加のため札幌にいた。

FPSAC 2025 · Hokkaido University

07/21(月)

午前8時過ぎ起床。今晩からは隣のホテル・東横イン札幌駅北口に宿泊するため、チェックアウトした後すぐそちらに向かってスーツケースを預けておいた。

そういえば昨日、札幌のホテルは少ないことで有名だと聞いた。学会参加者で埋まっていても不思議ではないらしい。以前Mrs. GREEN APPLEが札幌でライブしたときは、電車で1時間以上かかる旭川のホテルまで満室になったそうだ。

隣のホテルの素泊まりを、ほかの日の倍する値段で取った。

週記（2025/05/26-2025/06/01） - kotatsugameの日記

コンビニでパンを買って朝食とし、午前8時50分くらいに会場到着。最初の講演は午前9時からのはずが、もう満席だし前では人が喋っていてびっくりした。実際は「Opening remarks」として、海外の方向けに日本・札幌で過ごす際の注意点を話していたようだ。会場後ろに追加の椅子が用意されていたので、それを並べて座った。スライドが遠くてちょっと見えづらい。

最初の招待講演者のスライドに東北大学のロゴがあってびっくりした。メインは上智大学だが東北大学にも所属しておられるとのことらしい。

発表の合間に自分の目の前で海外の方が会話を始め、そこからICPCやらカザフスタン出身やら漏れ聞こえてきたので、思わず話しかけた。ICPC WFの関係者とのこと。自分はYandex Cupという別のコンテストで行ったよ、と伝えた。ナイスコミュニケーション。

休憩時間、受付のところには大量のパンと少しの果物、コーヒー・紅茶・緑茶が置いてあった。果物がお菓子に変わったりしつつ学会期間中は毎日用意されていて、サービスの良さにびっくりした。パンは毎日気が遠くなるほど余っていたので、持ち帰って朝食にしたりしていた。

昼食は昨日のwelcome receptionで集まっていた人々と「四季花まる」へ。系列店が複数あり、有名なところだと行列が絶えないらしい。連れてきてもらった店舗は若干マイナーなのか待たずに入れた。食事のメンバーは、現在の所属はまちまちでも学部や院が北海道大学だった方ばかりで、金曜日までほぼ毎日一緒に行動させてもらったが店には事欠かなかった。

午後の発表も乗り越えて、ラストはいよいよポスターセッション。昼過ぎの時点ですでに貼り出されていたため、自分のものをチェックしたり、他のポスターを読んだりしておいた。

発表を終えての感想は、とにかく人が多く、場所が狭く、時間が短い。左右のポスターが繁盛していると通路が完全にブロックされ、自分の前だけ誰もおらずみじめな気持ちになったりした。結局2時間ずっと自分のポスターの前で客を待ち構えていた。

以下、反省点。ポスターは自分含め横向きが多かったが、議論用のホワイトボードシートが横向きなら下に、縦向きなら横に用意されていて、後者のほうが書きやすい。その点では縦向きのほうが良いかもしれない。運営の先生もスペースの制約から縦向きのほうがありがたいと仰っておられた。また文字を強調する際にサイズまで変えている人がいて、かなり見やすいと思った。

受け答えは、ポスターを読んでから質問してくれる人に対しては何とかなったはず。しかし最初から説明してくれと言われるとボロボロになってしまい、冷や汗をかいた。直前にもう少し内容を振り返っておくべきだった。また、口頭で補うつもりでポスターの記述を省きすぎるとやりづらい。英語が堪能でないなら、書いてない物事をその場で説明できるとは思わないほうがよい。

午後8時過ぎまで会場で過ごし、追い出されるようにして外に出た。昼とほぼ同じメンバーで夕食。誰も食べたいものを挙げられず、しばらく彷徨ったあと「金獅子のホルモン」という店に入った。ホルモンが焼けたかどうか判定するのが難しかった。

午後10時くらいにホテルに帰り着いた。先週の週記を投稿するのは諦め、日付が変わるまでずっとスマホを弄っていた。シャワーを浴びて午前1時半就寝。

07/22(火)

午前8時過ぎ起床。昨日会場から持ち帰ってきたパンを食べたが、カロリーメイトみたいにボソボソしていてやたらとお腹にたまる。食後はすぐには動けず、しばらく横になって休んでいるうちに最初の講演は終わってしまった。

会場到着。前のほうの席をよく見ると思ったより空きがあったので、そちらに入れてもらった。これでスライドがよく見えるぞと意気込んだはよいものの、眠気に負けまくりで午前中を終えた。

昼食はスープカレー。最初に向かった「ピカンティ」は満員だったので「カレー食堂 心」に行った。ここは3月にも来た店で、今回は奥の広い座敷席に通され、間口こそ狭いけれども確かに席数が多いことを5か月越しに確認できた。辛さを選ぶ際、5辛は市販のカレーの辛口だと言われたが、注文してみると明らかにそれより辛かった。

「カレー食堂 心」に行ってみた。着いたら同じ研究集会の参加者と思しき10人規模の集団が並んでいて、回れ右して帰ろうかとも思ったが、席数が多いのか案外早く中に入ることができた。

週記（2025/03/03-2025/03/09） - kotatsugameの日記

午後の発表を聞いている間に腹の調子が悪くなってきて大変だった。昨日のように最後列に座っていれば、そこは通路でもあるから出入りしやすいのだが、今日は少し前のほうの席に座ってしまったため横の人にどいてもらう必要がある。しかもその横の人が寝ており、ちょっとした絶望を味わった。

最後はポスターセッション。ポスターを読んで、人がいれば少し質問して立ち去るということを繰り返したが、全部説明してもらったものもいくつかあった。一対一で、あらかじめポスターなり論文なりを読んでから聞くと理解できる。しかし多人数に対する説明に混ぜてもらった際は、周りの話し声もあってほとんど聞き取れなかった。

welcome receptionで話したオーストリアのD1の方と再会したので、彼のポスターも説明してもらったものの、その分野に関する基礎的な知識すらない状態だったので何もわからなかった。かなり丁寧に説明してくれたのにこのありさまで本当に申し訳ない。

夕食は「黒むぎ」という蕎麦屋。大盛りにしても量が若干物足りなくて、サイドメニューをいくつか注文した。

午後9時前にホテルに戻ってきてすぐシャワーを浴び、深夜のコンテストに備えて仮眠の体制に入ったが、うっかりハーメルンで時間を消し飛ばしてしまった。午後11時半からECR181。

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

書く

東横インのWi-Fiが貧弱すぎる！ブツブツ途切れるくせして再接続もスムーズにはいかない。スマホのテザリングに切り替えるのに、序盤少し時間をロスしてしまった。

午前1時半就寝。

07/23(水)

午前8時過ぎ起床。またしても会場から持ち帰ったパンで朝食を済ませ、今日は遅刻せずに会場に到着した。

今日の朝一番の講演はグラフ多項式の研究者であるEllis-Monaghan先生によるもので、全体を通して一番楽しみにしていた。修士のときに扱っていたものとその発展が話され、あまりにも自分向けで感動。最近の研究の動向についても聞けて大変ありがたかった。その流れでポスター発表の「On the reconstruction of trees from their chromatic symmetric functions」も紹介されたが、これはちょうど昨日聞きに行って面白かったものの一つであった。

この日以降、会場には一日目と二日目のポスターが全部貼り出されていた。改めて見て回ると興味がある内容なのに見落としていたものが多い。というかそもそも、なかったものが増えている気がする。飛行機の遅れなどでポスターセッションに間に合わなかった人がいたのかもしれない。

昼食は会場にあったおにぎりで済ませ、午後からExcursion。自分は「野外博物館 北海道開拓の村」に行くコースを選択していた。広い敷地に北海道各地の古い建造物を集めて、当時の街・漁村・農村・山村を再現した施設である。

www.kaitaku.or.jp

大学からバスに分乗し、1時間ほどで到着。入り口の建物でチケットと英語のパンフレットを渡され、あとはご自由にどうぞとばかり自由行動が始まった。バスに乗った時点で分かっていたが、知り合いどころか日本人がほとんどいない。どうしようか迷っていたら、月曜日に話したカザフスタン出身の方が誘ってくれたので、彼を含む三人と一緒に行動した。多くの人とは逆順で、山村から順に回った。

それにしても暑い。野外を歩き回るのは辛いし、展示されている建物にエアコンが設置されているわけでもない。特に今日は、ただでさえ平年よりずっと暑い今週のうちでも最も気温が高くなる日だったため、全員汗まみれになっていた。

展示の説明文がほとんど英訳されていないのも残念だった。自分にできる範囲で説明を試みたものの、英語の語彙も北海道開拓に関する知識も全く足りなかった。それでも、活版印刷の展示では我ながらいい感じのことが話せたと思う。大量に並んだ活字を前にして、漢字は「音」ではなく「意味」の記号だからそれぞれの文字に読みが複数あると言うと、結構ウケた。

最後に売店でアイスを買って食べた。同様のことをする参加者が多く、売店の周りに大量にたむろしていた。三々五々バスに戻り、大学へ向けて出発。行きでは活発な会話が交わされていたが、帰りは全員疲れ果てて静まり返っていた。そのまま、特に締めの挨拶もなく解散。

実はちょっとしたご縁で、運営の先生にExcursionの様子を撮ってきてくれと「写ルンです」を渡されていた。結構やる気になっていたのだが成果は芳しくない。逆順で回ったのですれ違いながら様々なグループを撮れるかと思いきや、前半はほぼ人がおらず、ようやくすれ違う頃にはグループがかなりばらけていて、誰を撮るべきかが難しい。迷っていたら既定の枚数を撮りきれなかった。

そもそも「写ルンです」で写真を撮るのはかなり大変。覗き窓は小さくてあまりよく見えず、写真の構図を考えることができない。また後から聞いたら、ちょっとでも陰になっていたらフラッシュを焚く必要があるそうで、これをしていなかったため屋内の写真は全滅なのではないかと思う。

Excursionはほかに二つのコースがあり、そちらでは有志により集合写真が撮影されていた。自分はそこまで積極性を発揮できなかった。

疲れているが今日はゲーセンに行く絶好の機会。ホテルに戻ってシャワーだけ浴び、すすきののラウンドワンに向かった。ホテルでグダグダしすぎてプレイ受付が終了するまで4時間弱しかない中、22クレ遊んだ。バージョンアップ以来初めてで、新曲を簡単なほうから半分くらい埋めて理論値を六つ出した。

すすきのには遅くまで営業している店が多いものの、そこで食事すると終電を逃してしまう。札幌駅まで戻ってきてから夜中でも営業しているラーメン屋を探し、「久楽」というところに行った。

ホテルに戻ってもう一度シャワーを浴び、午前2時就寝。

07/24(木)

午前8時過ぎ起床。布団からなかなか起き上がれず、ホテルを出たころには最初の講演が始まっていた。昨日はパンを持ち帰ることができなかったため、コンビニのゼリー飲料で朝食を済ませた。

30分ほど遅刻して会場に着いてみると、なんとSageMathの話をしていてびっくり。これならちゃんと最初から聞けばよかった。昼前に15分の枠が用意されていたSoftware Demonstrationの発表も同じ内容で、朝一番の講演が前提となっていた。15分しかない中で説明を済ませるためには、こういう形にならざるを得ないのかもしれない。

休憩時間、飲み物のラインナップに粉末タイプのオニオンスープが追加されていた。小さめの紙コップで溶かすとどうしても濃くなるが、しょっぱくて美味しい。この日からはずっとそればかり飲んでいた。

昼食は「三代目月見軒」のみそキムチラーメン。チャーハンは大盛りを頼み、三人分に取り分けてもらうとこのような形で出てきた。

午後の講演では「Real Stability and Log Concavity are coNP-Hard」が興味深かった。指導教員に無茶ぶりをされたのでそれが難しいことを示した、というストーリーがまず面白い。関数の性質とグラフのクリーク数の関係を述べる結果が存在するらしく、証明はそれに帰着していた。アルゴリズム的な書き換えでない点を目新しく感じた。

夜はBanquetとして、サッポロビール園でジンギスカンを食べた。机が狭くて窮屈だし、周り中肉を焼いていて暑いし煙いし、セルフサービスの食べ物や飲み物には常に長蛇の列ができているし、とても快適とは言えない。それでも肉は美味しかった。

会場に入るとき、二日目のポスター発表で説明してくれたオーストリアのD1の方が話しかけてくれて、流れで一緒のテーブルに座った。近くの席は先生だらけ。特に隣にEllis-Monaghan先生がおられ、少し会話する機会を得た。教科書「Handbook of the Tutte Polynomial and Related Topics」を紹介していただいたほか、ツーショットも撮ったが、食後で汗をかいた先生が恥ずかしがっておられたためツイートはしていない。

いい気分でホテルに帰り、シャワーを浴びて寝る準備を整えたところで、集中講義のレポートの提出期限が明日に迫っていることに気づき、慌てて先週解いた分の清書を済ませた。本当は残りも解くつもりだったが、さすがにもう時間がない。

午前2時就寝。

07/25(金)

午前8時半起床。最終日の今日も朝食は会場でもらってきたパンだった。結局東横インの無料朝食は食べずじまい。荷物をまとめてチェックアウトし、札幌駅のコインロッカーにスーツケースを預けてから会場に向かった。

少し遅刻して到着し、最初の発表の時間で、レポートの見直しと提出をした。午前中の発表のうち、2月の研究集会でお会いした方のものは一所懸命聞いたものの、ほかは寝落ちしてばかりだった。

今日から一泊二日で名古屋の研究集会に参加する。

週記（2025/02/10-2025/02/16） - kotatsugameの日記

昼食は「SOUP CURRY KING」。具材が大きいし、熱いし、噛み切れないしでちょっと大変だった。

購買に行く機会があったのでしおりを購入した。

午後の部の休憩時間には学生発表の表彰が行われた。日本の伝統的なスタイルだと言って、受賞者に表彰状を受け取る姿勢について指導していた時点でコミカルだったが、渡す前に「表彰状、○○殿……」といつもの定型文が日本語で読み上げられて、ちょっと笑ってしまった。また賞品として素数大富豪、和訳された書籍「数学者たちの黒板」、羽衣チョーク一箱が渡されていた。

すべての発表を聞き終えての感想として、まず第一にStanley先生の偉大さを実感した。氏の結果や予想を動機とした研究が山のように存在する。また自分が興味のある多項式関連では、June Huhらによるlog-concavityの結果を応用するものが目立ったように思う。それ以外でもlog-concavityに関する発表は多かった。

この国際会議における最後のイベントは「Ice cream」で、何があるのかと思ったら北大マルシェに行って北大牧場のアイスクリームを受け取るだけだった。会場からとっとと人を追い出すための恒例になっているらしい。

自分のポスターを回収し、アイスを食べるともう帰りの時間。仲良くなった人々に別れを告げ、新千歳空港に向かった。午後7時45分発の最終便に乗り仙台へ。

仙台駅まで戻ってきて、東口のBiViに入っている「餃子のすみ田」で食事した。

また、サープラで5クレだけ遊んだ。このゲーセンは今月末で閉店してしまうため、おそらくこれが最後のプレイとなるだろう。9月頭までとなっているチュウニズムのグッズキャンペーンを実施していてびっくりしたが、店頭賞品はちゃんとすべて売り切れていた。

駅前のゲーセン・サープラが閉店するようだ。

週記（2025/06/02-2025/06/08） - kotatsugameの日記

日付が変わる前に帰宅。すぐシャワーを浴びたあと、PCを触って過ごした。午前3時過ぎ就寝。

07/26(土)

午後1時起床。

ハーメルンで「傍に立つ君は完璧で究極のアイドル」の更新分を読んだ。舞台編はほぼオリジナル展開らしく、やりたい放題。1話あたりの文字数がどんどん多くなっており、気合いを入れないとなかなか読み進められなかった。

syosetu.org

ハーメルンで「傍に立つ君は完璧で究極のアイドル」を読了。

週記（2024/05/20-2024/05/26） - kotatsugameの日記

二度寝して起きたら午後8時。ちょっと喉に違和感がある中、午後9時からABC416に出た。

AtCoder Beginner Contest 416 - AtCoder

Aはよい。Bは最近流行りのDaily Akari。動画では恥ずかしながらdailyとdiaryを混同している。Cは全列挙。DはA_i+B_i\ge Mとなるペアの数を最大化すればよく、いくつ作れるか二分探索した。Eは空路のための超頂点を一つ用意すると更新クエリがどちらも辺追加になるため、ワーシャルフロイドの更新をO(N^2)で行えば間に合う。Fは若干面倒な木dp。

Gは各長さにつき最小の文字列しか使用しない。この10個を集め、各文字列を使う回数を決めると、いつものa+b\lt b+aでソートした順序で繋げるのが最適になる。ここで、より後ろの文字列を使う個数は前にある文字列の長さ未満になるのではと考えた。これが成立すれば、パターンは9!しかないため全列挙して比較できる。出したら通った。しかしよく考えてみると証明ができていない。

68分で全完して7位。

www.youtube.com

ハーメルンを読んで午前5時半就寝。

07/27(日)

今日は競プロサークルの活動としてBBQがあるため、午前9時過ぎに起きた。しかし喉に結構な痛みがある。これはいけないということで、欠席することにした。

二度寝、三度寝と繰り返しつつハーメルン「まぁ我慢強い勇者ならどんな苦難も乗り越えてアイドルを推せるだろう」を読了。1年前に最初の十数話を読んでからずっと放置していたが、そのうちに完結していたため、改めて最初から読み直した。以前は苦手意識を抱いていた妊娠する展開も、そういうものと分かっていれば案外気にならなかった。そもそもこれは話の前提に当たるため気にしてもしょうがない。

syosetu.org

「まぁ我慢強い勇者ならどんな苦難も乗り越えてアイドルを推せるだろう」。原作準拠なのかもしれないが、ヒロインが妊娠する展開には慣れない。

週記（2024/06/17-2024/06/23） - kotatsugameの日記

午後11時半からCF #1039 div.2。

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

書く

www.youtube.com

日記を書いて、午前8時半就寝。

週記（2025/07/14-2025/07/20）

07/14(月)

午後2時起床。しばらく布団でゴロゴロして過ごし、午後3時半からインターン先定例会に出席した。進捗はなし。

勉強会ではスモール・ワールド現象と、それを応用したベクトル検索のアルゴリズムが紹介された。この現象は人間とその知り合い関係でグラフを作ったとき平均距離が短くなるという話で、ランダムグラフにおいてはWatts-Strogatz modelによって再現される。以前Barabási–Albert modelがSNSにおける人間関係を表すと聞いたので同じかと思ったが、そちらは平均距離こそ短くなってもクラスターを構成しないという点で異なるらしい。

学食に行ってきた後は、以下のmaimai配信を見ていた。

www.youtube.com

数日前のアプデで超高難度のイベントが始まったらしく、完走目指してここ数日ランカーたちがこぞって配信していた。特に最後の曲は情報が徹底して隠されており、前半を乗り越えた後は残り何秒耐えたらいいのかすらわからない状態だったが、最も先まで到達できたプレイヤーのレートが上がったため、いよいよ終わりが近いと噂されていた。

配信の切り抜きや言及などがTwitterに盛んに流れてきて、アーケード音ゲーの配信では空前絶後の同接1万5000人だか6000人だかを集めるなか、チャンネル主が見事完走。EXTRA TRACKとしてエンディングのような曲調の新曲をプレイしたり、公式からついに完走者が出た旨のツイートがあったりして、大盛況のうちに終わった。

本当にすごい盛り上がりだった。「音ゲー史に残るイベント」という評価もたくさん目にしたし、他の音ゲーでもこんなイベントが欲しいというツイートが無数にあった。しかし、このイベントの何がそんなに人を惹きつけたのだろうか？特に、自分はなぜこんなに興奮しているのだろうか？

譜面にまともに取り組めるのがランカーだけというのはやはり解禁イベントの宿命であり、他と状況は変わらない。一般プレイヤーの協力で進行する箇所がほんの少しあったらしいとは言え、あまり重要とは思えない。maimaiのこれまでの歴史を回収する集大成のようなストーリーが長くプレイしている人にとってはたまらなかったという話で、これは大きいかもしれないが、しかし自分にとっては関係ない話。

自分なりの結論としては、同じランカー向けでも「誰が最初にクリアするか」だったのが、どんどん情報が明かされていく度あまりの難しさに「誰かクリアしてくれ」という総力戦の様相を呈していく、そこが面白かったのだと思う。

先週の週記を書いて日付が変わる前に投稿。その後ラノベ「社畜剣聖、配信者になる」4巻を読んだ。

特に前半が面白かった。一般探索者と合同のダンジョンアタックということで主人公たちの格の違いがよくわかる。ちゃんと遠慮して手柄を譲っている分活躍は少なめかと思ったが、もちろんそんなことはなく、見合う敵が用意されていた。単なる雑魚狩りで終わらなかったというのも嬉しい点。

午前6時半就寝。

07/15(火)

午後0時半起床。

ラノベ「好きだった子をメイドにしたら、俺の部屋でこっそりナニかしている」を読了。上流階級出身の主人公が出自に見合った振る舞いをしようと決意した矢先に、その出自に関する致命的な事実が明らかにされて梯子を外されたような気分になった。タイトルも回収されたしおそらくこれがストーリーのメインなのだが、少し淫靡なパッケージやそれまでの話の雰囲気と大きく食い違っており、ちょっとついていけない。

午後5時前、散髪してもらいに大学生協に向かった。それが終わった後は学食で食事。特別なイベントの日でもないのに非常に長い行列がずっと途切れず、不便だった。文系のほうの食堂が改装のため閉店中なので、そのせいだろう。

帰宅してからはCHUNITHMのアプデ直前生放送を見ていた。strさんの3番勝負が目当てだったが、やはり圧倒的。「ニルヴの心臓」の前半を理論値で通したところは見ているだけなのに心臓が張り裂けそうになった。出演者たちの押し殺した驚愕の声が配信に乗っていて面白い。後半も交差して絡まったように見えた手が正しい位置に瞬間移動したりとさすがのリカバリ力。

そういえば、稼働10周年に合わせて明日がアプデ日らしい。明後日だと勘違いしていたので、削除要素の回収などが間に合っていてよかった。

www.youtube.com

ラノベを読んで午前0時半くらいに就寝。

07/16(水)

午前9時起床。

ラノベ「お嬢様頭脳戦」を読了。謎のゲームにおける企業の跡継ぎたちの対戦結果が経済活動に影響を及ぼすことについても、主人公がそのゲームでほぼ無敗の戦績を誇る強力なプレイヤーであることについても、説得力が感じられなかった。こうなると主人公たちが策をめぐらしてゲームに勝ったところで、その強さよりも負けた側の弱さが要因に見えてくる。

登校して午後1時半から後輩のセミナーに参加した。最近新しいテキストを始めたらしいが、初回のセミナーを逃してしまったのか内容についていくのが精一杯で、黒板の計算を追っているうちに終わった。

学食で食事した後、院生室で明日のセミナー準備。ところでトイレの悪臭問題はもうばっちり解決されており、謎の小さな機械が導入されて、まるで香水売り場にいるみたいに露骨な良い香りが漂っていた。また問題になったトイレ以外にも数学棟のすべてのトイレに芳香剤が2個ずつ配備されていた。

同じ階にある男子トイレが非常に臭いと聞き、怖いもの見たさ（嗅ぎたさ？）で行ってみたところ、確かに使い込まれた公衆トイレのようなアンモニア臭がした。

週記（2025/06/23-2025/06/29） - kotatsugameの日記

午後11時半くらいに帰宅。それから家のパソコンでプログラムを書き、数値計算を始めた。夜中ずっと試行錯誤を続けていたら朝方にはそこそこの結果がまとまったため、これもセミナー資料に追加した。

午前10時就寝。

07/17(木)

午後1時起床。すぐ登校して半から他のセミナーに出た。本当に何もわからなかった。

それが終了して、午後3時半から自分のセミナー。もっぱら昨日の計算について話していたら終わった。計算結果よりはその理論的な話。別に難しいことをしたわけではないが、ちょうど良い理論付けができているので、ずいぶん久しぶりのちゃんとした進展になったはず。

午後5時終了。学食で食事して、院生室に行き先月の集中講義のレポート課題に手を付けた。来週金曜日が締め切りだが、来週一杯は学会参加のためあまり時間を割けない見込み。

演習問題とその解答を見やすく表示するため、tcolorboxを使ってみることにした。しかしなぜかうまく表示されない。Geminiを問い詰めつつしばらく格闘してみても全然ダメだったが、後輩のTeXファイルを貰って丸ごとコピペするとちゃんと表示される。そこから記述を削除していき、ついに原因が判明した。graphicxパッケージを読み込む際のオプションにdvipdfmxを付ける必要があったらしい。

午後11時に帰宅して、半からCF #1037 div.3に出た。

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

Aは最小の文字。Bは適当に。Cはできるだけ小刻みに上がっていく。Dは貪欲が正当。Eはa_i=\operatorname{lcm}(p_i,s_i)でOKかチェック。Fは根付き木にして、各頂点について子の情報を集計しておく。取得も更新も親だけ気にすればよい。

Gは要素をdistinctだと思い込み、中央値と右端または左端を固定して、逆の端を限界まで伸ばしMINを見る。正確には「中央値がv以上」という条件にした。これだと値を\pm 1に置き換えた際の累積和で簡単に記述できる。

全完、コンテスト終了直後は3位。しかし上二人のFが後からopen hacking phaseで落とされて優勝した。隣接する頂点の情報を集計する問題は、次数の大小で分けてクエリごとにO(\sqrt m)個の頂点を見ることが多いが、今回のようにグラフが木の場合は高々1頂点にできる。そうしていなかった人たちが落とされたようだ。

また、Gは区間長の偶奇によって累積和が0以上なのか1以上なのか異なるため、コンテスト中はそこを気にしていたが、パリティを考えれば0以上で書いてしまってOKだということをYouTubeコメントで指摘してもらった。

www.youtube.com

ハーメルン「胡蝶の夢、或いは不労所得の夢」を読んだ。最近読んだ「告知事項（隣人がVtuberです）」と同じく逆行とVTuberを扱う話だが、こちらは主人公自身がVTuberになっている。設定は良いものの主人公のメンタルの不安定さがちょっと気になる。

syosetu.org

午前5時就寝。

07/18(金)

午前9時起床。

登校して後輩のセミナーに参加した。前回よりは何をしていたか分かったと思うが、特に言えることもなく、ただ聞いているだけに終わった。それにしても1週間に2回セミナー発表をするのはかなり大変そう。

セミナーが正午に終わったあと、しばらく待ってピークを終えた学食で食事。それから院生室で集中講義のレポートに取り組んだ。前半は結構簡単に解ける。後半は難しめだが、夕食後に後輩と相談して、さらに数問解けた。雰囲気は同じだし、手を動かせば残りも解けそうに見える。

夜は久しぶりに麻雀の卓が立った。今日の後輩のセミナーに参加していた一人が打てるそうなので、わざわざ合同棟の院生室から数学棟に来てもらって卓を囲んだ。3半荘打って、着順は覚えていない。めくり合いに連敗したりしてほとんど上がれなかったものの、なぜか放銃もほぼなく、2着か3着を繰り返していたはず。

夕食が早かったので腹が減り、購買でカップ麺を買って食べた。院生室で食べるとお湯が常備されているしカップのゴミを気にしなくてよいし、かなり楽。

それから急激に眠気が来て、椅子を並べて横になったら思いっきり寝てしまった。気づいたら午前2時前。まだ院生室には二人残っていたが、ちょうど帰り支度を始めたところで、自分を寝かせておくか起こすか迷っていたらしい。

帰宅してから後輩と相談して解いた分のレポートの清書を行った。午前6時半就寝。

07/19(土)

若干の中途覚醒がありつつ午後5時起床。長い間布団でゴロゴロし、食事して、午後9時からABC415に参加した。

Japan Registry Services (JPRS) Programming Contest 2025#2 (AtCoder Beginner Contest 415) - AtCoder

Aはよい。Bは出力形式が特殊。CはbitDPっぽく。Dは瓶A-B本とシールを引き換えていると思うことができる。実はA-Bの昇順に操作できるだけ操作するのが正当。Eは左上ではなく右下からdpするとうまくいく。Fは区間長や両端点の情報を区間更新の遅延セグ木で管理した。

Gは難しかった。瓶A-B本と引き換えに答えをB増やすものと思ってみる。瓶が残り\max A本を下回らないうちは、容量が非常に大きい個数制限なしナップザック問題になっている。基本的には「効率」B/(A-B)が最も大きい行動を繰り返すのがよいだろう。

Bが同じならA-Bが小さいものを残すなどの方法で、行動を300種類程度にすることができる。また、B_i/(A_i-B_i)\ge B_j/(A_j-B_j)のとき、行動jをA_i-B_i回行う代わりに行動iをA_j-B_j回行うとしてよいため、効率が最大でない行動はそれぞれ、高々300回程度しか行わないことになった。

しかしこの評価では容量3003程度のナップザック問題を解く必要があり、まだ十分でない。しかしコンテスト中は3002になっていると勘違いし、実際そのまま通った。

複数種類の行動を一気に組み替えることを考えてみる。効率B/(A-B)以下の行動を合計でA-B回以上行うなら、適当に並べてコストの累積和\bmod{(A-B)}に鳩ノ巣原理を適用することにより、ある区間のコストがピッタリA-Bの倍数になるとわかる。そこを置き換えても損しない。これで効率が最大でない行動は合計300回程度しか行わないことがわかり、先ほどの容量を制限したdpの正当性が示された。

全完32位。Gに32分かけたのがダメダメだった。あんまりナップザック問題であることを意識せずに考察していたのがよくなかった。

www.youtube.com

動画公開準備でタイムスタンプを作っていたらギリギリになったが、午後11時半からCF #1038 combinedに出た。

Dashboard - Order Capital Round 1 (Codeforces Round 1038, Div. 1 + Div. 2) - Codeforces

書く

www.youtube.com

日記を書いて午前7時半就寝。

07/20(日)

午前10時起床。今日から来週金曜日まで、国際会議「FPSAC」のため北海道大学に行く。3月に2回行ったばかりなので結構な頻度だ。

手早く荷造りをして午前11時過ぎに出発。なんとスーツケースのキャリーバーが引き出せなくなっていることが判明し、頑張って持ち上げて運ぶ羽目になった。

仙台空港に到着し、チェックインと保安検査を済ませたあと、ラーメン屋「だし廊」で食事した。前から気になっていたので来られて嬉しい。仙台空港限定のトビウオ油そばは、麺が細麺だったので油そばとして少し物珍しさを感じた。タレが少なかったのでかなり入念に混ぜた。美味しかった。

搭乗ゲート付近にラーメン屋「だし廊」があるのを見て、ここで朝食を摂ればよかったなと思った。

週記（2025/03/24-2025/03/30） - kotatsugameの日記

午後1時20分発の便で新千歳空港へ。そこから電車で札幌駅へ向かい、スーツケースを持ち上げてヘトヘトになりながら今日泊まるホテルへたどり着いたら、午後4時だった。睡眠時間確保のためすぐ仮眠に入った。

なかなか起きられず、気付けば午後6時を回っていた。学会前日の今日は午後5時から会場でwelcome receptionがあるそうだ。参加費が無料なのでそう大げさなものではないだろうと思っていたが、調べたら着席形式のパーティーの参加記が出てきて、果たして遅刻が許されるのか不安になる。恐る恐る会場に向かった。

広大な敷地を持つ北海道大学だが、今回の会場は学術交流会館という、最も駅に近い建物になっている。駅北口のホテルから歩いて10分ほどで着き、受付で学生スタッフから名札とノベルティを受け取った。

この名札は3月初めの「数学総合若手研究集会」と同じつくりで、当時ホルダーを回収されたからそれも再利用したのだろう。そもそも学会の予行演習として研究集会側に貸し出された名札ホルダーだった、という噂も聞いた記憶がある。

結局、welcome receptionは出入り自由の立食形式だった。同行者もいないし発表者の知り合いもほぼいないので、寄る辺ない気持ちで会場をうろついていたが、3月に知り合った方を見つけて挨拶することができた。あとはその流れで、周辺に固まっていた日本の学生たちと過ごしていた。

知り合いができて腰を落ち着けると気も大きくなるもので、目が合った海外の方に積極的に話しかけてみたものの、英語があまり聞き取れないし語彙も全然口から出てこないし、コミュニケーションには失敗気味だった。

食事はオードブル5皿・サンドイッチ4皿・寿司を一セットとして、計九セットが部屋にぎっしり並んでいた。ソフトドリンクや、自分は飲まなかったがアルコールもたくさん。学会全体で参加者が300人くらいいるとのことで、全員来ても大丈夫なくらい用意したのだろうか。当然そんなわけはなかったし、そもそも部屋に入りきらないだろう。最終的には大量に余っていた。

午後8時半くらいに解散。ホテルに戻り、午後9時からARC202 div.1に出た。

AtCoder Regular Contest 202 (Div. 1) - AtCoder

Aは、数列を最大値vで分割すると、残ったそれぞれの区間を操作でvのみにする必要がある。何回の操作でいくつのvになるか再帰的に求めていくことができる。ペナ率が高かったのでしばらく間違いを探していたが、結局そのまま投げたら通った。vに揃えるところで一旦ストップするような解法だったのが良かったらしい。vが四つあったとき、先に真ん中二つをマージしてはいけない。

Bは問題を見てすぐ実験を始め、同じ行だと\pm 1のどちらを選択するかに綺麗なパターンがあることに気づいた。本来はここで考察を行い、なぜそうなっているのか理解するべきだったのだが、そのまま実験だけでさらなる条件を探しに行った結果、とんでもない時間がかかった。

Wが奇数のときは簡単で、\pm 1が行ごとに完全に一致するため、パターンがかなりシンプルになる。グッと睨むとH個の\pm 1の和がWと互いに素であればよいことが判明し、実験と一致した。

Wが偶数のときは\pm 1が交互に現れる行も存在する。どちらが先に現れるかは問題でないらしい。これを0として扱い、H個の-1,0,+1の和がW/2と互いに素であればよいことを何とか見抜いた。数え上げはcombinationを使う方法がわからなかったため、FPSで(x^{-1}+2+x)^Hを計算した。

100分弱かけて辛うじてAC。この時点でBもCも100人以上に解かれており、絶望しながらCへ進んだ。もう考察で何とかする時間も気力もないため、レピュニット数のWikipediaを読みつつ実験を始めた。

m\mid nならR_m\mid R_mらしいので、素因数分解のようなことができそう。R_{p^e}で割れるだけ割った残りが互いに素だったりしないかと期待したものの、これは不成立だった。しかしどこで不成立になっているか見た感じ、約数を列挙してその「寄与」を取り除いておくのはうまくいきそう。

このくらいで残り時間が数分になったため、実験はやめて書き始めた。自身の約数の寄与で割れるだけ割った値を、新たに自身の寄与としてみる。ギリギリで実装を終え、サンプル1と2が正しいことまで確認し、サンプル3は最初の1行だけ見て、投げた。ほとんど何もチェックしていないに等しかったが、なんとAC。残り1分半だった。

3完69位でパフォーマンス2672、レートは2885→2865(-20)。結構痛いがCが間に合って本当に良かった。

早速明日がポスター発表の本番である。自分の発表自体は何とかなるかなと楽観的に構え、見て回る時間がないであろう同日の発表をチェックした。午前2時半就寝。

週記（2025/07/07-2025/07/13）

07/07(月)

午後3時過ぎ起床。

半からインターン先定例会に参加した。今週も進捗はなし。勉強会は半導体の話だった。高校物理の教科書に書いてあったが、詳細はすでに忘却。電子の不足を正孔と呼び、まるで正の電荷をもつ電子のように扱うことだけは面白い考え方だと思ったので覚えていた。

解散後学食で食事し、先週の週記を書いていた。午後11時過ぎに投稿。

その直後に一部のスクショをツイートした。TLで見かけた、問題に対する当を得ていない言及についてのもので、それを指摘するというよりは自分のモヤモヤを晴らす目的である。まあ別に「等比中項」というキーワードがそれほど盛んに言及されていたわけではなかったはず。ただたまたま目についただけ。

明日はホスフィンと家飲みする予定なので部屋の掃除をする必要があるが、眠くて身動きが取れない。起きてから頑張ることにし、日付が変わってすぐ寝た。

07/08(火)

午前9時半起床。途中1時間半ほど中途覚醒してしまったが、何とか寝直すことができた。

部屋の掃除とセッティングをし、シャワーを浴びてゴミ出ししたら午前11時過ぎ。それからレストランに向かったら予約していた時間に15分ほど遅刻してしまった。

店は「Blair House」。ランチタイムのピークでは待ちが数名おり、遅刻してきたのが申し訳ない。また、コースも一緒に予約していたので二人揃ったら自動で始まるものと思っていたが、店員さんを呼ぶまで始まらず、空のテーブルを挟んでホスフィンと二人で喋っている時間が30分弱あった。ただしこれらの時間がなかったとしても、食べ終わる前に満員状態は解消されていたはず。

コースは「スペシャルランチコース」、写真の順に前菜5品盛り合わせ・サラダ添え、ハーフパスタ、メインの魚料理、ドルチェ、パンとドリンク付き。

前菜では、ラスクに添えられていた芋のソースがほんのり甘くて一番好み。ジンジャーみたいな色で細長い繊維も見えていたため、少し辛いのかなと予想していたが、外されて驚きを得た。一方肉類はどれも塩気が強い。オムレツはかなりあっさりした味わい。

パスタは何種類かあるうち「国産しらす・ズッキーニ・ポテト・ピーマン、ガーリックソース」を選択。生麺パスタの種類も選べたので、一番普通のスパゲティにした。ズッキーニが濃厚でかなり美味しい。

メインは肉料理ではなく魚料理「メヌケ、バルサミコソース」を選択した。白身の淡泊な味にソースがマッチしていた。一口目で骨に当たったのでそれから注意深く食べ進めたが、結局危険だったのは一口目だけだった。さすがにそのあたりの処理はしてくれていたらしい。

ドルチェはいくつかあるうちから「カシスとベリーのムース」を選んだ。写真にはホスフィンが選んだ「はちみつとレモンのムース」も映っている。周囲の模様はチョコレートに加えキウイ、マンゴー、イチゴのソースで描かれている。頑張ってフォークですくい食べた。端のベリーはキンキンに冷えていて、口をスッキリさせてくれる。

ドリンクはフレーバーレモネード。

ドンキに寄りつつ帰宅し、午後3時から宅飲み開始。

以前の家飲みで「逆転裁判1」を完走したため、今日は「逆転裁判2」の最初からスタートした。1話は短い中にも裁判のエッセンスが詰まっており、短くても達成感がある。2話からは逆転裁判の本領発揮ということか、探索パートが入ってくる。また今作から「サイコロック」という機能が追加されて、2話にしてもうかなり大変。

フラグを立てるのに苦労しているうちに眠くなってきて、2時間ほど寝落ちしてしまった。起きたら放置してしまったホスフィンが2話を終わらせていて、びっくりするやら申し訳ないやら。

夕食として、一番町にある「成龍萬寿山」という中華料理屋へ行った。「水煮肉片」が有名で本店に何度か行ったことがあるが、そのすぐ近くに同じ店がもう一つあるとは知らなかった。ねぎ味噌ラーメンを注文。しょっぱくて美味しいものの、細切れのチャーシューを食べるのが体調的に少ししんどかった。

帰宅して逆転裁判2の続き、3話を開始したが、やっぱり眠い。自分がもう無理そうなのを見てホスフィンもプレイを切り上げ、午前2時前に二人して寝た。

07/09(水)

午前6時に目を覚まし、昨日の余りものを食べて処理していた。お酒については半分くらい残ってしまい、かなり残念。消費した分も大半はホスフィンが飲んでくれたもの。昨日は酔いの限界ではなく眠気の限界が来てしまったように思う。最近がっつり寝ていないのが悪かったと反省。少し片づけをして午前8時過ぎに解散した。

換気のために窓を開けたまま二度寝に入ってしまい、午後2時ごろ暑さに耐えかねて起きた。なんだか調子が出ない。移動させていた積読やPCモニターを元通りに戻したところで力尽き、布団に横たわった。少しラノベを読んで午後6時半就寝。

07/10(木)

日付が変わったくらいに目を覚ました。

ICPC横浜大会のためのホテルを取った。今年は参加する2チーム共に全員一人部屋に泊まることを希望したため、コーチ二人だけ同室に。会場にほど近いホテルを取ったので、これでも宿泊費をオーバーしてしまっている。冷静になるとコーチが近くに泊まる必要はない気もする。

あとはインスタに一昨日の食事をアップした。インスタを動かすにはかなり気合いが必要で、タイムラグがある。ベオグラード旅行についても投稿したいがあんまり気力がない。

まだ調子が悪い気がする。布団に戻って、二度寝したりしつつ夜までずっとラノベを読んでいた。4冊読了。

「凡人転生の努力無双」4巻。面白かった。2巻で登場したヒロインのトラウマを祓う巻。もう少し引っ張るかと思っていたので、1冊で終わりまで持っていったのはびっくりした。3巻でもあったヒロインと協力して放つ主人公の必殺技が、また新しく登場したが、ソロでの強さというのは以前から変化がないように思う。主人公の設定を盛りに盛っているので、うかつにインフレさせると周りとつり合いが取れないのだろう。

「U-15サッカー日本代表だけど部活は幼馴染と一緒の文芸部です」。爽やかな青春を思わせる装丁だが、中身はかなりドロドロしたざまぁ系の話で衝撃を受けた。幼馴染との恋愛ではなく、サッカーの実力で絡んでくる輩をボコボコにすることが作品のメインだったように思う。

「口もききたくないあいつと、自習室で甘い筆談」。面白かった。主人公の堅物さが好ましい。ヒロインも外面はクールかつミステリアスでお似合いの二人。挿絵において、ヒロインの雰囲気が公の場とプライベートとでガラリと変わっているが、これはどうやら肌色や頬の赤みだけの違いらしい。それでこんなにギャップを生み出せるのかと驚いた。

「神の代行者（自称）」。設定は非常に好み。「陰の実力者になりたくて！」と同じと言ってしまえば終わりだが、こういうのはいくらあっても良い。しかし文章がそぐわなかった。主人公視点のときに怠けたことをグダグダ言っているのはいいとしても、真面目に恰好付ける場面でも語りが軽く、あんまり雰囲気を作れていないように感じた。

午後5時過ぎに学食に行った。今日はやたら涼しく、空気がこもっている自室より外のほうが快適なくらいだった。

午後8時就寝。

07/11(金)

午前3時半起床。

「黄金の経験値」7巻を読んだ。面白かった。「森エッティ教授」という序盤からゲーム設定考察勢として掲示板で有名だったプレイヤーが、ついに主人公たちの前に現れ、プレイヤーであると見抜いてくる。ここは初見時かなり衝撃的だった。レアの危機感のないコミカルなふるまいでカバーされてはいるが、結構なストレス展開だと思う。結局主人公たちの仲間入りをしたいだけだったのでセーフ。

二度寝したり布団でゴロゴロしたりで午後3時くらいまで怠惰に過ごしていたが、実はそんなことをしている場合ではない。再来週に迫った国際会議での発表に向けポスターを作成する必要がある。

締め切りが存在して、それは07/11の23時59分とされていた。……UTC-12の。見た目より21時間遅いことに気づいたときから謎の余裕をかましてしまい、この時間までダラダラしてしまった。冷静になるとあと丸一日ちょっとしかなくて大変まずい。しぶしぶ起きて、公開されている昨年のポスターを眺めながら構想を練っていた。

午後7時くらいに学食に行った。今日は昨日に輪をかけて涼しくなり、なんと20度。この気温だと原付に乗るときパーカーを着ていた気がする。今日長そでTシャツで乗ったら寒かった。

帰宅してポスター作製開始。beamerposterについて調べ、Geminiというテーマを知った。ポスターの作例が公開されているため、これをテンプレートとして弄るだけで形になりそう。ポスターは基本縦向きで作るものと思っていたが、作例は横向きだし、昨年のポスターも大半が横向きだったので、それに合わせることにした。

Gemini poster theme - Overleaf, Online LaTeX Editor

それにしてもやる気が一切出ないし、眠い。このまま続けても捗らないと思ったのでいったん寝ることにした。午後9時過ぎ就寝。

07/12(土)

日付が変わってすぐ起床。

眠気覚ましにハーメルン「異能を使った凶悪犯罪ランキング作ったwww」を読んだ。かなり面白かった。投稿開始早々日間ランキングの最上位に躍り出た作品で、実はそのころから読んでいた。毎日投稿でランキング10位から1位を駆け抜け、昨日ついに完結。オチが衝撃的だった。感想に書き込まれた考察をいろいろ眺めてみたが、どんな異能にもカウンター異能が存在し、異能対策局が攻撃対象になったらちゃんと感知できる、というのが好み。

syosetu.org

ポスター作製を開始。生成AIのほうのGeminiに論文や以前作った発表スライドを与えたら自動で作ってくれるんじゃないかと期待したが、「テキストはできるだけ簡潔にまとめるのがポイント」など言うのと同じ口で論文の抜粋を並べた原稿しか出力してくれなかったので、少なくとも初稿は自分で頑張る必要がありそう。ただ、やりたいことが決まっているときにTeXでどう書けばいいか教えてくれるのはかなり役立った。

昼過ぎになってひとまず内容が完成。今度はそれ自体をGeminiにぶん投げて校正・添削してもらった。PDFだけだとOCRに失敗したり文字たちの位置関係を読み取れなかったりしてあまり適切な助言はしてくれないが、TeXコードと共に渡すとかなり有能。

また、先ほどは論文の抜粋ばかりでうまくまとめられていなかったが、すでに存在する文章をポスター向けに圧縮するのは得意らしく、いい感じのアイディアをどんどん出してくれた。以前のやり取りが残っているとそこから不要な内容を引っ張ってくることがあるので、チャットを新規作成して試してみたりもした。

午後5時くらいになって満足いくものが出来上がったので、先生に送ったりホスフィンに送ったりした。ホスフィンはすぐにフィードバックを返してくれて、大変頼りになる。

2時間ほど仮眠した後、フィードバックをもとに最後の仕上げをして、何とか締め切りギリギリに提出することができた。かけた時間は少ないが、表示の調整以外にできることはもう思いつかない。昨年のポスターには論文かと思うくらいに文章が詰め込まれているものがちらほらあって、まあそれらよりは見やすく作れたはず。誤字があったら現地で修正したい。

そのあとすぐ、午後9時からABC414に参加した。

Mirrativ Programming Contest 2025 (AtCoder Beginner Contest 414) - AtCoder

書く

www.youtube.com

少し日記を書いて午前3時就寝。

07/13(日)

朝方から何度か目を覚ましていた記憶がある。今日はゲーセンに行き、深夜からコンテストに参加するつもりだったので、睡眠時間が短いとまずい。その一心で二度寝を繰り返し、午前10時くらいまでは眠ることができた。

ラノベ「社畜剣聖、配信者になる」3巻を読了。主人公を社畜にした元凶と対決。とんでもない事件を引き起こしているし普通に倒して終わりかなと思っていたら、古い友人だったとのことで助命エンドとなりびっくりした。また細かい点だが、斬業モード時の挿絵なのにネクタイを着けたままになっていた。

しばらく日記を書いて、午後3時くらいに外出。立ち食いそばで腹ごしらえしてゲーセンに向かった。それから6時間で35クレプレイ。理論値四つ、14+の新規AJ五つ、さらに来週水曜日までのイベントのクエスト残り二つを完走した。前回削除曲関連の称号を回収したため、これでバージョンアップに向け準備は万端。

「Sparking Revolver」はその昔、13全鳥で最後に残った譜面だった。それから6年半が経ちだいたい押せるようになっていたため、精度は若干悪いものの順当に出た。73小節は左4分の1と右4分の3のトリルで取る運指を追加当時に知って以来ずっと使っている。174小節は押すと直後の全押しのリズムが崩れがちだったので擦った。右、左、二つ目の折り返しで区切ってまた右。

「管弦楽組曲 第3番 ニ長調「第2曲（G線上のアリア）」BWV.1068-2」は一発で出た。上手すぎる。これでイロドリミドリのMASTER譜面は全AJ。全99AJを目指そうと思ったが「色彩過剰のダイアリーミュージック」が残っているのを見て一瞬で断念した。

これらの更新によりOVER POWERが今日一日で14弱伸び、99.14%から99.15%になった。全譜面解禁しているわけではないので総OPがどれだけか不明だったが、99.15%になった瞬間のOPが117495.40だったので、そこから逆算して0.01%伸ばすのにおよそ11.85必要ということが分かった。

帰りに「末廣ラーメン」で食事した。いつもかなり行列の出来ている店だが、このときはたまたま空いていた。確かかなり昔、調べたら2019年9月だった、に一度だけ入ったことがあって、その時は大変混んでおりサービスに不満を抱いた記憶がある。その悪印象が尾を引いて、目立つ位置にあるのに今日まで再訪していなかった。冷房がスポットクーラーと扇風機しかなくて暑かった、というのが今日の感想。

ドンキに寄って午後11時前に帰宅。シャワーを浴び、半からCodechef Starters 194に出た。Ratedラッシュ。これからRated for allの場合に限り日曜開催となる可能性があるらしい。助かる。

https://www.codechef.com/START194A

書く

午前5時就寝。

週記（2025/06/30-2025/07/06）

06/30(月)

午後1時過ぎ起床。2週間前の続きがあって今日も登校した。学食で食事し、午後2時から1時間ちょっとで終了。

昼から大学で用事があったため登校した。

週記（2025/06/16-2025/06/22） - kotatsugameの日記

急いで帰宅して午後3時半からインターン先定例会に出た。進捗は、なし。勉強会は最近話題になっていたALE-Bench/ALE-Agentの話だった。コンテスト運営・AtCoderとの共同研究である点が良いなと思っている。アルゴのほうだと、今はどうか知らないが昔はランダム生成してACコードでverifyしたものを使っていると論文に書いてあった覚えがあり、データセットの質に疑問を抱いていた。

先週の週記を書いて午後10時くらいに投稿。それから今週分のセミナー準備を開始した。

日付が変わり月も変わったのを見計らい、今シーズン初めてエアコンを起動した。6月中旬から一気に暑くなったが、謎のこだわりを発揮して7月になるまで何とか耐え忍んでいた。飲み物の消費量が増えてAmazonの定期購入がまったく追いつかなかったのは面白かった。

午前2時半就寝。

07/01(火)

午前8時過ぎに目を覚まし、論文を読んだりラノベに逃亡したりしていたが、午後2時ごろ寝入って次に起きたら午後9時になっていた。

ラノベ「なぜ逃げるんだい？僕の召喚獣は可愛いよ」2巻を読了。今回はほぼずっと主人公視点だった。相変わらず世界観がよくわからないし、主人公も理解していない様子なので、読んでいると不安になってくる。一方、のんきな主人公と見た目にそぐわず常識的な召喚獣のやり取りには安心感がある。そういう盛大にズレた感じが至る所に見受けられて、作品の特色だなと思った。

午後11時半からCF #1034 div.3。

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

Aは4\mid n。Bは最後の二人までなら何でもOK。Cは自分より左に自分より小さな値があり、右に大きな値があるとどうしようもない。DはBobが勝つ条件で記述すると、1手目で負けず、さらに毎回1がk+1個以上ある状態で返すことが必要。後者については2k\le nのとき、またその場合に限り可能である。

Eは各MEX候補に対しそれを達成するために消さなければならない要素数・消してはならない要素数が決まるため、可能なkが区間になっている。imos法で集計。Fはi\mid p_iを保ったままnを減らしていった。最大の約数とswapするとうまくいく。一度swapに巻き込まれた要素は絶対に不動点にならない。

Gはg:=\gcd(k,m)刻みで値を変化させられるため、(a_i\bmod g)\gt(a_{i+1}\bmod g)となる箇所がいくつあるかわかればクエリに答えられる。そしてgはmの約数であり、今の制約だと高々200個しかないので、全列挙して1点更新の度に差分計算することが可能。

38分で全完して5位。

www.youtube.com

6月の読書記録をツイートした。5月たくさん読んだ反動というわけではないつもりだが、上旬は旅行中を含めてハーメルンに熱中、帰ってきてからはペンシルパズルに熱中してしまった。

それからはずっとセミナー準備をしていた。昼前になって少し大学生協に行き、食事。ほどほどのところで寝ないと夜のCodechefに響くことは分かっているものの、やっていた計算が全然合わずキリの良いところが見つからなくて、結局午後7時半くらいまで続けていた。

07/02(水)

3時間くらいの仮眠を取り、起床。日付が変わった判定にしておく。

午後11時半からCodechef Starters 193に参加した。今日はRated for all。普段Codechef StartersのRated範囲は当日になってようやく発表されるが、今回ばかりは先週のうちに告知されていた。

Invitation to CodeChef Starters 193 (Rated for All) — 2nd July - Codeforces

https://www.codechef.com/START193A

書く

セミナー準備を再開し、午前7時を回ったころにようやくけりがついた。序盤の設定を何度か弄ったらそのたびに大変な計算をやり直す羽目になり、さすがに途中でプログラムを書いた。

いつもはこの時間から眠るところだが、今日はそのままプログラムで別の計算をしてみることにした。徹夜だが日記の日付は変えておこう。

07/03(木)

SageMathと格闘したり出力とにらめっこしたりしているうちに昼になった。シャワーを浴びて登校し、学食で昼食を摂った。

腹を満たしたところ覿面に眠くなってしまい、焦燥感を覚えつつ午後1時半にセミナー開始。話す内容がスラスラ出てこなくてメモを確認することが普段より多かったと思うが、まあ何とかなりはしたと思う。式の意味を捉え切れていなかったところも補足してもらえて非常に有益。午後4時に終了した。

\rho^\ast(g)(f)(x)=f(\rho(g^{-1})(x))であるという意味で\rho^\ast(g)(f)=f\circ\rho(g^{-1})と書きながら、Haskellのポイントフリースタイルを思い出していた。そのまま続けると\rho^\ast(g)=(\bullet\circ\rho(g^{-1}))とか、\rho^\ast=\operatorname{flip}(\circ)\circ\rho\circ\bullet^{-1}になりそう。ところで自分は\rho^\ast(g)(f)(x)という表記がわかりやすいと思っているのだが、一般的ではないかもしれない。付き合っていただいている聴衆に感謝。

明日のICPC国内予選に関するメールが立て続けに3通来ていたので、各チームに転送した。参加登録すると国内予選までに計5通のメールが届くと言われているのに、例年その過半数が前日に届くため、それまでちょっと不安になってしまう。ともかく、これにてコーチ業務は一段落。

学食で食事したあと院生室に行ってしばらく雑談していたが、ちょっと眠すぎてお話にならないため帰宅した。帰り道の原付の運転では注意力も集中力も足りていないなと思うポイントがいくつかあって、なかなか危険だった。

シャワーを浴び、布団に入ってハーメルンの日間ランキングから「告知事項（隣人がVtuberです）」を読んだ。あらすじからは読み取れなかったが逆行転移＋VTuber運営の話で非常に好み。

syosetu.org

午後10時就寝。

07/04(金)

午前2時に目を覚ましてラノベを読んでいた。2冊読了。

「元勇者はのんびり過ごしたい」。タイトル通りののんびりした雰囲気で、非常にリラックスして読めた。読後感がかなり良い。内容は異世界召喚からの帰還ものとしてテンプレを外しておらず、好きな設定なので面白く感じた。

「このコスプレお姉さんは、僕専用らしい」。見た目も中身も単なるちょっとエッチなライトノベルだが、主人公が手掛けたコスプレ衣装がコミケで注目を浴びるシーンは非常に面白かった。また作者の趣味が反映されてか、コスプレにまつわる描写全体に説得力がある。これらが舞台設定に過ぎず話のメインではないことが残念でならない。

今日はICPC国内予選である。コーチとして顔を出すため午後3時過ぎに登校した。とはいえ会場の設営はすでに終了しており、特にすることがない。自分のアイコンを掲示してよいか聞かれたので許可を出したり、コンテスト開始直後の問題文印刷・配布について監督員の先生と打ち合わせをしたりしていた。監督員向けの問題文リンクが存在するらしいので、そちらから印刷をかける。

午後4時半にコンテスト開始。もう一人のコーチ・仮の人さんと手分けして問題文を配り、一息ついたら、もう一般向けにも公開されていたので考え始めた。以下にコメントを書くが、正当性については公式解説と照らし合わせたくらいで実装をしたわけではないことに注意しておく。

https://storage.googleapis.com/files.icpc.jp/domestic2025/problems/problems_ja.pdf

A、Bはよい。Cは制約が不親切だが、サンプルは強いのではないか。

Dはかなり大変だと思う。なんでもできそうな制約の中、考察でどこまで詰めるか、どんな実装方針を取るかでバグらせやすさ・実装の簡潔さが大きく変わる。自分は色が2回以上切り替わっている行を探し、パターンの幅と横のオフセットを特定したあと、縦のオフセットを全探索して毎回O(nm)かけて判定する方針を考えた。盤面を転置して2回解く。まあ公式解説のほうが楽そう。

Eは逆順に見る。つまり、時刻n-2,\dots,0で通る辺を葉のほうから順に決めていく。公式解説のような辺の期限を書き換える方法も考えたものの、それでよいことに自信が持てず違う方針を考えた。

Fは操作する度に同じ文字が固まって離せなくなるものと思ったが、もしそんな問題だったら可能・不可能の判定が複雑すぎる。よく考えると、文字列の末尾のほうから決めればかなり自由だった。操作回数の見積もりがn^2/2\times 2くらいになってかなりギリギリ。

Gは見慣れない設定なのでいったん飛ばし、H。始点が((で終点が))なら、パリティさえ合っていれば可能になる。少し拡張すると「始点から((にたどり着ける」「終点から))にたどり着ける」という条件になる。このどちらかを満たさない場合は()()...()というパターンになり、文字列全体がそうなっているケース以外ではもう片方の条件を必ず満たすことに注意。よって重複にはあまり気を遣わず数え上げることができる。開き括弧と閉じ括弧を入れ替えて2回解くとやりやすいだろう。

Gに戻る。多面体の側面がどのような形をしているか考えると、上下の面の辺を一つずつ使った四角形か、片方が頂点になった三角形である。すると四角形をいくつ作れるかというのが問題になる。四角形を作るためには辺が平行かつ向きがそろっている必要がある。ほんの少しずらすことで四角形を0個にすることはでき、一方四角形を一つ固定すると残りの辺の関係もすべて決まるので、カウントすればよい。実装面では小数の扱いが怖い。

IはARCみたいな難しさ。普通に考えようとしてもとっかかりが見えなかったので、何かアクロバティックで綺麗な解法があるのだろうと予想し、そういう気持ちで考えてみた。まず同じ数がたくさんあるのが気になるが、同じ数同士をswapしないためペアは一意に定まる。すると円にn本の弦があって、それらがすべて直径となるように点を並び替える問題だと思える。

ここからアイディア勝負。直径という条件もまだ扱いにくいので、もっと別の言い方ができないか考えてみると、「すべての弦が互いに交わる」ことが同値だと気づいた。初期状態では交わっていない弦のペアがいくつかあり、1回の操作で高々1ペアしか減らせない。逆にちょうど1ペア減らせることが示せるため、そのペア数をカウントすれば答えになる。これは円を切り開いてBITを使えばできる。

9問の実装にどれくらいかかるかわからないので、もしかしたら3時間で終わらないのかもしれないが、少なくとも考察は終わったので例年より簡単なセットだったのではないか。実際、全完が12チームも出ている。東北大学のチームも上位は8完・6完で、5問解けば進出できた自分の現役時代との違いにめまいがしそう。

その2チームは横浜大会に進出できる見込みであり、自分と仮の人さんが1チームずつコーチをしていたので、二人ともついていく予定。今年も横浜に行けるのはありがたい限りである。

また他のチームでも、会話をこっそり聞いていると考察自体はEやFまで進んでいる様子のところがあった。しかし残念ながらDの実装が大炎上……。この実装の難しさにICPCらしさを感じる。一方で、以降の問題はAtCoder的すぎるのではないかと思った。最も、横浜大会も最近はそんな問題が集まっているから、予選としては正しいのかもしれない。

会場の後片付けをした後、一部の人たち（11名）で打ち上げに向かった。誰も店の候補を挙げられず、しばらく駅でたむろしてスマホを触る謎の時間が発生したが、結局は去年と同じ居酒屋「いただきコッコちゃん」に入った。

帰宅して午前0時半就寝。

07/05(土)

午前7時起床。

「虚構推理短編集 岩永琴子の密室」を読んだ。実はこの本、昨年度末から海外に行く度持って行っていたのに、機内で全然読まなかったので単に本にダメージを与えただけになってしまった。久しぶりに虚構推理シリーズに触れたがやはり面白い。多重解決で頭が混乱。また、第三者視点での岩永琴子たちが定期的に描かれる点がかなり好みだと気づいた。

今日は久しぶりに遊びに行く。正午くらいに外出し、まず昼食を摂る店を探した。駅前は大変混雑していたのでアーケード街のほうを歩き回り、焼肉屋のランチタイム営業に入った。

それからゲーセン。今日は新曲を埋めたり、近々削除される譜面の称号を集めたりして、30クレ遊んだ。最近「デート・ア・ライブ」アニメ5期とのコラボが始まり、精霊たちがキャラクターとして追加された。精霊の番号とマップで走るマス数が対応していて、仕事が丁寧。しかし我らが主人公・五河士道はいなくて残念。あとは身も蓋もないが、アニメ版のイラストが好きではない……。

特大の成果として「Imperishable Night 2006 (2016 Refine)」のAJを出した。しかもあり得ないくらい噛み合って99AJ。普段はこの倍以上赤を出している。

56小節から70小節がメインの難所だが、ここは地力で何とかなるところ。大体、その日数回目のプレイまでは上手いので、序盤でミスしたら捨てゲーしてゴールデンタイムを大切にしておくと吉である。問題は7小節と9小節で、たまに選曲する度ここでお断りされる。今日、直前の階段を右手三鍵で取ると無理なく端フリックが使えることに気づき、やってみると劇的に改善された。

帰りに立ち食いそばを食べた。今年も夏季限定メニュー・薬味そばがスタート。「そばの神田」で最も好きな一杯である。

午後8時過ぎに帰宅し、シャワーを浴びて午後9時からABC413。

Denso Create Programming Contest 2025（AtCoder Beginner Contest 413） - AtCoder

A、Bはよい。Cは与えられた形式のまま列を管理。Dは絶対値の昇順にソートするしかなく、公比が\pm 1のケースだけ注意する。Eはセグ木を降りていきつつ、最小値が前のほうに来るようにreverse。実はswapでよい。Fはゴールまで行けるマス2マスと隣接したマスが新たにゴールまで行けるようになる。普通の多始点BFSで対応可能。Gは左下から右上まで8近傍で隣接した障害物のパスがあればOK。

28分で全完して5位。D問題の等比数列の判定b/a=c/bを(double)b/a==(double)c/bとしてWAを出した人がたくさんいるらしく、TLにはb^2=acを指す「等比中項」という用語まで流れてきた。自分にとってはこの判定を(long)b*b==(long)a*cで行わないことが奇妙で不自然。誤差や浮動小数点数に対する感覚の話だから、等比中項を知っているかいないかが問題になるとは思えない。

www.youtube.com

朝から起きており、午後は体を動かして遊んだため、もう眠気が限界に達しつつある。気合いで午後11時半からCF #1035 div.2。

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

書く

www.youtube.com

午前4時半就寝。

07/06(日)

午前10時起床。日記を書いたりラノベを読んだりしていた。

「凡人転生の努力無双」3巻を読了。この巻からカクヨムで読んだ範囲を超える。かなり面白かった。特に主人公の修行パートである前半は、どんどん技術を身に着けていく様子が楽しい。敵の所業があまりにも残酷だったり、グロテスクだったり救いがなさすぎたりするのは、ギリギリ演出の範囲に収まっている……のか？シーンを想像するととんでもないことになっているのがよくある。

午後7時からAHC050に出た。

AtCoder Heuristic Contest 050 - AtCoder

問題を読んだ瞬間に2点swap山登りの実装を開始。1時間で何とか書き上げ、2secで100イテレーションちょっとしか回らないまま提出したら、88431332でボロ負けだった。冷静になるとこの解法は自明すぎる。そこで、初期解を確率の小さいマスから貪欲に選んだものとしてみると、138053483点まで爆増した。

ビジュアライザを見ると、最初は広い空間の真ん中あたりをチェック模様に埋めているようだ。この挙動は納得できるものだが、終盤は問答無用で潰していくことになるため別に良い状況ではない。ただ特に改善するアイディアもなく、そのまま布団に入った。

コンテスト後の感想戦でゲーム「勇者のくせになまいきだ。」のコケ地獄の話がされているのを見て、なんで思いつかなかったんだろうと頭を抱えた。子供のころプレイしていたかなり好きだったゲーム。当然コケ地獄には大変お世話になった。

午後9時半から2時間弱仮眠を取って、CF #1036 combinedに参加。

Dashboard - EPIC Institute of Technology Round Summer 2025 (Codeforces Round 1036, Div. 1 + Div. 2) - Codeforces

書く

www.youtube.com

朝、大家さんからスイカをいただいた。

日記を書いて正午前に就寝。

週記（2025/06/23-2025/06/29）

06/23(月)

今週は基礎論分野、記述集合論の集中講義の週。

午後3時半に無理やり起きた。談話会が午後4時スタートなのでまあ間に合うかなと思いながら外を見たら小雨が降っていてたまげた。地下鉄を使うと絶対に間に合わない。トボトボ家を出ようとしたところで、雨合羽を着て原付に乗るという選択肢があることに気づいた。実際、ギリギリで間に合った。

1時間の談話会。先月の集中講義のそれには全くついていけなかったのに対して、今日はそこそこ分かったのではないかと思う。基礎論が自分にとって馴染みのある分野だから、ということのほかに、いろいろな定義をしっかり話してくれたことも大きい。時間の制約から代わりに命題の証明がほとんどスキップされたが、唯一行われたものはパズルチックで面白かった。

学食で食事したあと、しばらく院生室で雑談していた。同じ階にある男子トイレが非常に臭いと聞き、怖いもの見たさ（嗅ぎたさ？）で行ってみたところ、確かに使い込まれた公衆トイレのようなアンモニア臭がした。トイレ自体は綺麗なだけあってかなり違和感がある。

午後9時過ぎに帰宅し、先週の週記を書いて投稿。午後11時半からECR180に出た。

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

Aはxとyを端点とする区間にaが含まれているか判定。Bは1手以下でできなければ列が単調であるとわかり、このときどれだけ操作してもbeautifulにはならない。Cは二つ決めて三つ目を尺取り＋カウント。

Dは入次数0の頂点と出次数0の頂点を交互に配置することでn-1ペアが達成でき、これが最小。そこから長さ2のパスをちょうど一つだけ作ればよい。次数2の頂点が存在することが必要条件で、また存在すればその二つある部分木のうち片方をflipするとうまくいく。Eは緑でない頂点について、その部分木がすべて同じ色になる。ここから木に対して塗り方を求めるdpを考え、状態と値を入れ替えた。

Fは2回以上のchminが連鎖することで値が更新されればunstable。まずちょうど1回のchminによる値の更新をすべて行っておき、そのあとに0回以上のchminで更新できるかチェックした。全点対間最短距離を求めておけば、クエリ当たりO(n^2+m)となる。

1時間ちょっとで全完して9位。

www.youtube.com

先週末の第六回日本最強プログラマー学生選手権予選について、メールが来たので無事通過できていたようだ。そこでホテルを決めた。当日のスケジュールは昨年からほぼ変化がないので、同じく後泊することにした。土曜開催だった昨年は週末のあり得ないくらい高いホテルに泊まる羽目になったが、今年は日曜開催のためそのあたりの心配はいらない様子。

それでホテルの選択肢が広がり、いろいろ探していたものの、結局昨年と同じホテル「西鉄イン新宿」にするのが距離的に一番良いようだ。朝食に2種類あるうち高めのプランを選択して、ちょっとだけ贅沢。これでも公式が提示している宿泊費よりそこそこ安い。

少しインターンで稼働したあと、いつの間にか布団で寝ていた。スマートウォッチの記録では午前6時過ぎ就寝。

06/24(火)

午前1時半起床。ゆっくりシャワーを浴びて原付で登校した。今日は曇り空だが、雨が降る予報ではない。

午後3時から集中講義一日目。今日も非常に基本的なところから話してくださる丁寧な立ち上がりだったが、気を抜いて少しよそ見しているうちに済まされていた議論が分からず、少し置いて行かれ気味になった。予定していた分が早く終わったとのことで、普通午後6時までのところを午後5時20分には終了。

院生室に移動して、同じ講義に参加していたM1の後輩と共にわからなかった行間を埋めた。何とか解決はしたものの、式を紙やホワイトボードに書かないと追えないような議論になったので、講義中先生がどのように説明されていたのか謎。後輩も覚えていないというから、それだけサラッと話されるべき自然で直観的な説明があり、我々が感覚を掴めていないだけなのだろう。

学食で食事したあと院生室に戻って、友人がChatGPTに書かせているプログラムに口出ししていた。結構な規模のコード群がちゃんと動いていたのでかなり驚き。ただ高速化をお願いしたらバグったらしくて、自分が解決したが、コードのあちこちを見る必要があったからChatGPTにエラーメッセージを投げるだけでは直らなかったのではないか。とりあえず今日は的外れなことを言っていた。

午後10時帰宅。うっかり朝までペンシルパズル「波及効果」に熱中していた。

ラノベの新刊チェックをして29冊注文した。「美少女フィギュアのお医者さんは青春を治せるか」2巻が出ると知って驚き。

午前9時半就寝。

06/25(水)

午後2時起床。

寝る前に注文したばかりのラノベがもう生協の店舗に届いたらしい。早いなんてレベルじゃないので調べてみたら、なんとひと月前にも同じものを注文していたことが判明した！普通は注文時にメッセージが出るが、そのラノベはここひと月の間に商品管理IDが変わったようで、同一商品と認識されなかったようだ。

常に大量の本を買っているし、積読が多すぎて何を買ったかちゃんと覚えていない自分ではあるが、同じ本を複数買ってしまうのは記憶の限り初めてのはず。買った本の記録をつけていても予約注文には無力。発売のかなり前に予約するとこういうことが起こりうる、というのは反省としてちゃんと頭に入れておきたい。

今日は雨が降るらしいので地下鉄で登校し、午後3時から集中講義二日目。講義資料が配布されているとやはりかなり楽で、差分だけ板書している。昨日は結構異なる部分もあったように思うが、今日はかなり資料通りだった。そしてなんと午後5時半に終了。もしかして毎回この時間を目指しているのだろうか？

学食で食事したあと、院生室に行って、先月の集中講義で出ていたレポート課題に取り組んだ。しかし眠気に大敗北。椅子を二つ使って横になっていたら、後輩が帰るときに声をかけてくれて、車で家の近くまで送ってくれた。今年2月にも送ってくれた、今M2の彼で、今週講義を一緒に受けているM1の後輩とは別。

後輩の車で一昨日と同じラーメンを食べに行き、帰りも送ってもらった。

週記（2025/02/03-2025/02/09） - kotatsugameの日記

家にたどり着くと少し目が冴えて、「カードゲームで世界が滅ぶ世界に転生してカードショップを開店したら、周囲から前作主人公だと思われている」2巻を読了。

1巻発売から少し間が開くも無事2巻。面白かった。主人公視点での語りでは主人公自身の特別性がいまいち強調されない。この点はWeb版でたまにあったあとがきが加筆されて補われていたが、ではWeb版ではどうだったかというと、勘の悪い自分は寄せられた感想を読んで追いついていた。

自分が見過ごしていた伏線・小ネタを回収するため、この作品に限らず、最近追っている作品は感想欄も覗いてみることが多くなった。ただ他人の感想を読んで作品の印象ごとそれに引っ張られてしまうことには注意したいと考えている。こうして読んだ本・Web小説について日記にコメントを書いているのも、その対策という意図がある。大したことも書いていないが、自分で言葉にすることに意味があると信じて。

少し日記を書いて午前4時前に就寝。

06/26(木)

午前9時起床。朝の今は天気がいいが、昼過ぎからは雨が降るらしく、地下鉄で登校。

M2の後輩の用事に少し付き合ったあと学食で食事し、集中講義の時間まで図書館で一緒にレポート課題に取り組んだ。M2の後輩も先月の集中講義を受講していたのである。

土砂降りの中移動して午後3時から集中講義三日目。昨日までボレル階層を定義していたが、これが算術的階層と対応することを今日説明なしに使われてびっくりした。単に記号が同じだけだと思っていたら、そういう関係があったのか……。しかし算術的階層にあまり慣れていないため、具体的な論理式を見せてもらわないとどの階層に属するか判断することが難しい。

今日は午後5時40分に終了。10分ずつ遅くなっているが、時間通りと仰っていたので、いったい何時までの講義だと認識されているのか本当にわからなくなった。とはいえ早く終わってくださるのは非常にありがたい。

学食で食事して院生室へと移動。月曜日トイレの臭いについて言及したが、それから徐々に拡散し、今ではトイレから最も離れた院生室の前までどことなく臭い。また上下階への階段も怪しい。すでに事務に連絡は行っているらしいから、近く解決されるだろう。

昨年度立体四目並べに熱中していたメンバーは、うち一人が就職した今も週一回、研究会としてDiscord通話で集まっている。最近は自分が書いたコードをぶん回して中盤の局面を完全解析したり、評価関数のパラメータを機械学習のテクニックで最適化したり、あるいはまったく別でAlphaZeroを実装したりしているようだ。今日はその研究会の日で、自分もちょっと顔を出した。

終電で帰宅。しばらくハーメルンを読み、午前3時半に就寝。

06/27(金)

午前8時半に目を覚ましてうっかりハーメルンを開いた。そのまま4時間ほど読みふけり、昼過ぎにようやく二度寝。追加で2時間しか寝られなかった。

原付で登校して集中講義最終日。順序数の降下列が必ず有限で停止することを、実は知らなかった。考えてみると、極限順序数の「一つ前」を具体的に取るときに何らかの有限性が現れて、それをどれだけ繰り返しても有限になりそう。相変わらず少し早い午後5時50分に終了。

学食で食事したあとM2の後輩と図書館に籠って、レポート課題に取り組んだ。提出は来週月曜日まで。日付が変わるまで格闘し、何とか5題の回答を揃えることができた。

先週の集中講義の課題については、友人が先生と偶然会ったときに聞いてくれたようで、曰く「1日1題以上、全体で5題以上」の演習問題を解いて「06/30までにメールで提出」とのこと。

週記（2025/05/19-2025/05/25） - kotatsugameの日記

コンビニに寄りつつ帰宅。朝までかけてレポートをTeXで清書し、Geminiに投げつけて校正を頼んでおいた。出力を確認するのはまた後日。

布団に転がってハーメルン「Fate Night Unnamed　～チート転生者はデスマーチに挑む（ほぼ強制）」を読了。かなり面白かった。Fateシリーズを全く知らないので話の細かいところはいまいちわからなかったが、それが気にならないくらい主人公が最強で良い。連載開始から二か月経っていないのに年間ランキングの最上位まで上り詰めており、やはりみんな直球の転生チート無双ものが好きなんだなという気持ちになった。

syosetu.org

次いでラノベ「怠惰な悪辱貴族に転生した俺、シナリオをぶっ壊したら規格外の魔力で最凶になった」3巻を読了。ふわふわしたペットを手に入れ、主人公の牙がどんどん抜けていくようだ。一方後半で異世界転生の真相が明かされ、成長した先の主人公の可能性が垣間見れたのは良かった。

生協が開店したので本を受け取ってきた。つつがなく同じ本を2冊手に入れ、途方に暮れた。別にお気に入りのシリーズでもないというのがまた痛い。

午後1時前に就寝。

06/28(土)

午後8時起床。寝ている間にICPC模擬国内予選が行われていた。自分も先週内部コンテストで走ったので、その時の話をしておく。

2025/Practice/模擬国内予選/講評 - ICPC OB/OG の会

まず、結果は3時間でABCDEGの6完だった。もともとFとGがswapされており、6問目のGでドン詰まりしたためそれ以降にあまり時間を残せなかったと言い訳しておきたい。また、Fはもともとサンプルにコーナーケースが置かれておらず、コンテスト終了直後に気づいて通すというなかなか悔しい終わり方だった。HとIは読んだだけ。

Cまでは特に言うことなし。難易度の差もわからない程度だと思った。Dはできると知ってからだと戦略がかなり限られるため考えやすい。Eは伝統的な構文解析だが、ふつう空白区切りとなるところをアンダーバーにしているあたり現代人向けにされている印象。

Gは大変そうな実装方針ばかり思い浮かんで全然解けなかった。最終的には公式解説と同じパターンで数えたものの、対辺を結ぶ線の縦横まで決まることには気づいておらず、90度回転させて2回解いた。部分文字列の一致判定は面倒だったので愚直で許してもらったが、制約強化でもしかしたら落ちるようになっているのかも。まあ文字列アルゴで書き直すのは面倒なだけで難しくはない。

Fも解説通りの解法。O(N^2)のdpにするまでは典型的だが、復元でちょっと詰まった。BCCを除くための3状態のどこから遷移すればいいのかわからないからである。これはあり得る遷移元をすべて持っておくと解決できた。あとは冒頭でも話したようなコーナーケース。内部コンテストでみんな引っかかっていたため、サンプルに追加されたらしい。

食事して、午後9時からABC412。

AtCoder Beginner Contest 412 - AtCoder

Aは問題文を斜め読みしたらA\le B,A\lt B,A\ge B,A\gt Bのどれを数えるのかわからなくて困った。Bはよい。Cはちょっと難しいと思った。迂闊な方針だとコーナーを踏みそうなので、問題文の言い換えなどはせずそのまま実装するように心がけた。Dは何をやっても間に合うだろう。サイクルを一つずつ作っていくbitDPをした。

EはA_{n-1}\lt A_nとなるL\lt n\le Rを数えればよく、そのようなnは素べきである。久しぶりに区間篩を書いた。Fは外にある靴下の色を状態として期待値の連立方程式を立てた。靴下の枚数が多いほうが期待値が小さくなるので、外に残す靴下は常に枚数の多いほう。よってAの降順に求めていくことができる。Gはわからず。

CとFで若干詰まったが、42分6完で15位。Dは順列を全探索するだけでよいとか、サイクルが高々二つしかないとか、楽な実装はいろいろあったようだ。

www.youtube.com

それから寝るまではずっとラノベを読んでいた。

Universal Cupシーズン3のSemifinalsのアナウンスがあった。08/24の午後8時からということで、日本最強プログラマー学生選手権決勝と同日。スケジュール上は懇親会の終わる時間がちょうど午後8時なので、少し早めに抜けてホテルに戻れば問題なく参加できそう。家から出られないのは少し痛いかもしれない。

About the Universal Cup, the Semifinals, and myself... - Codeforces

明日は特にコンテストの予定がない。久しぶりにゲーセンに行きたいなと思いつつ、午後0時半就寝。

06/29(日)

夕方くらいには起きてガッツリ遊ぼうと思い目覚ましをかけていたのだが、意識だけ取り戻してもあまりの眠さに身動きが取れず、結局ゲーセンには行けなかった。そのくせ小刻みに目覚ましで起きたため睡眠も途切れ途切れで、いいとこなし。午後9時起床。

昨日から読んでいたラノベ「悪役令嬢はしゃべりません」4巻を読了した。非常に面白かった。自身が喋れること、魔術を扱えることを少しずつ明かし始めた主人公が戦場で大活躍。またそれからどんどん時が流れ、立太子の儀の直前まで話が進んだ。次の巻からいよいよ、この世界のもととなった乙女ゲームのストーリーが開始するらしい。

しかしこれまでのシリーズ4冊すべて400ページ台後半という文章量で、内容が盛りだくさん。敵味方がそれぞれ謀略を巡らす話なので、ちゃんとストーリーの細部まで覚えておくべきなのだろうが、一気読みした3巻まではともかく今はもうすでに記憶が薄れていっている。

PCに向かって集中講義のレポートを仕上げた。PDFをそのままGeminiに投げると文章を読み取ってくれるが、内部でOCRでもしているのか、特に数学記号が微妙に間違っている。その状態で校正を頼むと読み取りミスに対して修正をしてきて困る。数学的な内容を踏まえてちゃんと直せている点は素晴らしいものの、そもそも間違っていないのだから意味がない。その分文章の間違いが見過ごされているのではないかと心配であった。

朝まで日記を書いていた。午前10時就寝。

週記（2025/06/16-2025/06/22）

06/16(月)

午前11時に気合いで起床。昼から大学で用事があったため登校した。1時間もかからず終了。

院生室に移動してMidnight Code Cupのお土産を設置した。空港で買ったチョコ2種類。ナッツアレルギーの後輩がいるためアレルゲンを含まないものも探し回り、ヴィーガン向けのチョコを見つけて買ってきたのだが、ダークチョコレートであることを見落としており、そちらはかなり苦くて微妙だった。

少しだけボドゲで遊んで帰宅。途中で生協に寄りラノベを受け取ってきた。新刊コーナーに「サイレント・ウィッチ」9巻extraが並んでいてびっくり。それまでの巻を一切置いていないが、いったい誰が買うのだろう。生協が我々の注文とは別に入荷するラノベ新刊は、よくわからないセレクションであることが多い。自分が買った本と同じものが入っていることも頻繁にあり、もしかして参考にされているのでは、とこっそり思っていたりする。

午後3時半からインターン先定例会に出席。セルビアからロストバゲージしつつ帰ってきた報告をした。勉強会は電力メーターなどのメーターの構造について。例えば電力量は「アラゴの円盤」の原理を用いて回転する動きに変換され、それが歯車などの物理的なシステムを通してメーターの表示となるらしい。全部デジタルに処理しているものだと思い込んでいたためびっくりした。

解散後、かなり眠かったので3時間ほど仮眠をとった。起きて先週の週記を書き投稿。それから朝までラノベを読んでいた。

「天嬢天華生徒会プリフェイズ」を読了。読みは「てんじょうてんげ」で、プリフェイズ（prifaes）は作中の造語。タイトル・あらすじといった購入前に確認できる情報や、なんなら口絵を見てもどんな話か全く分からない中で、超巨大な学園を舞台にしていること、著者が「神様のメモ帳」「生徒会探偵キリカ」で有名な杉井光さんだったことのみを手がかりに購入を決めた作品。

読んでみるとしっかり面白かった。それと同時に、確かにあらすじに書けることは少ないなと思った。というのも、主人公が何者で一体何をするのか、ということが1巻全体を通して徐々に明かされていくストーリーだったから。よってここから先の感想はネタバレを含むことに注意しておく。

まず主人公は詐欺の天才。これは杉井光さんの他作品でもよく登場する設定のため、求めていた通りのものが出てきた感じで満足感を得た。ストーリーも人を騙すイベントの繰り返しで進んでいくが、しかし最も大きな詐欺はやはり叙述トリックだろう。これがあるからあらすじに何も書けなかったのだなと納得した。

ちょっとした描写の違和感は最初のころからずっとあったと思う。しかし自分で勝手に文脈を補うと無理のないシーンが想像できたため、あまり気にせず先に進んでいった。真相に気づいたのは8章に入ってからだったと思う。

それでもラストの種明かし前に自力で気づけて嬉しかったが、直後に再読してみたところ、これでなぜ分からなかったのかと思うほど露骨な描写があちこちにあってびっくりした。真相を知った後では些細な単語、句読点、ダッシュの意味がガラリと変わっている。これには感服。実のところ、再読するということが少なくて知らなかっただけで、ほかの叙述トリックの作品でもこういう仕掛けが随所に施されていたのだろう。

午前11時就寝。

06/17(火)

午後8時に目を覚ましたあと、長い間布団でゴロゴロしていた。午後11時半からCF #1032 div.3。

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

Aはよい。Bは|b|=1とする。Cはすべての最大値を一斉にデクリメントできるかチェック。Dはaとbをそれぞれソートしたあと、a_i\lt b_iを満たすようにswapすると条件を満たす。Eは桁dp。Fは\max\le xから\max\lt xを引けばよく、使ってはいけない数で列を区切るとZero-Sum Rangesになる。

Gは01を\pm 1に置き換え、区間和の絶対値の総和を求める。これは典型問題で、累積和を取って値をセグ木のインデックスにすればよい。そこから答えを求めるのは算数。HはLISのdpで、末尾の値に対して長さの最大値を持つタイプのものを考える。不要な箇所で値を大きくするのは無駄なので、末尾の値がl_iのところだけ真面目に区間MAXで計算、他は単にインクリメントでよい。最初にl_iを集めて座圧しておく。

32分で全完して4位。Gでうっかりlong longをlongと書いてしまい1WAしたが、これがなくても順位は変わらなかったようだ。

www.youtube.com

それから、夜中から朝を通り越して昼になるまでずっとセミナー準備をしていた。昼前に学食に行って食事し、午後2時前に就寝。

外はバカみたいに暑かった。夜は夜でそこそこ蒸し暑いが、昼よりはよほどマシである。よって昼夜逆転こそが大正解の生活リズム。ただ、ちゃんと逆転したところで止めておかないと、今日みたいに寝る時間が暑さのピークになってしまう。

06/18(水)

午後8時起床。

セミナー準備がヤバい。そもそも話す予定だった内容の理解が追い付かない。資料を前日までに送信することになっていたが、当然間に合わず、夜中もずっと取り組んでいたのに全く先に進めず、午前8時くらいになってついに諦めた。分かっていないところを分かっていないと書いた資料を、さも前日作ったものを朝起きてから送りました、みたいな顔して送信。

このくらいの時間、外は土砂降りだった。登校するのに原付が使えないなら少し早く起きなければならないな、と憂鬱な気持ちになったが、天気予報を調べるとすぐ晴れるようだったので一安心。

布団に入ってからはなかなか眠る気になれず、ハーメルンを漁っていた。午前11時くらいにようやく就寝。

06/19(木)

午後0時半に気合いで起床。無事晴れていたので原付で登校し、学食で食事した。

今日のメニューは油そば。以前食べたときはただでさえ量の少ないタレが細い中華麺に吸収されきってしまい、味ムラができて美味しくなかった。しかし懲りずに注文してみると今日は美味しかった。盛り付け前に調理スタッフが麺とタレを絡めるのだが、そこが上手だったのではないか。

学食で「にんにく油そば」を食べた。前から気になっていてようやく出会えた期間限定メニューだが、タレが少ないため素の中華麺の味が目立ち、美味しくなかった。

週記（2024/07/01-2024/07/07） - kotatsugameの日記

午後1時半からセミナー。準備は大炎上していたがセミナー自体は和やかに終わった。理解できなかったところを話したら聴衆からいい感じのコメントが来て、雰囲気で計算してみると論文に書いてある内容とほとんど整合してくれた。符号の食い違いだけ残ったので、後でちゃんと整理しなおす。そういうことをしていたため、長引いて3時間ほどかかった。

院生室に移動して雑談。月曜日設置したお土産は順調に減っており、またうれしいことにホワイトボードにお礼のメッセージが残されていた。学食で食事して午後7時前に帰宅。

すぐ眠ればいいものを、なぜか眠気に抗いペンシルパズル「波及効果」と格闘していた。1問に2時間かけたりしていて意味不明。

しばらく日記を書いて午前10時くらいに就寝。

06/20(金)

午後6時起床。気力がなく、布団でYouTubeを眺めて過ごしていた。

ようよう起きだして午後9時20分からyukicoder 471。

yukicoder contest 471 - yukicoder

Aからちょっと悩んだ。バブルソートをする。Bは上のbitから揃えていく。Cは片方の切れ目を固定し、もう片方をデータ構造で処理する。

Dは面白かった。素因数分解できれば、p^a\mid Aとp^c\mid Cについて\lfloor aB/c\rfloorというふうに簡単に計算できる。しかし制約がデカすぎて素因数分解できない。そこで小さいBに対する結果から答えを求めることにする。B=0,1,2,\dotsに対する答えの増分は必ず周期cを持っており、cは十分小さいので、計算可能。

A^{2c}くらいの数もそこそこ桁数が大きいが、A^0から順に求めていくとすれば、Aをかけ、Cで目いっぱい割ったあとはCとの\gcdを取っても次の計算に影響を与えない。これで入力と同じくらいの桁数の数だけ扱う解法が得られた。多倍長整数が必要なためRubyで実装し、出したら通ってFA。後から試したら\gcdを取らなくても普通に間に合った。

Eはdp。a-(a\bmod b)とa-1-((a-1)\bmod b)が異なるのはb\mid aの場合だけなので、毎回そのbだけ列挙して寄与を更新すればよい。

FはSA+LCPを作り、区間を順にチェックしていった。細かい部分だが、prefixを指定したときにそれを含む区間がどれくらいあるかセグ木で取得できるようにするため、後ろから見て区間代入を行った。前からだと代入を戻す操作になってしまう。ちなみにこの問題の強化版がABC280Exで既出だったらしい。その回を見に行ったらG問題でドン詰まりしており、upsolveもしていなかった。

Ex - Substring Sort

Gはクエリ平方分割で通した。距離の取得やsetの操作で\logがついているものの、なんとか3secくらいで通ってくれた。なかなかTLが厳しいなと思っていたら非想定だったようだ。

HはW_1,\dots,W_Nが独立な確率変数でないから一斉に求めなければならないと思い込んでおり、この場合にも期待値の線形性が使えることを完全に忘却していたため、問題に取り組む土俵にすら立てていなかった。

7完3位。

ラノベを読んで午前5時半就寝。

06/21(土)

午前8時半起床。今日は夏至らしい。

午前9時からUniversal Cupに参加した。今日は40回目、Potyczkiセット。これがシーズン3の最終回らしい。チームメイトの都合により通常用意されている中では最も早いウィンドウで走ることになったが、現地チームのゴーストが入っておらず順位表情報がほとんどなくて、なかなか大変だった。

https://qoj.ac/contest/2135

書く

感想戦終了後、午後3時から1時間ちょっとAHC049に参加した。

Toyota Programming Contest 2025#3（AtCoder Heuristic Contest 049） - AtCoder

操作2を真面目に考えるのはかなりつらそうなので、なかったことにする。基本的には遠くにある荷物を拾い、戻ってくる行動を繰り返すこととした。これだけだと芸がなさすぎるので、道中で他の荷物を拾えるなら拾ってくることに。とりあえず帰り道だけ実装して、1617782点が最初の提出。ちょうど全く同じ点数の人がいて面白かった。

帰りに目いっぱい拾ってくるので行きには何も拾えないだろうな、と思いつつそちらもやってみたところ、高々1個だけ拾うとしたコードで1744898点が出た。その1個を重さ最大のものにしたところ少し点数が落ちて、1個ではなく無制限に拾うのを許すと少し改善され、1766150点が出た。ここまででおよそ1時間。

夜のABC+CF combinedに備えて布団に入り、仮眠。午後8時半くらいに起きたら肝心のcombinedがdiv.2オンリーになっていて仰天した。

午後9時からABC411。

UNIQUE VISION Programming Contest 2025 Summer (AtCoder Beginner Contest 411) - AtCoder

A、Bはよい。Cは左右を見て差分更新。Dはやけに難しいなと思いながらtrie木を書いた。EはAをdistinctだと思って全部まとめてソートし、最大値を決め打って数え上げ。0を含む数列の1点更新・全体の積取得が必要になったため、セグ木を持ち出した。

Fは各頂点から生えている辺をsetに入れてマージテク。頂点を縮約する度に辺の行き先もチマチマ書き換えて、常に代表元同士の辺としておくと、多重辺の削除が簡単に行える。しかし各駒が置かれている頂点も同様に管理しないといけないことに気づかず1ペナ。

Gはあらかじめ多重辺をまとめておき、始点・通った頂点集合・今いる点を持つbitDPをすればひとまずO(N^3 2^N)になる。ところがNが一つ少ないと思い込んでしまい深く考えずに実装開始。ただ重複削除と定数倍高速化のつもりで、始点が通った頂点のうち最もラベルの小さい頂点となるように遷移したところ、実はNが一つ落ちる本質的改善になっていたらしく、それに無自覚なまま出したら通った。

34分・1ペナで全完し7位。

www.youtube.com

早々に全完し動画を撮り終えたため、合間にシャワーを浴びる余裕があった。午後11時半からCF #1033 div.2。1問既出だと判明して消え、div.2に降格され、さらに時間が30分短くなったようだ。

Dashboard - Codeforces Round 1033 (Div. 2) and CodeNite 2025 - Codeforces

書く

www.youtube.com

夜中からずっと木曜日のセミナーでの計算を整理していた。教科書で該当するところを探し舐めるように読んだり、ChatGPTに聞いてみたり。教科書からは正確な定義や計算手法を、ChatGPTからはお気持ちを教えてもらえる。それでも理論的なところを分かった気にはあまりなれていないが、正しい計算を行えるようにはなった気がする。

昼前にコンビニに行って菓子パン等を爆買いし、食事。午後1時就寝。

06/22(日)

午後4時半起床。午後5時から3時間、ICPC模擬国内予選の内部コンテストを走っていた。

午後9時からARC201。今日は第六回日本最強プログラマー学生選手権の予選のため、divは設定されていない。

AtCoder Regular Contest 201 - AtCoder

Aは各writerがセットをできるだけ作ったとき、Div.1とDiv.2の数の和は定数になり、またその配分として可能なものは区間になる。これらの値を足し合わせる。細かい部分の算数でやたら時間がかかってしまった。

Bは上のbitから見ようとして大失敗。容量をNでchminしてよいことを使うと思ったが、計算量がO(N^2)になっても間に合わない。正解は下のbitから見ることで、W\bmod 2を埋めたあと二つの品物をペアにすることでサイズの小さい問題に帰着できる。

Cは簡単。良い集合の様子を考えると自然にtrie木が出てきて、S_1,\dots,S_kから構成したtrie木上でdpすれば求まることがわかる。文字列を追加する度、通ったパスの頂点だけdpの差分更新を行えばよい。

Dは大変。Bをソートし、A+BとMとの大小を考えると、最適解において「A+B\lt MとなるprefixとA+B\ge Mとなるsuffixへ分割できる」「prefixのAよりsuffixのAのほうが大きい」「prefixとsuffixそれぞれについて、Aは降順に並んでいる」ことが示せる。よって考えるべきパターンはprefixの長さ\ellとしてN+1通りになった。

ここで二分探索を行うと、Bの各要素についてペアとなれるAの条件が定まり、そこから可能な\ellの条件を計算できる。prefixのほうは緩いのでsuffixに対して真面目に判定することになるが、いずれにせよAとBがソート済みならすべての\ellをチェックするのがO(N)になる。よって二分探索でO(\log M)つけても間に合う。

Eは簡単だが、それ以上に自分が上手かったと自画自賛したい。バウンディングボックスの面積(\max x-\min x)(\max y-\min y)について、\min\bulletを\max{-\bullet}に置き換えつつ展開すると、\max\pm x\times\max\pm yを複合任意で求めて足し合わせることになる。平面走査して\max\pm xを固定し、\max\pm yのほうは遅延セグ木で取得。区間に一斉に値を掛ける操作で更新できる。13分で通した。

Fを読んで双対じゃないかと言っていたらコンテスト終了。5完30位で無事決勝進出。

www.youtube.com

今日も朝まで計算。昨日の理解をもとに再度実行してみるとちゃんと論文と一致する値が出てきた。符号が反転していた原因は、自然に定まるらしい群作用の定義を間違えていたから。常識がないので、ちゃんと言ってくれないとわからなくて困ってしまう。

唐突にハーメルンの日間ランキングを開き、「超有能な幼なじみを堕落させたんだがなんかおかしい」を読んだ。4話で完結済み。道中の雰囲気はかなり好みだったものの、ラストで勘違いしたまま別れそうになったところにはヒヤッとした。結局縒りを戻してからも勘違いしたままだったし、ちょっとスッキリしない気持ち。

syosetu.org

日記を書いて午前10時くらいに布団に入ったあと、眠れず少しラノベを読んでいた。正午過ぎに就寝。

週記（2025/06/09-2025/06/15）

06/09(月)

水曜日までMidnight Code Cupでセルビア旅行。帰国時にロストバゲージした。

06/10(火)

06/11(水)

日付が変わる少し前に帰宅した。

旅行前から読み進めていたハーメルン「転生男の娘は道化の海賊を王にする」を読了。3年前に一度最新話まで読んだあと放置していたため、改めて最初から読み直した。もうエタっているが、原作開始前からスタートして頂上戦争までたどり着いている。

面白かった。主人公がバギーの腹心の部下として海賊団を超強化しており、原作開始前に五皇入りしている。これによる序盤のアレンジ、特にローグタウンでルフィを捉え、逃がす展開が良かった。

syosetu.org

午前8時就寝。なぜかセルビアにいたときより寝るのが遅くなっている。

06/12(木)

午後6時くらいに目を覚ました。今日は夜中にCFがある。夜はずっと布団でハーメルンを読んでおり、午後10時過ぎにうっかり寝落ちしたが、念のためかけておいた目覚ましが功を奏してギリギリで起床できた。

午後11時半からCF #1030 div.2。

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

Aは出現回数を0回にすればよい。Bはrotateがしたい。reverse 3回による実装を思い出してみると、最後の1回、全体のreverseが不要なことに気付ける。Cはaで立っていないbitを集めて貪欲。Dは信号に引っかかるタイミングと移動方向の2n状態で遷移を求め、ループに陥るか見る。Eは中央から縦横交互に長方形領域を拡張していくと通った。おおむね、直前に塗ったマスがチェビシェフ距離最大となるようにする。

Fは辞書順最小を正規形として実験していたが特に何もわからず。Eまで解いて10位。Fで正規形を考えるのは実は外れ方針だったようだ。

www.youtube.com

ハーメルンを読みふけり、午前11時就寝。

06/13(金)

午後5時半起床。布団で転がっていたらホスフィンから夕食に誘われたので、出かけた。

店は「玄米食堂 番」。その名の通り玄米を売りにした店で、二人とも鯖の味噌煮定食を注文した。自分はご飯をお赤飯に変更。鯖は美味しく、また骨が取り除かれていて非常に食べやすかった。お赤飯と鯖の味噌煮を一緒に食べるのが難しいことに気づき急遽玄米ご飯をおかわりしたらフードファイトが始まりかけたが、何とか完食。

食後少し歩いてホスフィンと別れ、本屋に入って4冊購入。それから閉店までゲーセンで遊んだ。新曲埋めで14クレプレイ。

新しく追加されたものと最近通常解禁されたもので、Lv.15が新しく二つプレイできるようになった。「ひつぎとふたご」のほうは全部擦るとすぐSSSを出せた。85小節目が下手くそすぎたのでもうちょっと伸びると思う。「リ・フィクション・O」はラストが無理すぎる。非常に苦しい。

ドンキに寄って、日付が変わってから帰宅。それからハーメルンを読みふけって正午くらいにようやく寝た。

06/14(土)

午後6時起床。布団でハーメルンを読んでいた。午後9時からABC410。

AtCoder Beginner Contest 410 - AtCoder

A、Bはよい。Cは配列のオフセットを管理。DはN\times 2^{10}状態でBFS。Eは消費体力・魔力に対して何番目のモンスターまで倒せるか持つdp。

Fは適当に転地してH\le Wとしておき、長方形領域の上下を決め打つと、横方向でZero-Sum Rangesをすることになる。値の範囲が-HWからHWであることから出現頻度を配列で管理することができ、O(HW\sqrt{HW})を達成できる。

Gは弦の削除操作を不要なものと勘違いして一度コードを書ききってしまい、かなり時間がかかった。円を適当に切り開くと、弦の両端点それぞれにおいて、重なる弦は入れ子の区間になっている。つまり逆に、入れ子になっている区間の集まりをdisjointに二つまで選べば、それと交わる弦が構成できる。prefixとsuffixそれぞれで入れ子になった区間の数の最大値を求めることができ、組み合わせれば答えが求まる。

38分で全完して11位。このうちおよそ半分の時間をGに消費している。

www.youtube.com

一昨日から読んでいたハーメルン「アイドルの世界に転生したようです。」を読了。昔から好きな作品だが週刊連載で進みが遅く、3年ほど放置していた模様。一念発起して読んでみると、その150話くらいでちょうど第八章から第九章までだったらしい。続き物の章だったこともあり、非常にタイミングが良かった。

内容もとても面白かった。もともと外伝『Days of Glory!!』としてオリ主たちのライブシーンが存在したが、これはあくまで外伝扱いで、本編ではなかったことに。それが、より大規模なライブが企画され、第八章はその準備、第九章は全編ライブの話になっていた。このあたりを一気読みできたのは本当に最高。

この作品はアイドルマスターシリーズ全体の二次創作としてかなり長い間連載されており、連載開始後に展開が開始されたブランドももれなく話に登場している。最近は学園アイドルマスターが有名だが、これもいずれ扱われるものと思うと今から楽しみ。

syosetu.org

東北大学からICPCに出場するチームが決定した。今年のコーチは自分と仮の人さんが担当する。割り振りを仮の人さんに決めてもらったので、担当するチームをICPCのサイトで作成した。今年は大学全体で7チーム、自分は3チーム受け持つ。

朝まで日記を書いたあと、ラノベ「二度目はタの付く自由業」を読了。

サブタイトルから装備と知識がチートなことは分かっていたが、読んでみるとジョブもスキルもチート。しかし天下御免の力を持ちながらもやたら慎重に強くなったり社会的立場を構築したりしており、その様子は楽しめた。ただ終盤の、ヒロインにちょっかいをかけてきた悪役を煽って決闘に持ち込みコテンパンにする展開は好きではない。主人公が理論武装しても相手の頭が悪いのを強調しているだけに見えていたたまれなくなってしまうことが、この作品に限らず多い。

寝る前に宅配便が届いて、何事かと思ったら自分のスーツケースだった。見つかったとの連絡自体は帰国翌日に受け取っていたが、そこから仙台まで運ばれてくるのにさらに二日ちょっとかかったことになる。これが行きで起こっていたら大変だった。ちなみにスーツケースは特に梱包などされず、持ち手にタグが結ばれただけの状態。まあそういうものか。

午前11時就寝。

06/15(日)

午後5時半起床。食事して、今日は午後6時からCF #1031 div.2。

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

Aはxやyの小さいほうを優先して使う。Bは縦または横のずれがシートのサイズの倍数になっているかチェック。サンプルが優しい。Cは2回目以降の爆破を必ず金を巻き込まないように行えるため、最初の爆破で消えてしまう金の数を最小化すればよい。

Dは自分がk回以上勝てる場合、相手の出すカードはb_1,\dots,b_{n-k+1}のどれか。このうちの最小値に勝てるカードのみで、自分の山札の上からk枚を固められればよい。このことをすべてのkについて判定した。二分探索すればもう少し簡単。

Eはかなり大変。答えは存在するなら2n以下なので、それまで毎秒どの頂点にいられるかを管理したい。当然、毎回全頂点から遷移していては間に合わないが、更新される部分をうまく取り出せばO(nm)になるというのがポイント。なぜなら敵によって邪魔されるのは各頂点高々m回だから。変なところでO(\mathrm{deg})かけたりしないよう慎重に実装したら通った。

Fは簡単。唐突に辺a\rightarrow bとしてグラフに言い換えてみる。すると、適切に辺の向きを切り替えて、入次数が正の頂点数と出次数が正の頂点数の和を最大化する問題となった。特に次数2以上の頂点が入る辺と出る辺を両方持つようにできれば最大値であり、これは次数1の頂点やサイクルに含まれる頂点を根としたdfs木に沿って向き付けることで達成できる。

1時間半で全完して3位。

www.youtube.com

続いて午後9時からARC200 div.2。

AtCoder Regular Contest 200 (Div. 2) - AtCoder

A問題から大変苦労してしまった。二つのベクトルが平行でなければ構成できるはずで、そのとき特にN=2のケースを解ければ十分。ところがどうしてもA_1B_1のような値を使用したくなってしまい、Xの値の範囲に合わなかった。

しかしこの制約は内積がオーバーフローしないためのもののはずなので、いくら何でもこれのせいで構築できないケースがあるとは思えない。冷静になってもう一度式を確認すると、二つの有理数の間にある有理数を構成すればよいことに気づいた。これはABC408Gでも見たやつで、分母と分子をそれぞれ足したものが適する。

これになかなか気づけないのはさすがに意味不明。図形的には、二つのベクトルの「間」にあるようなベクトルを90度回転させることで、それぞれとなす角を鋭角と鈍角にできるが、そのようなベクトルとして二つのベクトルの和が適するという話にもなる。

Bは適当に決めていったらできた。\max(A_1,A_2)\le A_3\le A_1+A_2が必要条件。\operatorname{lcm}(X_1,X_2)/X_2は「掛けるとA_2桁がA_3桁になる数」なので、10^{A_3-A_2}-1としたい。X_1はこれと10^{A_1+A_2-A_3}の積にすればA_1桁になる。\gcd(X_1,X_2)=10^{A_1+A_2-A_3}よりX_2=10^{A_1+A_2-A_3}\times(10^{A_3-A_1}-2)としてみる。

これで全パターンチェックしたところ、A_2=A_3のケースだけ落ちたので、それは10のべき乗で自明な構築を与えておいた。

Cは区間の包含関係とPの大小関係を整合させれば不満度の和が最小になる。辞書順最小化のためまずP_1の最小化を考えると、区間[L_1,R_1]に含まれる人に優先して左の席を割り当てることになるが、これは一部の人を抜き出して同じ形の問題を解いているだけ。残りの人も同様なので、あとは再帰的に解ける。

毎回ソートしていてもO(N^2\log N)で、制約がO(N^3)を想定していそうだから見落としがないか心配になったが、出したら普通に通った。

Dは実験。K=Mは自明、K=2はMが偶数のときのみで\{0,M/2\}、K=4はMが4の倍数のときのみで\{0,M/4,M/2,3M/4\}。残りはなんとMの値によらず同一のAで構築できる。実際、\{0,\dots,(K-1)/2\}で0,\dots,K-1が、\{0,\dots,K/2-2,K/2\}で0,\dots,K-2,Kが作れる。

Eは全体にA_1をXORすることを考え、A_1=0として解く。このとき他の数のpopcountは2以下になるので、それらを頂点や辺だと思ってグラフ的にパターンを考えてみた。すると「頂点のみ」「ウニグラフとその中心」「三角形の辺のみ」「1辺と両端点」しかないことが判明。あとは重複がないよう丁寧に数えるとサンプルが合った。

しかしMが巨大なことを見落とし、うっかり\binom{M}{2}などにライブラリを持ち出した結果、痛恨の1ペナ。ここまでノーペナで進めてきたためかなり残念だった。

A問題に30分かけたときはどうなることかと思ったが、残りは順調に進み、100分1ペナで全完して7位。結局5問の中でA問題に一番時間がかかっていた。

www.youtube.com

動画を見たりペンシルパズルに熱中したりしていたら朝になっていた。シャワーを浴びて午前9時就寝。