01/01(月)

午前10時に親に起こされた。家族はみんなすでに朝食を終えたらしく、一人でお雑煮とおせちを食べた。すぐ着替えて初詣に出発。

今年の神社は雪がまったく積もっておらず新年という感じがしない。普段は駐車場の端に雪が山盛りになっていて車は2列で駐められているのだが、今年はなんと3列形成されていた。また出店が1店しか出ておらず寂しい感じ。

初詣　今年雪全然ないね pic.twitter.com/kUjqDBGRaH
— こたつがめ (@kotatsugame_t) 2024年1月1日

昼食を摂って午後3時頃帰宅。両親は買い物に出かけ、自分含む残った3人はこたつで昼寝の体勢に入った。

午後4時過ぎ、地震発生。前震からそこそこ大きかった。TLに流れてきたNERVのツイートで能登のほうが震源と知り、そりゃこれくらい揺れるわと思いながら再度横になりつつとりあえずツイート。送信ボタンを押すと同時に本震が来た。

富山でこんなデカいの珍しいね〜
— こたつがめ (@kotatsugame_t) 2024年1月1日

【地震 16:10】
［震度６強］能登地方
［震度６弱］新潟中越
［震度５強］新潟上越、新潟下越、佐渡地方、富山東部、富山西部、加賀地方、嶺北地方
［震度５弱］長野北部、飛騨地方
［震度４］会津、群馬北部、長野中部、長野南部、美濃東部、美濃中西部
［震度３］栃木北部
— 特務機関NERV (@UN_NERV) 2024年1月1日

どころの話ではないんだが？
— こたつがめ (@kotatsugame_t) 2024年1月1日

本震の揺れは自分が過去経験した中で最大だったように思う。震度だけで見れば2022年福島県沖地震が記憶に新しいし、富山県でも2007年能登半島地震があったが、今回は揺れている時間が非常に長かった。

最初はこたつの中で固まっていたが、次第に家具もグラグラしてきたためリビングのほうぼうに散ってテレビを押さえたりしていた。リビングの高い位置には物がないため多少は安全。ただキッチンの方まで行くのは、戸棚に地震を検知してロックがかかるシステムが導入されていたとはいえ危険行為だった。

揺れのピークが過ぎた後、まだ多少揺れている中を暖房器具の電源を落としたり、他の部屋を確認したり、玄関扉を開け放ったりして回った。幸い何も壊れていないようだし、棚から落ちたものもほとんどなくて一安心。上の14分のツイートは確かこのタイミングで行ったはず。

テレビを付けると富山県に津波警報が出ていた。実家はそこそこ海の近くなのでまずい。アナウンサーの緊迫した声に焦燥感を煽られ、3人で避難しようと決め荷物を持ったが、ここで問題発生。どこに逃げれば良いかがわからない。市のハザードマップを確認すると徒歩圏内にいくつか避難場所が定められているものの、どれも家より海側にあるのだ。

1/3【津波情報 2024年01月01日 16:12】
津波警報を発表しました。ただちに避難してください。

《津波警報》
［新潟県上中下越］津波到達中と推測
［佐渡］津波到達中と推測
［富山県］津波到達中と推測
［石川県能登］津波到達中と推測
［石川県加賀］17時0分
— 特務機関NERV (@UN_NERV) 2024年1月1日

まごついているうちに外出していた両親と通話が繋がった。あと10分ほどで帰宅するので待つように、とのこと。津波＋車＋避難といえば渋滞なのでそれを心配したが、家の方向に向かう分には大丈夫だったらしい。4時半くらいに合流した。

町内会長などまとめ役を務めているから家にいなければならない、という父だけ置いて、母と4人で山の方にある春に亡くなった祖母の家に向かった。そちらに向かう人はやはり多いようで途中から道が渋滞していたが、そこはこのあたりで生まれ育った母のこと、裏道からスイスイ行ってなんの問題もなく到着。積雪がなくて良かったねという話をした。道中見えた被害は石灯篭の上の部分が道路に落ちていただけだった。

残念ながらここまで来ても標高は実家とあまり変わっていない気がする。富山平野は進んでも進んでも真っ平ら。高いところに逃げろという指示には従いようがなかった。途中立体交差している道路に人が鈴なりになっているのを見て、そこに逃げるのは頭がいいなと思った。

