10/28(月)

午後4時少し前に起床してインターン先定例会に出席。昨日寝る前に、今日の定例会は普段より30分遅く始めると告知されていた。

進捗はなし。勉強会は書籍の売り上げ予測の話だった。本の売り上げのピークは発売日に来ると思っていたが、実際はそれより数日遅れるらしい。考えてみればほとんどの本を予約購入している自分でも、大学生協の営業日などが影響して発売日当日に入手することはむしろ少ない。そして売り上げに計上されるのは自分が店頭でお金を支払ったタイミングなのである。

定例会後に大学生協へ。およそひと月ぶりにブラックサンダーを箱買いしたら、720円から880円へと大幅に値上げされていた。生協が暴利を貪っているわけではなく、今はメーカーで買ってもそのくらいになるようだ。自分が買い始めた4年前はドンキに行けば550円弱で手に入ったが、そちらはどうなっているのだろう。

予約していたラノベを受け取り、学食で食事して帰宅。それから先週の週記を書いて、午後11時半に切り上げて投稿した。いくつかのコンテストが穴あき。

少し後からECR171に出た。

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

Aはよくわからないが、A問題であるということを考えて長方形内部に正方形を取り、対角線を出力すると通った。Bは二分探索。 $n$ の偶奇により1点追加するか否か、またペアの作り方もほとんど決まる。64bit整数をうっかりlongと書いてしまって1WA。このミスをしたのは本当に久しぶり。Cは $n$ 日目から降順に適当な貪欲をしたら通った。Dは算数を頑張る。

なんとEが解けなかった。4完114位。あまりの出来の悪さに絶望し、コンテスト終了直後に録画データを削除した。TLでEが燃やす埋めるだと知り仰天。解法ガチャでフローまでは出たのに、この典型を完全に忘却していた。

その後EとFをupsolveした。Eは知ってしまえば簡単。Fは一旦普通のSWAGを書いて、それを永続化した。必要になる永続stackはABCで既出であり、根付き木によって非常に簡単に実装できる。しかしやっぱり永続化されたデータ構造は魔法のように見えるな。

動画を見たりしてグダグダ過ごし、午前5時半就寝。

10/29(火)

正午起床。ハーメルンで「プーサーなオリ主とコナン君」を読んだ。ファンタジーの産物を積極的に公開していてびっくりするが、これはこれで気分が良い。

syosetu.org

そのまま布団の上で二度寝、三度寝と繰り返していたら火曜日が終わりかけてしまった。以降は次の日の日記へ回す。

10/30(水)

10/29 午後10時半起床。木曜日のセミナーに向けてpreprintの加筆修正を始めた。最初は気分が乗らずちょくちょくなろうを読んでしまっていたが、エンジンがかかってきてからは結構ガリガリ書き進めることができたと思う。本来は火曜日のうちにある程度進めておきたかったのに、うっかり寝て過ごしてしまったので、その危機感もあった。

掲載するつもりのデータの生成も並行して行った。いつでも作れると思っていたが、実際計算させてみるととんでもなく時間がかかり冷や汗。序盤の見積もりでも夕方ごろまでかかる予定だったのに、後半に行くにつれ扱うデータが大きくなって予想以上に遅れ、結局夜までかかった。ギリギリ間に合う時間に計算を始められてよかった。

昼は学食。先週噛んでしまって傷つけた下唇の内側が今日になって一段と痛むようになり、口を動かすのが辛い。その点ラーメンという選択肢はなかなかよかったのではないか。レンゲを使うと唇をあまり動かさずに食べられた。ラノベを買って帰宅。

夜まで作業を続け、午後8時になって何とか完成。preprintをメールで先生方に送った。

集中講義の課題レポートも提出し、午後9時就寝。

10/31(木)

午前1時に目を覚ました。preprintの英語に関する指摘が来ていたので反映した後、シャワーを浴びてラノベを読み、午前7時前にもう一度寝た。

今度は午前9時半くらいに目を覚ました。もう少し寝ておきたいなと思いつつスマホを触っていたが、午前11時過ぎというもうそろそろ起きなければならない時間になってうっかり入眠。次に起きたら午後1時半、セミナー開始の予定時刻だった。寝坊である。

メールで一報入れて即登校。午後2時前に到着してそのままセミナーを開始した。特に何も言われなかったのが怖い。セミナーでは昨日送ったpreprintの改善点についていろいろ指摘してもらった。それらをなるべく早く反映して、今度は別の先生にも送る予定。1時間ちょっとで終了した。

