04/29(月)

午後7時起床。今日は休日のためインターン先定例会が休みだった。先週の週記を書いて午後11時半に投稿し、直後からECR165に出た。

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

Aは $p_{p_i}=i$ なる $i$ が存在すれば2、そうでなければ3が答え。Bは左の0から順にすべての1より左に持ってくるのが最適。1の個数をカウントしながら見ていくとコストがわかる。Cは区間を選びその左右どちらかの値で置き換える操作だと思うことができる。dp。

Dは $b$ でソートしてBobにとっての無料と有料の境界を全探索。境界の上は下位 $k$ 個を優先度付きキューで持ち、下は $\max(b-a,0)$ の総和を持った。Eはuniqueでない区間のうち右端が最も左にあるものを見つけ、その右端を置き換えることを繰り返す。区間を見つけるためには右端を固定した状況で各値がカバーできる左端を管理すればよく、区間ADD区間MINでカバーされていない点を探すテクで処理できる。

Fは手札に揃ったカードがあれば貪欲に出してよい。そうでないなら手札に全種類のカードが1枚ずつ揃っているから、それがどのタイミングで発生するかを考えてdpした。例えば $a_i$ を引いて手札が一杯になったとする。 $a_{i+1},\dots,a_j$ のうち奇数回登場したタイプが $u$ と $v$ の二つのみ、かつそのような $j$ が区間 $(i,j)$ に存在しないとき、 $u$ と $v$ を捨てると次に手札が一杯になるのは $a_j$ を引いたタイミングだとわかる。3乗だが定数倍が非常に軽いため全く問題なかった。

全完3位。Eのテクは最近やたら見る気がする。

www.youtube.com

ラノベ「バスタード・ソードマン」3巻を読了。信じられないくらい面白かった。ただの日常の積み重ねなのに相変わらずやたら面白いなと思いながら読み進めていたら、ラストでぶっ飛ばされた。これまで読者にすら隠されてきた主人公の本当の実力が一部明かされたのだ。シーンとしては危機が迫るなどの大きなイベントがあったわけではないが、これまで3巻分の積み重ねがあったこその魅せ方で、最高に強烈だった。

ゴミ出しをするつもりだったのに、とりあえずもう一冊と手を出したら途中で眠気に耐えられなくなり、そのまま寝た。午前9時。

04/30(火)

午後7時起床。夜中までラノベを読んでいた。

「やる気なし天才王子と氷の魔女の花嫁授業」を読了。能力の代償が重すぎるように見えて辛い。ネタバレになるが主人公の代償はやる気のなさに繋がっており、そのせいでヒロインへの気持ちが表れにくく、代わりにヒロインと関わる理由として契約・約束が何度も強調され、窮屈に感じた。

午後11時半からCF #942 div.1に出た。

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

Aは最終的な $a$ に対する $n\times\min(a)-n+1+\#\{a_i\gt\min(a)\}$ が答えなので、 $\min(a)$ を大きくするのがよい。最大いくつを達成できるか二分探索し、余ったものは最後の項を大きくするように割り振った。

B1とB2はあまり関係がない。B1は $a$ が $b$ の倍数になるから、あとは算数。 $b$ の全探索により $O(m)$ になる。B2は $g:=\gcd(a,b)$ とすると $g$ が $(a+b)/g$ の倍数になるため、 $a/g\le\sqrt n$ 、 $b/g\le\sqrt m$ の範囲を調べればよい。全探索で $O(\sqrt{nm})$ 。

Cは先頭から順に決めていった。 $f^k(a)_i$ を $k$ に関する多項式で表示し、 $i$ 乗和の公式を $i\lt 20$ くらいまで求め、それを使って計算。多項式の扱いに慣れていなかったが一発で合って良かった。しかしそうやってべき乗和の公式によって計算した値は、寄与を考えるとBITを表す木のパスに沿った累積和 $k$ 回だから2項係数で求まってしまうようだ。

Dは二分探索を考えると、先頭から順に、functional graph上で移動可能な範囲にあるできるだけ小さい値を取っていくのが良い。これだとHLDやセグ木が乱れ飛んで計算量に大量に $\log$ がつくので見方を変える。目的の値をどんどんインクリメントしつつ、そこに到達可能かを判定することにすれば、ただ2点間の距離を求めるクエリになって、部分木判定などにより $O(1)$ で実行できる。