祖母宅は、無人となって8ヶ月経つとはいえ電気・水道がまだ維持されており、過ごせる環境にある。ここで1時間ほど待機した。古い様式の家なのでふすまが多く、余震のたびにガタガタ言ってなかなか怖い。また土壁の端が剥がれて粉が落ちてきていた。もしかしてヤバかったか？

午後6時くらいに一段落ついたと判断して実家に戻った。山道はまだ車だらけのようで、ライトが列をなしていてなかなかきれいだった。以上が自分の避難行動の一部始終である。

振り返りを少ししておきたい。今日の行動は……最悪もいいところだった。立山信仰というのは根深くて、自分も東日本大震災の頃小学校で友人たちと「富山は揺れない」と囁き交わしていた記憶がある。アナウンサーの声がなければ一時的な避難すらしなかったと思う。後で確認したら自宅は海岸線から1kmも離れていなかったから、津波警報通り3mの津波が来たとしたらひとたまりもなかったのではないか。

ツイッターでも避難しようとしない親と揉めた人が散見されたが、これはどうしようもない気がする。津波で酷い目に遭った歴史が富山県にはほとんど、あるいはいっそ一切、存在しないからだ。「ここに津波は来ない」という考え方が前提になってしまっている。それでも、自分が祖母宅から戻ってきたとき車がなくなっている家が数軒あったから、避難する人もちゃんといるらしい。

午後6時過ぎに家にたどり着いてから1時間ほど寝て、夕食。今日はしゃぶしゃぶだった。わざわざ今日やらなくても……という気もしたが、早く肉を消費する必要があったらしい。

午後9時くらいまではこたつでゴロゴロしていた。見ていたチャンネルでは午後9時に緊急放送が終わって通常のテレビ番組が再開した。自分もそのあたりから先週の週記を書き始め、日付が変わる前になんとか投稿。相変わらず穴開きがいっぱいある。

入浴してからまた日記執筆。記憶が薄れないうちに、と先週の穴埋めより先に今日の日記を書くことにした。午前4時半就寝。

01/02(火)

午後5時半に起こされ、すぐに家族揃って夕食を摂った。今日はすき焼き。先週金曜日もすき焼きだったが、それから帰省してきた姉がいるとかそういう理由だろう。その姉は食後、新幹線に乗って帰っていった。つい数時間前に運行を再開した北陸新幹線の座席がなんとか取れたらしい。もともとは今日の、もう少し早い時間に帰るつもりだったと聞いた。

自分は、食後は紅白の録画を飛ばし飛ばし見ていた。気になっていたのはTLでも話題だったAdoの「唱」とYOASOBIの「アイドル」。どちらも圧巻だった。「アイドル」で他のアイドルが全員出てきて踊ったことについてはなんだか否定的なツイートも見かけたが、単純にそれぞれが主役級の人たちが大人数で踊っている事実が壮大で、自分としてはなんだかワクワクした。ただしそれに合わせて引き伸ばされた間奏に間延びした感じは抱いた。

その後うっかりこたつで寝落ちして、起きたら日付が変わっていた。入浴してから本日の活動開始。まずはラノベ新刊を予約した。いつも毎月下旬にやっていることだがちょっと遅れてしまい、すでに発売されてしまった本があったりする。今回は34冊となった。ピックアップしたいものがいくつかあるので以下に記す。

「非科学的な犯罪事件を解決するために必要なものは何ですか？」は夏に書籍化の情報を聞いていたが、ついに発売間近となった。楽しみである。

何気なく活動報告に目を通したら、つい最近書籍化の情報が出ていてびっくりした。非常に嬉しい。
週記（2023/08/14-2023/08/20） - kotatsugameの日記

famitsubunko.jp

「現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変」の5巻。4巻が出てから丸一年経過しており、3巻から4巻も1年以上空いていたため続刊を心配していたが、無事出てくれて嬉しい。この巻からイラストレーターが変更になっているからその周りで何かあったのかもしれない。

over-lap.co.jp

「やさぐれ執事Vtuberとネガティブポンコツ令嬢Vtuberの虚実混在な配信生活」。一年半前になろうで読んだがその後の更新は追えていない。そのため書籍化も今初めて知ってびっくりした。

tobooks.shop-pro.jp