先々週と同様、同じ教室で行われる5限のセミナーにも顔を出す予定。ただしそれまでの時間は特にやることもないので一旦解散となった。ちなみにそのセミナーでは、先週ベルトランの仮説を証明したらしい。かなり興味があるので、帰省で聞き逃したのは残念だった。

院生室に移動すると、持ち込まれた私物に関して少々問題が発生していた。学生相談室に行く人々に着いて行ったりした結果抜け出すタイミングを見失い、5限にはかなり遅れての出席となった。

学食で食事して午後7時から麻雀。今日は原付で登校したため、終電を気にせず日付が変わった午前1時過ぎまで打っていた。かなりツイている日だったらしく、4半荘でトップが2回か3回、面前で清一色を上がった。待ちは自分ではすぐわからず、慣れている人の助けを借りた。

写真の手は四・七萬のみらしい。タンヤオと一盃口が付いて倍満だが、一盃口を見落として跳満で申告してしまった。後日このツイートを見た父に「三連刻」というローカル役を指摘されたが、そういう系はほとんど採用していない、はず。そもそも詳しい取り決めがあるほど打ち慣れていない。

4半荘でトップ2回か3回。面前で清一色上がった pic.twitter.com/Rqx61Bj1pm
— こたつがめ (@kotatsugame_t) 2024年10月31日

帰宅後、ラノベ「恋愛魔法学院」2巻を読了。面白かった。やはり主人公の造形が好みである。また周囲のキャラも主人公に寄りかかりすぎず自立しようと努力していて、そういう人々に対してなら主人公が少し手を貸すのは全く気にならない。心地よい関係性を築けているなと思った。

午前9時半就寝。

11/01(金)

午後2時過ぎ起床。院生室の私物問題に関して専攻長が視察に来るかもという話が昨日あったので、顔を出すことにした。昨日は他人事みたいな書き方をしたが、実は関係している。詳しくは伏せておきたい。

ところが登校してみると、そもそも専攻長が今仙台にいないということで、少なくとも今日は視察がないことが確定した。仕方ないので麻雀が始まる夜まではpreprintの修正を行っていた。しかしこういう個人作業をするのであれば、モニターが複数枚あるとか、机が広くて綺麗とかの理由で、やはり自宅のほうが快適だろう。

午後6時半に学食で食事して、それからいよいよ麻雀。今日は1半荘だけだった。ラス親がトップに立ってもなかなか上がり止めをせず、確か4本場まで突入。トップ狙いで強気に行ったら振り込みまくって、一時はラスまで落ち込んだが、それを上回る放銃をした人がいて3着に浮上した。

院生室に戻ってもう少しpreprintに関する作業を続けた。大学のいいところはMathSciNetが使えるところ。.bibファイルの中身を全部MathSciNetで出力し直すと非常に綺麗になった。

午後11時帰宅。10月の読書記録をツイートした。ネット小説の月だった。

10月の集計
買った：24冊
読んだ：3冊
積読：+21冊
積読（累積）：+169冊
— こたつがめ (@kotatsugame_t) 2024年11月1日

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

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

Aは $\sum a$ の値とその偶奇を見ればよい。Bは3分割して、真ん中の列を $[k]$ または $[k-1,k,k+1]$ とする。Cは小さいほうから二つの和が最大値を超えることが条件。2番目の最小値と最大値を見ながら尺取りする。

Dはまず線形探索で $p_i\gt 0$ となる最初の $i$ を見つける。これにクエリが $i-1$ 回。その後は $p$ の値が $2$ 以上 $n-2$ 以下の範囲で単調増加するので、尺取りっぽくすれば高々 $n-3$ 回の質問ですべて特定できる。 $i\le n-1$ なので、計 $2n-5$ 回と見積もれた。実際には $p=n-2$ となる場合クエリを投げなくても確定しているとか、 $i=n-1$ ならその後の質問が一切必要ないとかで1回以上減り、通る。

Eは大変。 $i$ に対する操作回数を $v_i$ として、まず $b_i:=v_i+v_{i+1}$ について $a_i+b_{i-1}=a_{i+1}+b_{i+1}$ という式を得る。ここから $b$ の値はoffsetを除いて一意に定まり、 $v$ の値はどこか一か所固定するとぐるっと一周してすべて決定する。その固定した値は $b$ の交代和の半分でなければならないが、交代和が偶数にならなくてもoffsetを1ずらせばよい。最後に $v$ 全体に適当な値を足して非負にすれば完成。ただし最大値が10¹⁸を超えないことはよくわからなかった。

