05/26(月)

午後3時過ぎ起床。

半からインターン先定例会に出席した。昨日寝る前に進捗を産もうとして少し調査したところ、最近考えていたことが全然的外れだったことが判明したため、そのことを報告した。勉強会はポテンシャル付きUFの話。ポテンシャルというと頂点重みが想像されるが、実際は有向辺に作用が乗っていることを意識したほうがよい。昔は前者ばかり考えていて、向きで大変混乱した記憶がある。

先週、さらに学振に追われて書けていなかった先々週の週記も仕上げて投稿し、午後11時半からCF #1027 div.3に出た。

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

Aは $(0,\sqrt s)$ でよい。Bは $s_i\ne s_{n-i+1}$ とするために0と1を1文字ずつ使う必要があることに注目する。Cは先頭から貪欲に、直前に選んだ要素より2以上大きな要素を選んでいくのが最適。Dは動かす候補が $x$ 座標最小・最大と $y$ 座標最小・最大の高々四つ。残り $n-1$ 点のbounding boxのサイズが $n-1$ になるケースに注意。

Eは根までの交代和を累積和のように見立てれば解ける。頂点の深さの偶奇には注意。Fは $x\rightarrow\gcd(x,y)\rightarrow y$ とすべきで、約数を全列挙してdpしても十分高速。Gはどこかの要素を中心として、その左右を一つずつ作っていくことになる。普通 $2^a\times b$ という数は $2^a$ 手かけて作れるが、隣に $a'\lt a$ なる $2^{a'}\times b$ がすでに存在する場合は $2^{a'+1}-1$ 手損する。損する分を勘違いして1WA。

52分で全完し6位。

www.youtube.com

午前2時就寝。

05/27(火)

午前8時起床。今日はラノベを三冊読んだ。

一冊目、「無双ゲーに転生したと思ったら、どうやらここはハードな鬱ゲーだったらしい」。非常に面白かった。敵に対して暴力的で容赦のない主人公が最高。人類のことを家畜だと見下し悪辣な所業に及ぶ魔族を、それを上回る凶悪さで蹂躙していく様が爽快だった。実力を隠した主人公のことをただの少女だと思い、正体も見抜けず侮ったまま何か算段をつけている魔族が滑稽でたまらない。

二冊目、「前世は冷酷皇帝、今世は幼女」2巻。主人公の知略・威風による格好良さは相変わらずだが、前世から従ってくれた部下と改めて友人になる一連のストーリーはあんまり合わなかった。ちょっと部下のことを振り回しすぎに見えるし、そうして振り回されてくれる根底にはやはり主人公との主従関係があるように思えてしまう。

三冊目、「娼館の乙女」。推理小説という話だったので、あらすじから安楽椅子探偵みたいな感じを想定していたが、全然違った。かなり活動的でいろいろ事件に首を突っ込むし、そのまま政界入りしたり依頼者と恋に落ちたりするので、話の本題は推理ではなかったように見える。

午後8時就寝。

05/28(水)

午前3時半起床。

「間取りと妄想」を読んだ。特徴的な部屋とそこに暮らす人に関する掌編の詰め合わせ。パッケージを見てもどんな話か全く分からず買ったのだが、読み終えた今もよくわかっていない。アッと驚くような劇的なことは一切なく、晴れやかだったり妖しげだったりする雰囲気だけが漂っていたように思う。

昼前まで日記を書き、シャワーを浴びて外出。学食で食事したあとゲーセンに向かった。

今日は夕食を挟んで閉店まで30クレ＋20クレプレイ。新曲を埋め、さらにLv.14の未99AJを17譜面減らした。残り62譜面なので先は長い。疲労・眠気から食後は精度がボロボロになってしまい、99AJを出すのに苦労したり出ても納得のいかない失点をしていたりと、正直日を改めるべきだったとは思う。

新曲の出来はかなり良い。まずLv.15の「超最終鬼畜妹フランドール・S」をAJ。ラストは非交差運指で取ったが、交差してもAJ通過したことは何度かあるし、単に噛み合い待ちだっただけだと思っている。0-1を5回出した。

さらにLv.14「Help me, ERINNNNNN!!」の理論値も無理なく出せた。Lv.15「I Wanna」は二回目で4-1となり、そこから伸びる気がしなかったので以降は触らなかった。これら新曲枠でレートがかなり盛られ、今日だけで17.13から17.18に上がったのはちょっとしょうもなく感じる。

今日は50クレ（！） pic.twitter.com/HjZkpKlfYa
— こたつがめ (@kotatsugame_t) 2025年5月28日

夕食はゲーセン近くの「カフェミスティー」という食堂へ。店頭のメニューを見て唐揚げ定食を頼もうと思い入店したが、改めてメニューを確認したらペペロンチーノを発見し、思わず注文していた。デザートはクリームソーダ。赤・青・緑の三色から選べたので、赤コーダーとして赤を選択した。

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

ドンキに寄って帰宅し、午前1時就寝。

05/29(木)

午前8時半起床。

7月下旬の国際会議「FPSAC」に向けてホテルと飛行機を取った。もともと4月初め、スケジュールがまだ出ていないときに一回ホテルを探したのだが、すでに以下のような状況で、とりあえず月曜日から金曜日まで4連泊を取っておいたのだった。

7月というかなり先の日程だからホテルもスカスカだろうと思っていたのに、東横インで調べたらもう埋まりかけでひっくり返った。
週記（2025/03/31-2025/04/06） - kotatsugameの日記

いざスケジュールが出てみると、五日間毎日朝から夕方まで講演が予定されており、前泊は必須の様子。何かの間違いで同じホテルに日曜夜も泊まれるようにならないかと淡い期待を抱いていたが、当然そんなこともなく、このままでは連泊どころか宿泊すら怪しくなってきたため、今日慌てて調べなおした。

結局隣のホテルの素泊まりを、ほかの日の倍する値段で取った。幸い飛行機の最終便が遅めの時間にあるため後泊は必要なさそう。日曜昼に行って金曜夜に帰ってくることにした。飛行機の値段も3月使ったものより若干高くて残念。

昼過ぎに学食に行き、ついでにMidnight Code Cupのため空港へ行く新幹線を取った。いよいよ来週。

最近Daily Akariというパズルサイトが話題である。パズル自体は美術館という名前で知られているものと同一だが、サイトのデザインが美しく、操作が楽しく、解くまでにかかった時間や精度を表示でき、さらに毎日一問出題される点が優れている。規模は異なれどWordleが流行したときと同じ雰囲気を感じている。

dailyakari.com

精度というのは、唯一解と異なるライトを配置したときに減点される値であり、どれだけ理詰めで解けたかの指標となる。自分がこのサイトで遊び始めたころは適当にdfsを繰り返して解いていたため、ひどい値を叩き出したものだが、典型を一通り学んで過去問で腕を磨いたところ、コンスタントにPerfect、つまり完全理詰めで解けるようになってきた。

ところが05/25出題のNo.140は他と一線を画す難しさであり、当日は手も足も出ず、昔ながらのdfsで解かざるを得なかった。この問題の理詰め解法についてツイートが流れてきた。

https://dailyakari.com/archive/140

数日前の激ヤバDaily Akariの理詰めを理解した。(正攻法なのかわからんけど)
明かりの総数が12個で数字の合計が20なので、一つしか数字を減らさない明かりは4つしか使えない。グラフととらえると、端付近の頂点だけでどうしても4つくらい使ってしまうので、他で無駄を出さないようにすると解ける。
— cled0328 (@cled0328) 2025年5月29日

盤面の数字の和と行・列の配置から、各行各列に一つずつライトを配置し、さらに端以外の行・列のライトは二つの数字に隣接している必要があることがわかる。するとすべてが簡単に確定していくようだ。こうやって盤面全体の情報を扱う解法はまったくの初見。ペンシルパズル典型はたいてい局所的な観察だけで攻めていくものと思っているので、そういう意味でも新しい手法だと感じた。

布団に戻ってラノベ「二度目の勇者に仲間はいらない」を読了。過去に飛ばされた主人公が一周目の知識で強くなり無双する話。仲間を失った辛い経験から二周目では仲間を作らないように行動している。勇者だとバレるとパーティーを作られてしまうため正体を隠しており、それが少しだけ勘付かれるのはちょうど良い塩梅だった。ただ最後の最後に仲間ができてしまったのには正直がっかり。まあ表紙イラストの時点で約束された展開か……。

午後11時就寝。

05/30(金)

午前7時半起床。

ラノベ「後方師匠面したい系転生者」を読了。勘違いもの。主人公視点と第三者からの視点が交互にある構成はよかった。相変わらず自分の実力を過小評価するタイプの主人公に対してモヤモヤするのは止められないが、師匠という立場があるからか謙遜する様子があまりなかったので、そこまで気にならなかった。

二度寝して起きたら午後4時だった。シャワーを浴びて学食に向かうと、建物をはみ出すどころか講義棟まで届かんばかりの長蛇の列が形成されていて仰天。何やら今日は100円夕食というイベントを行っているようだ。吉野家コピペみたいな気持ちになった。

学食で食事するのは諦め、購買でラノベを受け取るとともにパンを買い込み、その後散髪。帰るときには建物の外の列は消えていたものの、学食を覗いてみたら蛇腹折りになった行列がまだギッシリ詰まっていた。

少し前から大学生限定でGoogle AI Proが15か月間無料になっている。これに申し込んでみた。というのも、Midnight Code Cupで生成AIを活用したいからである。ChatGPTに課金しようと考えていたが、Geminiが無料で使えるならそれで良いだろう。

gemini.google

少しAHC048に取り組んだ。

MC Digital Programming Contest 2025 (AtCoder Heuristic Contest 048) - AtCoder

セミナー準備をして午前3時半就寝。

05/31(土)

午前10時過ぎに目を覚まし、昼まで布団でゴロゴロしていた。

久しぶりに休日の学食にでも行ってみようかと家を出たが、天気は土砂降りだし、サークル活動をしている学生で結構混みあっているし、そもそも学食の昼メニューにはあまり良いものがない。昨日みたいに購買のパンで済ませるべきだった。

帰宅して「才女のお世話」10巻を読了。選挙戦後編。かなり面白かった。会長に立候補したヒロイン二人を主人公が同時に支えるという無理のありそうな展開もきれいに回収された。また、この巻において卑劣な手を交えつつ主人公陣営を苦境に陥れた前生徒会長に対し、主人公が無自覚ながら格の違いを見せつけるラストシーンは最高にゾクゾクした。

しばらくセミナー準備をして、午後9時からABC408に出た。

AtCoder Beginner Contest 408 - AtCoder

Aは $T_0=0$ に注意。Bはよい。Cはimos法。Dは1がなす区間の候補を全探索する。Eは答えの初期値を $2^{30}-1$ として、上位bitから削っていく。判定はUF。Fは $H_i$ の昇順にdpを行う。遷移は $H_j\le H_i-D$ を満たす $j$ だけセグ木に乗せて区間MAX取得。

Gは方針を完全に間違えてしまった。 $\lfloor Aq/B\rfloor+1\le\lceil Cq/D\rceil-1$ を満たす最小の $q$ を求める問題だと思うと、もともと $\lfloor Aq/B\rfloor+1\le\lceil Cq/D\rceil$ ではあるから、 $\lceil Cq/D\rceil-\lfloor Aq/B\rfloor-1$ の $q=1$ からの和を見ることで二分探索が可能。よってfloor_sumを使うと $\log$ 二つで解ける。

ところがこの $\log$ というのは $\log\max(A,B,C,D)$ のことなので、全然間に合わない。高速化できそうなところもなく、コードテストで10sec以上かかるのを見て絶望しているうち、Stern-Brocot treeのことを思い出した。頂点を区間だと思い、 $A/B$ と $C/D$ を両方含む間降りていくと、最後の頂点の分母が答えになる。

残り20分もないのにフルスクラッチで実装するのは難しそうだな、と思いながら急いで書いてみたところ、なんと4分で実装が終了。サンプルも合って、投げるとそのままACした。全完107位。Fまで解いた時点では2位だったので、かなり苦しい結果となった。

www.youtube.com

午後11時半からCF #1028 div.1。

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

Aはすべて $\gcd(a)$ にするしかない。一つ $\gcd(a)$ を作るまでの最短手数は $O(n\max a)$ のdpで求まる。最初から $\gcd(a)$ が複数あるケースに注意。

Bはこのタイプの問題には珍しく、前から考えて解いた。どんな操作をしても得られる値は $a$ のうちいくつかのMINなので、必要条件として $a_i\ge c_j$ みたいなものがたくさん得られる。これを $i$ ごとにまとめ、 $a_i$ をいくつかの $c_j$ のMAXとして定めてチェックしたい。ここで満を持して後ろから見ると、 $c_z$ で $c_x$ 、 $c_y$ をchmaxしつつ $c_z\leftarrow 0$ とすることで計算できる。

Cは自然なdpが $O(nm(\max h)^2)$ かかる。ここで単体攻撃を少なくとも $\sum h_i-n\times\min h_i$ 回行う必要があることに注目すると、それ以前は単体攻撃をスキップしないため状態数 $O(nm\max h)$ 、それ以降は残りHPの総和だけ見ていればよいから状態数同じく $O(nm\max h)$ となって間に合う。

Dはほとんどエスパー。常に $a_i$ をXORすることとして、 $A_i:=a_i\oplus b_i$ をXORするかしないか選ぶ問題だと考える。実は $A$ を逆順に見てnoshi基底を取り、対応する手番のプレイヤーが最大化を目指すのか最小化を目指すのかに応じてXORするかを決めると答えになる。noshi基底が最上位bitに注目した基底であることがポイント。

説明を試みると次のようになった：最後に操作する人は $A_n$ の最上位bitを自由に制御できる。そこで $n-1$ ラウンド目までの $A_i$ に適宜 $A_n$ をXORすることで、 $A_n$ の最上位bitがほかに出現しないようにしてみる。この操作で答えは変わらない、なぜなら最後の人が相変わらず $A_n$ の寄与を自由に決められるから。あとは同じことを繰り返すと、noshi基底と同じ操作になる。

4完35位で2828→2885(+57)。

www.youtube.com

ECR178の動画の処理がひと月経っても終わらないため、業を煮やして再アップロードした。元の動画も限定公開として残してある。

今回の動画はYouTube上での処理が終わっていない。
週記（2025/04/28-2025/05/04） - kotatsugameの日記

午前4時就寝。

06/01(日)

午前10時起床。

5月の読書記録をツイートした。かなり頑張って本を読んだものの、それを上回る量買ってしまったので積読はそこそこ増えた。多分6月はそんなに買わないはず。といっても読む量も少なくなりそう。

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

4月頭のTeza Round 1（CF #1015 combined）の賞品としてTシャツが届いた。この回の出来は良くなかったが、ランダム配布に当たったらしい。

Tシャツ pic.twitter.com/IQWZglFSmz
— こたつがめ (@kotatsugame_t) 2025年6月1日

ハーメルンの読み返しをしたり二度寝をしたりしていたら午後8時過ぎ。食事して、午後9時からARC199 div.1に出た。今日のwriterは東北大学の雄、とりゐさん。TUPCの準備もあったろうに、どこから問題を生やしてきたのか結構気になる。

AtCoder Regular Contest 199 (Div. 1) - AtCoder

Aは制約の $N/4$ が気になる。 $N$ 列を四グループに分けるのではないかと思って、適当に2行 $i,$ 、 $j$ を固定し、四通りの $(A_{i,k},A_{j,k})$ をカウントしてみた。すると $A_{i,k}\ne A_{j,k}$ なる $k$ が $R_i+R_j$ 個より多くある場合不可能であることが判明。適切な方法で $i$ 行目の行和を $R_i$ にすると、 $j$ 行目の行和を減らせなくなることを観察して示した。振り返ってみると当たり前かも。

今 $R_i+R_j\lt N/2$ なので、 $X_i$ をfixすると $X_j$ が高々一通りしかないことになる。これを使うと $X$ が高々二通りになり、 $Y$ は自然に定まるため、最後にチェックして答えが得られる。実は $X_1=0$ と固定してもよいのだが気づかなかった。

Bはインデックスの部分集合 $S$ を取り、 $A_1=\bigoplus_{i\in S}A_i$ とできるか実験してみた。結果は $S=\{1,3,5,\dots\},\{2,4,6,\dots\}$ 以外できるようだ。この二つができないのは明らかなので、そうでないときの構築を考える。

条件は $i,i+1\in S$ または $i,i+1\notin S$ となる $i$ が存在することなので、これに注目する。 $S$ を01文字列にすると00または11があればよい。そして操作は11を01または10にすることに加え、 $A_i\oplus A_{i+1}$ を2回XORすると消えるので、00を11にすることもできる。

いったん $N-1,N\in S$ とし、そこからどんどん左に寄せて最終的に $S=\{1\}$ とすることを目指すと、かなり簡単に構成できた。最後に $\bigoplus_{i\in S}A_i=K$ となる $S$ を決める際は、noshi基底を使って解空間を求め、 $\{1,3,5,\dots\}$ と $\{2,4,6,\dots\}$ を回避するために高々三つ試した。

ここまでは調子が良かったものの、Cで最初に張る辺に注目すると複雑になりすぎて全然解けず。2完29位、パフォーマンス2991でレートは2872→2885(+13)。AGCと比べあまりにもしょっぱいパフォーマンスに愕然としてしまう。

コンテストが終わったあともCと格闘し、40分後に通した。根を固定すると、すべての部分木がどの円周上でも区間をなしていなければならないという、かなり強い制約が課される。辺だと2端点のどちらに接続するか決めるところで収集が付かなくなってしまったが、それ以外の部分の構成が先述の通りにかなり綺麗にまとまることには気づいていたのだから、根が重要だと感づいてもよかったのではないかと反省。

www.youtube.com

ハーメルンを読んでいるうち眠くなってきて、午前4時くらいに寝てしまった。今日読み返していたのは「闇の正義スパンダム」。

syosetu.org