その後ついに修論の執筆を開始し、朝まで取り組んでいた。思ったより難しい。とりあえず絶対に書くべきことを大まかに書いてしまって、肉付けしたり順序を入れ替えたりするという形で進められればと思う。

午前8時半くらいに両親が起床したため朝食を用意してもらった。今日もお雑煮とおせちの残り。

そのうち携帯ショップに行きたいなと思っていたが、今日はあんまり眠くなかったのでいい機会だと思って父に連れて行ってもらった。スマホに入れているmicroSDカードの容量が一杯になってしまったため新しいものに換えるというのが主目的。ただスマホ自体、4年近く使ってきてちょっと動作が不安定だったりケースやガラスフィルムが割れてしまっているため、あわよくば機種変更もしたいと考えていた。

父にお伺いを立てるとOKが貰えたがまだこの時点では迷っていた。ただ単純なもので、店員さんに新機種の説明を受けたり実際に手に取って見たりしているうちにその気になった。父も一緒に変えると言い出してびっくり。そこから二人分の契約の説明なりデータ移行なりで3時間ほどかかったので、あんまり混んでいなかったのは幸いだった。

あとは、急にSIMカードを認識しなくなって再起動する事象が頻発していたので、新しいものを発行してもらった。店員さんが機械で新しいSIMカードを読み込むとほぼ同時に古いスマホの携帯回線が途絶して、その反応の良さが面白かった。

microSDカードは最初に適当に選んだが、会計のときやたら高いのを不思議に思って聞くと2万円くらいしていてひっくり返った。結局機種変更もしたのでデータ移行には大して苦労しなかったし、ここで買う意味は一切なかったようだ。父に無駄遣いをさせてしまい申し訳ない。

二要素認証アプリの設定やチャットアプリの引継ぎなど古いスマホを使いたい用事はまだまだあったので持ち帰ってきた。以下の写真は仙台に戻ってから撮ったものである。古いスマホの色が赤なのはちょっとした冒険心だが、思ったより馴染んだ……というかどうせ画面しか見ないので気にならない。新しいスマホも奇抜な色にしようと思っていたのにプラチナシルバー・ブラック・ブルーしかなかったので、泣く泣くブルーを選択した。

pic.twitter.com/JER91XHebc
— こたつがめ (@kotatsugame_t) 2024年1月5日

駅で仙台に帰る新幹線の指定席券を買った。帰るのは金曜日の昼過ぎの予定。そこそこ混んでいたらしいが大宮までは3人掛け通路側の席を、そこからは3人掛け窓側の席を取れた。午後1時半に帰宅して昼食を摂り、午後2時半就寝。

01/03(水)

午後10時起床。夕食はすでに終わっているため夜食になるのだろうか、とにかく別メニューを用意してもらった。昨日のすき焼きで余った牛肉を使った牛丼。高い肉だけあって柔らかくて美味しい。

入浴して午後11時半からCodechef Starters 115に出た。コンテスト初め。このコンテストはRated for Allで、2週間前の113もそうだった。こんな短いスパンでRatedがあるのはかなり久しぶりに感じる。

https://www.codechef.com/START115A

書く：CC

修論に取り組む気になれず新しいスマホの設定をしていた。この時気づいたのだがやはり古いスマホは電池がかなり消耗していたらしい。そちらの感覚で見れば新しいスマホの充電の減りはほとんどないようなものとすら感じられた。

午前4時くらいからようやく執筆を開始。今日も午前8時半くらいに両親が起床したため、切り上げて朝食を摂った。今日は最後のお雑煮。少し残った分は納めるという話だったので、2.5人前くらいを全部食べつくした。

昨日変な時間に寝てしまったので、金曜日昼過ぎの新幹線に乗るために今日夜まで起きて生活リズムを一周させるつもりだった。しかし思ったより眠い。諦めて午前10時半ごろ寝た。

01/04(木)

午後9時半起床。寝すぎ。本当はもっと早く起きて一緒に夕食を摂るつもりだったので自分の分も用意されており、それを食べた。

食後に読売新聞を開いたら「賢くなるパズル」というのが目に入り、軽い気持ちで取り組んだら1時間以上かかってしまった。 $9\times 9$ の盤面が数マスずつ連結な領域に分割されているので、 $1\dots 9$ の数字を各行各列被りのないように埋めて、各領域の数字の総和または総積、2マスの場合なら差・商も可能、が領域で指定された数と一致させるというもの。