E1が上限と下限付きランダムウォークになることには気づいたが、計算できずコンテスト終了。5完41位でレートは2807→2856(+49)となった。

www.youtube.com

E1をupsolveした。 $m$ が小さいときは $O(nm)$ のdp、 $m$ が大きいときは鏡像法で解けるらしい。鏡像法はうまい具合に $\dots,+1,-1,+1,-1,+1,\dots$ を配置するタイプのもので、ゴールにたどり着ける始点が $O(n/m)$ 個しかないため計算量 $O(n^2/m)$ となる。

TCB 2024/03回2位の賞品、アマギフ7000円分が届いた。

ラノベ「依存したがる彼女は僕の部屋に入り浸る」2巻を読了。相変わらず面白かった。ハーメルンと突き合わせてみると、やっぱり今回も書き下ろしの章が複数あるらしい。ストーリーも時系列も、主人公の印象すら崩さずにうまくラブコメ色を強めたものだと感心する。また挿絵もよい。特に、1巻でもチラッと見えていたが、主人公が本当に納得感のある容姿をしていて素晴らしい。

届いていた外付けSSDに過去の動画をいくらか移した。2023年までのCFの動画を移動させたところ60GBほど空いたので、熱を持ってきたこともあり一旦終わり。外付けSSDは思ったよりコンパクトだったからなんだか信用できない気がしたのだが、小ささは技術の発展の現れであり、信用すべきでないのは6年以上使っているPCのほう。

過去の動画がPCストレージを圧迫しており、そろそろ何とかする必要がある。消すのもなんだか良くない気がしたので、外付けSSDを買ってそちらに溜め込むことにした。
週記（2024/04/22-2024/04/28） - kotatsugameの日記

修論英訳の作業をして午前11時半就寝。

05/01(水)

目覚ましで午後4時に起床。サークルバチャに参加するつもりだったが眠すぎて二度寝……しかけたその時、後輩からセミナー発表資料が送られてきた。読んでいたら目が冴えた。

午後4時40分からサークルバチャ。ARC088Cに取り組んだら、順列 $p$ の転倒数が $\sum_i|i-p_i|$ で求まると思い込んでとんでもないことになってしまった。今日は大学の教室の予約がいっぱいで取れなかったらしく、Google Meetで感想戦をして終わり。

https://kenkoooo.com/atcoder/#/contest/show/b33dceb0-9699-47c4-bc41-63776efe9a31

E - Papple Sort

後輩のセミナー発表資料を読み切っていくつかコメントを送り、4月分の読書記録をツイート。買った冊数が少し控えめ、さらに後半頑張っていたので3月までよりはマシといった感じ。それでも増分が正なのは変わらず、今年に入ってからだけで積読が100冊超増えたらしい。

4月の集計
買った：27冊
読んだ：16冊
積読：+11冊
積読（累積）：+105冊
— こたつがめ (@kotatsugame_t) 2024年5月1日

ラノベ「現実離れした美少女転校生が、親の決めた同居相手で困る」を読了。ヒロインが献身的すぎて読んでいるだけで申し訳なくなってくる。過去に主人公の言葉で救われたという話だが、そのエピソードと現在の主人公へ向ける愛情にバランスが取れていないと感じた。

午前2時くらいまで日記を書いた後修論英訳に取り組み、シャワーを浴びて午前7時就寝。

05/02(木)

05/01発売のラノベを10冊注文していたらしいので混んでいない時間を狙って受け取りに行く必要がある。ということで頑張って午前11時に起きて大学に向かった。無事受け取った後は学食で食事。この時間にすでに牛乳が売り切れていて愕然とした。購買にもなかったし、販売を停止してしまったのだろうか。

└( ＾ω＾ )┘♪ 買った♪└( ＾ω＾ )┘♪ 買った♪ pic.twitter.com/Z0oBhjsqeO
— こたつがめ (@kotatsugame_t) 2024年5月2日

いったん帰宅して荷物を整理し、今度は山に登って午後1時から後輩のセミナー。予備知識として必要になった閉曲面の分類の話だったが、難しかった……。すべての補題を証明しきることはできず、いくつかの補題を認めた上での議論。また展開図の上でグラフを描くのにも慣れていないようで手こずっていた。あまりに苦しいので次回はまた別の論文を読むことになった。