Fは分割した列の後ろのほうが後手勝ちならNim、先手勝ちならMisere Nimという最後の石を取ったほうが負けるNimの変種になる。後者の勝利条件も既出で、普通のNimとそれほど変わらない。dpも多少面倒だが頑張ればできる。 $a=1$ が連続する部分をうまく扱うため、後ろから見つつ最後に $a\gt 1$ だったインデックスを管理した。このインデックスを前に動かすとき、同時にdp遷移の準備をする。

sigma425.hatenablog.com

全完13位。Dのクエリ回数の見積もりでかなり手間取ってしまった。

www.youtube.com

そういえば、今日寝ている間に海外から荷物が届いていた。開けてみるとthink-cell Round 1の賞品の靴下。足裏に右辺値・左辺値と書いてあるのは面白いなと思った。

こどふぉから靴下届いた pic.twitter.com/A6uhpyNASE
— こたつがめ (@kotatsugame_t) 2024年11月1日

シャワーを浴びてからpreprintの作業に戻った。少しだけのつもりがなんだかんだ完成するまで続けてしまい、午前7時ごろメールを送信。午前7時半に寝た。

11/02(土)

午後2時直前に起床。また寝坊しかけた。飛び起きてUniversal Cup、今日は15回目のChengduセット。

https://qoj.ac/contest/1821

書く

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

AtCoder Beginner Contest 378 - AtCoder

書く

振り返りはギリギリ間に合ったが、動画を投稿している暇はなかった。午後11時半からCF #984 div.3。

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

Dまでやるだけ。Dは面倒なだけの嫌がらせ問題だった。Eは列ごとに単調性があるので条件が区間で表せる。区間の端点を表す変数rと入力の $r$ を被らせるというポカをやらかして1WA。Fは区間の数の総XORとinterestingでないものの総XORを求める。

Gは大変。まず最上位bitが同じ数の区間に分割し、それぞれで聞く。これによって $a\oplus b\oplus c=0$ でも確実にどの区間にあるか、さらに最上位bitが立っているかを見ることで具体的に何個かまで確定させられる。ここまでで $\log_2 n$ クエリ。区間内に1個ある場合はこの時点で値まで確定しており、2個ある場合は二分探索で求まる。

3個ある場合が大変で、単に二分探索を2回行うだけでは $2\log_2 n$ クエリになって微妙にオーバーしてしまう。そこで区間を2分割して、どちらか片方に3個ある場合どんどん再帰していくのを繰り返す。どこかのタイミングで2個と1個に分かれるが、1個なのが左右どちらかは実際に1回クエリを投げれば判定可能。2個のほうの区間を二分探索すると、これまでの再帰と合わせて $\log_2 n$ クエリになる。

全完、Gで手間取ったが12位。

www.youtube.com

何とか動画2本の投稿まで間に合わせ、午前2時からMHC Round 3に出た。

Meta Hacker Cup - 2024 - Round 3

書く

しばらくラノベを読んで午前9時半就寝。

11/03(日)

午後2時半起床。シャワーを浴びて目を覚まし、午後3時からTROC #40に出た。

https://tlx.toki.id/contests/troc-40

Aは $|X|\le NK$ 。Bは、どちらが勝ってもレーティングの集合は $X\gt Y$ として $\{X+1,\max(Y-1,0)\}$ に変化する。Cは一つで割引が得られるものを取り除き、もう1回割引されるかを調べる。Dは $R$ を固定して各要素を区間に含めたときの寄与を考え、最も良いsuffixをセグ木で求めた。

Eは爆破する鉱山の数 $k$ を全探索。 $A$ が大きいほうから $k$ 個を爆破することになり、残りは必要なだけ $\max(A)$ の採掘を間に挟んでいく。 $k-1$ 個挟んでも足りなければ、 $A$ の最大値と2番目の最大値を交互に採掘する。

Fは有向全域木に見えてかなり悩んだが、とりあえずコスト計算のコードを書いたところで $S_i$ から $S_j$ を作るコストとその逆が等しいことに気づいた。よって無向辺だと思って最小全域木を求めればよい。