演算が指定されているパターンもあるようだが今回はなかった。これが厄介。例えば3マスで105と書かれていたら $3\times 5\times 7$ と埋める数字は一意に決まるが、24だと $2\times 3\times 4,1\times 4\times 6,1\times 3\times 8$ の他に $7+8+9$ もあって大変。

どの数字もすべての行・列に出現する、という条件と領域の条件の合わせ技でしか先に進めなかったタイミングが2回ほどあって、苦しんだ分わかると快感だった。5マスで42と書かれているところに $7+8+9+9+9$ を埋めたのだが、これはそのあたりに9をたくさん置く必要があったから分かったことである。こんな約数の多い数なのに総積ではなく総和が適用されるあたり作問が上手すぎる。

01/13追記：この問題は懸賞問題だったので締め切りが過ぎるまで回答の公開を待っていた。新聞紙に手書きした写真を張ろうとしたが、検索したら専門のブログの記事を見つけたため代わりにそのリンクを置いておく。それにしても、この難易度で「そんなに大変ではなかった」のか……。

読売新聞夕刊賢くなるパズル 1月4日練習・挑戦問題 - なぜだかパズルが好きすぎる

入浴後は日記を書いたり来年度のミールカードの申し込みをしたりしていた。申し込みについて、たしか昨年までは書類を郵送していたと思うのだが、今年はWebから。コロナ禍での冷凍弁当の注文システムを流用しているらしく懐かしい気持ちになった。

午前5時くらいにようやく布団に入ったがなかなか眠れず、1時間ほどハーメルンを読んでから就寝。

01/05(金)

午前9時に目が覚め、布団の中でスマホを触っているうちに1時間くらい経過して予定していた起床時刻になった。

食事して荷物をまとめ昼前に家を出発。母に黒部宇奈月温泉駅に送ってもらった。12月の体調不良で大家さんにお世話になったという話をしたら駅でお土産を買って持たされた。まだ時間が余っていたのでお土産屋をうろうろしたり、天気が良かったので山の写真を撮ろうとしたりしていた。

改札前で母と別れホームへ上がった。途中の階段の一部がずれていてびっくり。写真はうっかり全体像を撮ってしまったのでわかりにくいが、壁際を見ると一目瞭然である。

階段がズレとる pic.twitter.com/plmLADNTUP
— こたつがめ (@kotatsugame_t) 2024年1月5日

せっかくなのでここで元日の地震からしばらく経っての所感を書いておきたい。余震は相変わらず続いており、今朝起きて布団の中にいるときも揺れていた。まあ富山だから揺れても震度1くらいなのだが、逆にここでそれだけ揺れるということは、震源に近い能登では同じ頻度で震度3や4を観測しているということになる。これはちょっと凄まじい話じゃないか。

元日の時点の報道であまり大きな被害が報告されなかったのを見て、正直に告白すると自分は呑気に「日本は地震に強い国だな～」などと考えていた。まあ富山県氷見市では断水が続いていたのだが。その考えを改めたのは以下のツイートが話題になってから。書いてあることをよく読むと音信不通の町がある。これで、被害が少ないのではなく集計できていないのだと理解した。事実、それから日を追うごとにじわじわと、しかし着実に死者数は増えていっている。気が滅入る話。

陸上自衛隊に対し、災害派遣を要請しました。明朝、朝一での対応をお願いしています。
私は地元に帰る途中でしたが、地震により飛行機も新幹線も止まったため、すぐに岸田総理や林官房長官に連絡を取り、官邸へ移動。現在官邸において、石川県庁にいる副知事と連絡を取りながら対応しています。 pic.twitter.com/vylb5k4ikz
— はせ浩（馳浩）石川県知事 (@hase3655) 2024年1月1日

新幹線の車内ではずっとハーメルンを読んでいた。午後4時前に仙台に到着。その足でゲーセンに向かい、3時間半で19クレ投入して01/10まで開催のイベントを走り切った。慣れない素手だったので成果は特にない。どんなにスライダーを乾拭きしてもプレイしているうちにすぐ指がべたついてしまうので、おしぼりが用意されている店舗じゃないと無理だなと感じた。