論文の話をしたり、秋から新たに受け入れる留学生に何をしてもらうか相談したりして午後6時過ぎ解散。学食で後輩と夕食を摂った。APG4bを少しずつ進めてくれているそうで、取り組んでいるのを見守った後コードを少し手直しさせてもらった。アルゴリズム小話として素数判定を $O(\sqrt N)$ で行う話をし、午後8時帰宅。

Webページをいくつか読んで時間を過ごし、シャワーを浴びて午後11時半からCF #943 div.3。

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

Aは $\gcd(x,y)\le x-y$ なので $y=x-1$ とすれば最適。Bは部分列判定で失敗した位置を答える。Cは $a_n=10^9$ から降順に $a_{i-1}=a_i-x_i$ と決めていった。Dは $n$ 回以下移動した後そこに留まり続ける。始点 $n$ 通りすべてに対してスコアを求めようとしてしまったが、 $P_B$ と $P_S$ からだけで十分。それぞれ $O(n)$ かけてよい。

Eは $(1,1),\dots,(1,N-2),(2,N),(N,N)$ 。Fは $k=2$ または $k=3$ で、累積XORを見て判定。Gはhard versionを直接解いた。LCPの長さ $f$ を決め打つと、suffix arrayを見ながら貪欲に分割していくことで $f\le f_k$ なる $k$ の最大値が求まる。これは $N/f$ 以下なので、貪欲に分割する部分を1回あたり $O(\log n)$ でできればあとはそれを繰り返すだけでよい。

全完7位。

www.youtube.com

ゴミを出し、寝るまでラノベを読んでいた。2冊読了。

1冊目、「平民出身の帝国将官、無能な貴族上官を蹂躙して成り上がる」。規則と証拠をもとに相手を言い負かす行為、これに憧れたことがないと言えば嘘になる。ただ現実では無理だろう。規則の文面や相手の発言を一言一句覚えきるのも、日頃の行動から瑕疵をなくすのも不可能。というわけで、主人公がやって見せたのは読んでいて楽しかった。ただしその対象となった敵キャラが周りに多すぎて、足を引っ張られまくっているのが辛い。

2冊目、「戦地から帰ってきたタカシ君。普通に高校生活を送りたい」。面白かった。向かうところ敵なしの主人公たちがドタバタしていて楽しい。紙幅が足りなかったようで肝心の高校生活については次巻以降。ただ一点、作品の軽快さに比べ、徴兵されて生還した主人公に対する家族の反応が重すぎると思った。それは重いのが当然の反応とは言え、そこまでニヤニヤしながら読んでいたのが申し訳ないような気持ちになってしまった。

午前7時半寝落ち。

05/03(金)

午後7時起床。本を読んでいた。午前3時ごろ寝落ち。

05/04(土)

午前6時半起床。昨日に引き続き本を読み進め、午後1時ごろ「冬季限定ボンボンショコラ事件」を読了した。大満足！自分はいかなるネタバレも踏まないようにと早めに読んだので、そういう配慮をここでもしておこう。普段書いているような感想は下に隠しておいた。

感想（ネタバレ注意）

今作はほとんどの部分が小鳩君による、小佐内さんと出会うきっかけとなった過去の事件についての回想だった。あらかじめ良い終わり方をしないとの前振りがあった上では読むのにも気合いが必要だったが、頻繁に現在のシーンが挟まれて一息つけたため、あまり負担にはならなかった。

過去の事件の終わり方は確かに最悪と呼べるものだった。しかしその直後から始まる現在の事件の解決編が強烈で、全体としての印象はそちらが目立つ。良い結末と言えるかは微妙なところかもしれないが、二人らしいものだったことは確か。またそれとは別にシリーズとしての締めもあって、そちらははっきりと良かった。

伏線はどれも明確に指摘できなかったが、知ってから振り返れば確かに違和感を覚えた箇所はあった。具体的に挙げるのはよしておく。ただどれも（どれもと言うほど数はない）、詳細な描写がなかったので勝手に解釈してしまったらしい。そういう伏線は明かされないと気づけないのに、明かされると悔しい思いをする。