Gは最小値から左右に伸ばしていくdp。遷移できるかの判定には直前2項が必要なので左右で $O(N^4)$ 状態になってしまうように見えるが、片方が値を大きく飛ばしたならそれを全部もう片方が拾わなければならないので、実は $O(N^3)$ 状態しかない。

Hはずっとフローを考えていて全然気づかなかった。実は、セッション $i$ でin-personとされたクラスそれぞれに生徒 $i$ を割り振るだけでよい。もし生徒 $i$ がonlineでしか参加しないセッション $j$ があるとすれば、それはすなわち $X_{i,\ast}$ と $X_{j,\ast}$ がdisjointということになり、明らかに矛盾する。そのようなセッションがなければ、onlineの生徒は常にin-personな生徒の真部分集合となっている。

滑り込み全完で6位。レートが3024→3031(+7)と微増し、ついにランキング一位に立った。

TOKI 3024->3031 (+7)
インドネシアで、一位 pic.twitter.com/t9kcUGcJnO
— こたつがめ (@kotatsugame_t) 2024年11月3日

今日の夜はインドカレー屋「RAJ」で食べることにした。入店時は空腹でいくらでも食べられるつもりだったが、用心して頼んだ少し安めのセットでもギリギリだった。

食事 pic.twitter.com/QrZ7PnF7D0
— こたつがめ (@kotatsugame_t) 2024年11月3日

この後のコンテストに備え、ゲーセンには行かずに帰宅。3時間ほど仮眠をとって午後10時半に目覚めた。かなり眠かったが30分の間に少しマシになり、午後11時からYandex Cup Algorithm部門のSemifinalに出た。

Enter — Yandex Cup 2024 — Algorithm — Semifinal — Yandex.Contest

Aは行・列独立に貪欲でよい。Bは $\sim\le t$ である確率の $n-1$ 乗を $t=0,\dots,k-1$ で足し合わせる。Cは予め隣接行列の2べきを計算しておき、クエリごとに適切に選んで掛け合わせる。このとき行列積ではなく行列とベクトルの積を求めるようにすれば、計算量が $O((n^3+qn^2)\log k)$ になって間に合う。

Dは算数。基数 $i$ で $k+1$ 桁以上の数は $\max(R+1-i^k,0)-\max(L-i^k,0)$ 個あるので、これを足し合わせる。 $k\le 4$ は二分探索で $i$ の範囲を求めた後、4乗和の公式まで埋め込んで計算した。 $k\gt 4$ は十分少ないので毎回ループを回して計算。

Eは素因数ごとに木を圧縮して計算。といっても頂点を抜き出しているだけで、元の木における距離さえ高速に計算できれば圧縮木を構築しなくても最遠点は求まる。その距離の計算には $O(\log n)$ かけたが、1.2secで通った。

Fは $s$ と $t$ を全部連結した文字列のSuffix Arrayを使う。クエリごと、部分木の各頂点について対応する $t$ をprefixに持つ区間に $+1$ しておき、 $s$ の各suffixの値を取得したい。木をdfsして入る瞬間と出る瞬間の差を見ればよい。区間加算が $n$ 回、1点取得が $2\sum|s|$ 回となった。

1時間21分で全完して4位。疑いようもなく決勝進出である。直近、大きな大会としてJapan OpenとMHCの予選もあり、どちらも落ちてしまったが、三つ目にして海外旅行を引き当てることができて非常に嬉しい。

日本人の決勝進出者は、順位表を信じるなら7名。昨年はペナありの順位表が終了後しばらくしてペナなしに書き換えられ、それで順位の変動が結構あったのだった。今年は最初からペナなしになっていたので、正しいものが表示されている可能性が高そう。

その7名のDiscordサーバーが作られ、準備について少し話し合われた。主にはパスポートの取得と、昨年のコンテスト環境について。そういえばYandex Cup 2023の参加記をまだ書いていない。せっかくなので書きたいが……。

https://t.co/aoN5OmAteP
執筆中……
— maspy (@maspy_stars) 2024年11月3日

朝までなろう版の「恋愛魔法学院」を読んでいた。とりあえず書籍化された部分まで読み終えたが、2巻はかなり加筆があったらしい。武術大会が存在しなくて驚いた。また周囲のキャラも結構印象が違い、特にエリクが腹黒でより得体の知れない感じになっていたように思う。

https://ncode.syosetu.com/n2840hw/

午前7時就寝。