イオン地下のフードコートでラーメンを食べて帰宅。大家さんに連絡を取って持たされたお土産をお渡しした。

シャワーを浴びて午後10時。今からUniversal Cup 17回目・Jinanセットに参加する。土曜日はOUPC・ABC・Hello 2024とコンテストが盛りだくさんで、フルで参加できるタイミングがなく運営に連絡を取ってこの時間にずらしてもらった。後から知ったことだがUSA1チームはUCを土曜日午前9時から開始し、4時間で全完してそのままOUPCになだれ込んだらしい。

The 2nd Universal Cup. Stage 17: Jinan - Dashboard - Contest - QOJ.ac

書く：UC

感想戦を終え、少し日記を書いて午前4時半就寝。

01/06(土)

午後1時5分前に起床。OUPC2023 Day 1にはソロで参加するのでどうせなら動画を撮ろうと思い立ち、急いで準備を済ませた。何とか間に合って録画開始から十数秒後にコンテストが始まった。

OUPC 2023 Day1 : 大阪大学セット - AtCoder

ABCLJKDHIQMGNFをこの順で解いて14完、3ペナしかつけなかったので速度差で5位に入った。最初3問が難易度順であることは知らされていたので、まずそれを解き、あとは順位表で多く通されているものを見ていった。

A、Bはよい。Cは先頭の文字との差分で判定。Lは実験すると $X=0$ 、 $Y=\frac{1+3+\dots+3^{T-1}}{3^{T-1}}$ が得られた。Jは $\sum_x k^x$ が等比級数の和で求まり、 $\sum_x x^k$ はFPS典型。Kは現在時刻をループ変数で表現し、そのタイミングである空港にいるためにはいつまでに空港1を出発しなければいけないかという情報を管理した。

Dは括弧列と同じ要領でスタックを使えばバーガー文字列が判定できる。知りたいのは全バーガーだけなので $S$ の先頭1文字を抜いておくことに注意。また $S$ 自体が全バーガーである場合にも注意。通してすぐに問題設定を共有しているというE問題をしばらく考えてみたが、こちらは何もわからなかった。Hは答えを二分探索し、bool値のdpをbitsetで高速化する $M^2 X\log K/\mathrm{wordsize}$ が1secで通った。

Iは $A$ と $N-A$ を用意しておけば $B\ge 0$ だと思ってよい。つまり重複を許して選び出した要素の和 $\bmod N$ を考えていることになるので、 $g(t):=1+\sum(t^A+t^{N-A})$ という多項式に対し $g(t)^k$ の係数を見れば $\sum B\le k$ となるような解があるか判定できる。指数の $\bmod N$ を取ったり係数が大きくなりすぎないよう01に置き換えたりしつつ二分探索。

Qは変換がセグ木に乗り、 $(i,j)\mapsto(Ai+B,Cj+D)$ あるいはその転置として表せる。そこで $c\le((Ai+B)\bmod N)\le d$ を満たすような $i$ の総和が求められればよい。 $\gcd(A,N)=1$ より $A$ の逆元を取ったりして計算すると、結局ある範囲の $x$ に対し $A^{-1}x\bmod N$ の和を求める問題に帰着できた。これは $(X\bmod N)=X-\lfloor X/N\rfloor\times N$ を用いてfloor_sumで解ける。

Mはユークリッド最小全域木を取ってその辺だけ見ればよい。kactlから高速なドロネー三角形分割を拝借して通した。全点が1直線上にあるときで1WAしたので、右上・右下・左上・左下の十分遠くに4点追加した。

kactl/content/geometry/FastDelaunay.h at main · kth-competitive-programming/kactl · GitHub

Gは駒がある頂点のペアで状態を表現できる。このままだと遷移が $O(NM)$ になり、提出したら1ケースだけTLEした。結局自分が駒を動かせる頂点に勝ち状態があるかチェックしているだけなので、頂点のペアを決めてから行ける頂点を舐めるのではなく頂点の片方を決めたタイミングで行ける頂点を舐めることにしたら、bitset高速化が効いて $O(M+N^3/\mathrm{wordsize})$ で通った。