小鳩君が最初に日坂くんを見舞った際、日坂くんの姉らしき人物とすれ違ったのには気づけた。わざわざ描くくらいだから何かあるのだろうと思って覚えておいて、後半で姉の特徴と一致することを知ったため興奮。しかし結局本文中で触れられることはなかった。そういう明かされないままの伏線が他にもあるのだと思う。

しばらく仮眠して午後3時半にまた起床。急いでシャワーを浴び、午後4時からUniversal CupのチームでCFの謎4.5hに参加した。

Dashboard - Helvetic Coding Contest 2024 online mirror (teams allowed, unrated) - Codeforces

書く

G問題はCodechef Lunchtimeからの剽窃だったらしい。

https://codeforces.com/blog/entry/129149?#comment-1146461

先生からメールが来ていた。修論でも引用した論文の著者が4月に新しく論文を出しており、やっていることが自分の修論と非常に似ているらしい。ヤバすぎる！来週木曜日のセミナーは先々週の続きではなくその論文を読むことにした。

これまでチンタラ準備してきた論文が紙くずになってしまったかもしれず動揺を隠せないが、とりあえず今はコンテストに向き合う。パックご飯を腹に詰め込んで午後9時からABC352。

AtCoder Beginner Contest 352 - AtCoder

Aは $\min(X,Y)\lt Z\lt\max(X,Y)$ か判定。Bは問題文が読みにくいが部分列判定と同じことをすればよさそう。Cは $\sum A+\max(B-A)$ 。Dは $a$ を全探索し、インデックスをsetで管理して最大・最小を求めた。Eは $(A_{i,j},A_{i,j+1})$ という辺だけ取り出してクラスカル法。Fは連結成分を一つ取り出して残りをbitDPすることを繰り返した。 $O(N^3 2^N)$ 。

GはABC331Gと似ていると思い、 $S\subseteq{1,\dots,N}$ に対して取り出した靴下の多重集合が $S$ になる確率を求め足し合わせた。ただ、 $n$ 回以上操作する確率を $n\ge 0$ で足し合わせるほうがよほど自然だし、結局計算は $n=|S|$ でまとめて行うためそちらを経由することになる。

G - Collect Them All

29分弱で全完し6位。かなり調子良く解き進められたと思ったものの、周りはもっと速かった。コードゴルフはAをdc、CをNibblesで。Aは $(Y-Z)(Z-X)$ が正か負かで判定したがNibblesに負け。入力をソートして $Z$ の位置を検索するのはかなり上手い。

www.youtube.com

コンテストを終えてもまだ精神の安定は戻っていなかった。今更じたばたしてもしょうがないと開き直り、ラノベを開いた。

「最強魔法師の隠遁計画」18巻を読了。ようやくテンブラムが開幕したかと思ったら本の前半しか使わず早々に終了してしまった。あまりにあっけないし主人公もほぼ活躍せず残念……と思ったら見せ場は後半に待っていた。久しぶりの主人公の全力バトル。最高だった。あとがきによれば次巻は舞台が変わるらしい。なろうと照らし合わせると、もしかしたら第5部冒頭のルサールカ訪問のことを言っているのかも。待ちきれない！

第5部冒頭のアルスが第1魔法学院を視察する話はかなり好きなので、早く本で読めないかとかなり前から心待ちにしている。
週記（2022/12/26-2023/01/01） - kotatsugameの日記

朝になってようやく論文の確認を始めた。読んでいくと、幸い自分の結果とは異なる、どころかいくつかは自分の結果に含まれるようなものだったので一安心。自分もいい加減けりをつけてarXivにでも上げてしまわなければならない。

正午就寝。

05/05(日)

午後10時起床。

ラノベ「VTuberの幼なじみと声優の幼なじみが険悪すぎる」を読了。面白かった。思ったより険悪でびっくりしたが丸く収まってよかった。ヒロインたちの仕事を応援する主人公の立ち位置が、遠くはなく、近すぎもせず、ちょうど良く感じた。炎上を鎮火するくだりはちょっとうまくいきすぎかなと思った。

日付が変わったころに布団を脱出。食事して少しだけインターン関連の作業を行い、日記を書き始めた。午前7時ごろからは昨日読んでいた論文のセミナー準備に移り、シャワーを浴びて正午前に就寝。