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月たくさん読んだ反動というわけではないつもりだが、上旬は旅行中を含めてハーメルンに熱中、帰ってきてからはペンシルパズルに熱中してしまった。

6月の集計
買った：23冊
読んだ：5冊
積読：+18冊
積読（累積）：+90冊
— こたつがめ (@kotatsugame_t) 2025年7月1日

それからはずっとセミナー準備をしていた。昼前になって少し大学生協に行き、食事。ほどほどのところで寝ないと夜の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時過ぎに登校した。とはいえ会場の設営はすでに終了しており、特にすることがない。自分のアイコンを掲示してよいか聞かれたので許可を出したり、コンテスト開始直後の問題文印刷・配布について監督員の先生と打ち合わせをしたりしていた。監督員向けの問題文リンクが存在するらしいので、そちらから印刷をかける。

必勝祈願 https://t.co/YcEgERI42U pic.twitter.com/XHR2a3Okm8
— nonon (@nonon_kyopro) 2025年7月4日

午後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名）で打ち上げに向かった。誰も店の候補を挙げられず、しばらく駅でたむろしてスマホを触る謎の時間が発生したが、結局は去年と同じ居酒屋「いただきコッコちゃん」に入った。

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

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

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

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

07/05(土)

午前7時起床。

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

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

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

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

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

Imperishable Night 2006 (2016 Refine) AJ pic.twitter.com/elkxbExoln
— こたつがめ (@kotatsugame_t) 2025年7月5日

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

これって常識ですか？ pic.twitter.com/St3L5iYQcq
— こたつがめ (@kotatsugame_t) 2025年7月5日

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

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

午後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

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

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

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