Nは、 $k-1$ 番目のグループまで座るのに成功したとき、 $k$ 番目のグループが座るのに失敗する必要十分条件が $\sum_{i=1}^{k-1}A_i+k(A_k-1)\ge L$ となる。この式を見ながら今座っている人数を持ってdp。状態数 $O(NL)$ で遷移 $O(L)$ に見えるが、 $k$ が大きいと $k(A_k-1)\lt L$ を満たす $A_k$ が少ないため、調和級数で2乗logになっている。おそらく $O(L^2\log N)$ 。座らせないグループの人数を弄って得できる場合があることに注意。サンプルが優しい。

Fは $a\gt b$ に対し $(a\mod m)\lt(b\mod m)$ となる条件を考えると $(b\mod m)+((a-b)\mod m)\ge m$ に等しく、 $b$ と $a-b$ の商列挙を同時に行うことで $m$ の範囲が出せた。これを $a=\max A$ のもとほかの $b$ に対してすべて計算すれば、 $m$ として考えられない正整数の区間が求まり、クエリに答えられる。 $O(N\sqrt A)$ 個の区間が現れるためvectorで管理するとTLEで、左端が小さい区間を配列に持ったら間に合った。よく考えれば $(a\mod m)\lt(b\mod m)$ から直接商列挙に持ち込める。

残り15分でPの部分点を全探索で通そうとしたが、ギリギリで投げたコードは実装ミスにより落ちた。ただし1401点がおらず、自分は1400点の中では最速だったため順位に影響なし。

撮った動画には昨日のUniversal Cupのコードが映り込んでしまったので、そちらの終了を待って日曜日に公開した。やたら音割れしているが、もしかしたら年末年始で人とたくさん会話したためデフォルトの声量が一時的に大きくなっているのかもしれない。以降の動画ではマイク音量を少し下げている。

www.youtube.com

TLを見ながら呆けているうちに時間が過ぎた。食事して午後9時からABC335。今日は企業スポンサードに見えて賞品もないし、個人情報の入力も求められない不思議な回。

AtCoder Beginner Contest 335 (Sponsored by Mynavi) - AtCoder

書く：ABC

www.youtube.com

OUPCの動画公開が遅れるため、この動画が新年一発目となる。冒頭に年始の挨拶を入れておいた。

午後11時半からはCF Hello 2024に出た。

Dashboard - Hello 2024 - Codeforces

書く：CF

www.youtube.com

明日も朝早くからOUPCがある。午前5時前に布団に入ったがうっかりカクヨムを読み始めてしまい、寝たのは午前7時くらいだった。

01/07(日)

午後1時10分前に起床。カメラなどは昨日セットしたままにしておいたので、今日は撮影準備に慌てることもない。午後1時からOUPC2023 Day 2、今日もソロ。

https://onlinejudge.u-aizu.ac.jp/beta/room.html#OUPC2023Day2

ABICDKEGJFHをこの順に解き、全完3位。Aが最も簡単ということだけ知らされており、また今日は同時コーディングが禁止なので、順位表情報が得られないタイミングもあるかもな～と心配していたが、結局2問目で詰まったせいでその後そのような場面はなかった。

Aはよい。後から解説を見たら場合分け $O(1)$ 解法があってびっくりした。次にとりあえずBに進んで、手でちょっとやってみたら解けそうだったのでそのまま取り組んだ。 $N$ が奇数のときは行をrotateしていく感じでよい。偶数のときも同様にできるらしいが、気づかずちょっと面倒な構築をしてしまった。ここでタイムロス。

順位表を確認したらすでにいろんな問題にACが出ていてひっくり返った。あとはsolved数順に。Iは行列累乗。Cは入力を $(\sin\theta,1-\cos\theta)$ として $1-\cos t\theta$ が答え。二分累乗法っぽく加法定理を適用していく。

Dはかなり悩んでしまった。閉路において頂点数と辺の数は等しいから、なもりグラフに対し閉路の辺を1本選ぶと考えてもよい。よって答えは1辺と全域木の組でdisjointなものの数。最初に1辺固定すると全域木を $M$ 回数え上げる必要があって、グラフのラプラシアン行列があまり変化しないことを用いた解法がないか探しに行ったが見つからなかった。実は最初に全域木を固定すると $M-N+1$ を掛けるだけになる。

Kはオイラーツアーとセグ木で $l$ 、 $r$ の範囲を求め、掛け合わせる。Eはどちらかの数列を使い切ると確率計算が素直に行かないので、整数 $K$ または $-B$ を置く直前の状態で場合分けした。Gは操作を逆から見る典型。今回頂点に重みがついているが「任意の点に対し最遠点は直径の端点のどちらかである」という性質は辺重みの場合から変わらないようで、それを使って直径を更新していける。Jはマージテク。

Fはとりあえずリールごとに考える。1回殴ると期待値は $E_1=\frac{\sum a}M$ になり、以降殴れる回数が増えるごとに $E_{i+1}=\frac{\sum\max(a,E_i)}M$ と変化していく。あとは頑丈さをどのように割り振るかだが、 $X$ が大きいため愚直な計算は不可能。しかし実は列 $E$ が上に凸なので畳み込みが線形時間で計算できてしまう。1回も殴らない場合を加えると凸性が壊れるため別で遷移させなければならないことに注意。

Concave Max Plus Convolution | Library

$E$ が上に凸であることはコンテスト中は実験で確かめただけだが、証明も難しくない。 $M\times(E_{i+1}-E_i)=\sum\max(a-E_i,0)$ より差分が非負だとわかり、ここからまず $E$ が単調増加であると言える。 $E_i$ が大きくなるにつれ差分の式は明らかに減少するため上に凸だったというわけ。

Hは1列の状態をあらかじめ列挙して遷移させてみた。1列だけ切り出すと長方形は区間になる。 $H=7$ で $a:=28$ 通りあるため全部持とうとすると2²⁸になり到底間に合わないが、ここからいろいろ枝刈りを考えた結果 $b:=4140$ 通りまで減らせた。高速ゼータ変換の要領で区間を一つずつ潰したり増やしたりすれば遷移は $O(ab)$ 回の計算で行え、 $W$ 回繰り返しても十分高速。

枝刈りは「左端または右端を共有する区間は同時に存在しない」というもの。実は当初考えていたのは「左端または右端を共有する区間があるとき、大きいほうを後から追加することはない」という程度のことだったのだが、実装ミスにより前者を書いていたようだ。後者は大きいほうから追加されると無力なので枝刈りになっていない。

www.youtube.com

Dで辺を固定した後毎回全域木を数える解法は $O(N^4)$ になるらしい。グラフ $G$ の全域木の個数を $T(G)$ と書くと、辺 $uv$ について $T(G-uv)=T(G)-T(G/uv)$ となる。ここで $T(G/uv)$ を行列木定理で求める際、縮約で生じた頂点を取り除いて考えることにすれば、使用する行列は $G$ のラプラシアン行列 $L$ から頂点 $u,v$ を削除したもの $L^{(u,v)}$ と一致する。

その行列式は $L^{(u)}$ の $(v,v)$ における余因子として現れるが、今 $L^{(u)}$ は正則なので、逆行列と行列式を求めてしまえば余因子行列が計算できて手に入る、ということらしい。余因子行列から逆行列を手に入れる話は線形代数典型であるものの、逆もできることを意識したことがなかった。感動。

D: tatyam 辺を取り除くと考える　a 行 a 列を取り除いた行列の余因子行列を求めたい → 正則なので逆行列と行列式から求められる
J: SSRS 完全既出 https://t.co/BVCpPnHEAP
G: SSRS 重心分解　重心からの距離の最大の top2 を持つ
— SSRS (@SSRS_cp) 2024年1月7日

食事した後、明日のセミナー準備を始めた。このセミナーは自分の今後の研究計画を考えるのが目的。先生に眺めておいてと言われた教科書を定理に絞って読み、めぼしいものを書き出していた。

途中で飽きてカクヨムに手を出してしまった。最近読んでいた「面倒くさいからって試験をサボったら序列最下位で学園生活が始まったんですけど、ここからでも巻き返すことってできますか？」を読了。同じ作者は他作品で現代ダンジョンものを2本書いており、どちらも非常に好みなので新作のこれにも手を出してみた。相変わらず誤字が多いが面白い。

kakuyomu.jp

教科書を読み終えた後は論文のサーベイを行った。最近の研究の動向を見ようと思ったのだが、そういう探し方は何分初めてなものでよくわからない。まあ目ぼしいものはいくつか見つかったからよしとしよう。シャワーを浴びて午前6時前に布団に入り、1時間ほどハーメルンを読んで就寝。