08/28(月)

午後4時半起床。インターン先の定例会に参加した。

先週は1on1で一瞬作業したきり一切稼働していない。最近進みがないと正直に報告したところ原因を聞かれたので、学業を理由に挙げた。しかし修論ヤバいですよと指導教員の先生に言われ続けているのがストレスになっていることは確かだが、かといって学業に邁進しているわけでもないのが現状のため、罪悪感を感じてしまう。

勉強会は会社の決算書の読み方だった。損益計算書とか貸借対照表とか、経営ラノベで名前だけ聞いたことがあったものの実例を見て興奮。ただし金額の正負だったり分類の慣例がややこしくて内容はあんまり理解できなかった。お金が入ってきているのか出て行っているのかを理解するだけでもその項目に関する知識が必要。

夜はずっと週記を書いていた。日付が変わる直前に投稿。相変わらず穴だらけなのでさらにしばらく文章を書き足していたが、急激な眠気に襲われて布団に倒れこんだ。午前2時くらいに寝たはず。

08/29(火)

午前10時前には目を覚まし、布団に横たわって本を読んでいたらしい。

正午くらいに「遺品博物館」を読了。面白かった。主人公があらかじめ調査しておいた様々な情報をもとにどんどん話を進めていくので、まるでミステリの解決編ばかり読んでいるかのような感覚だった。一つ一つの話が短いのもあって大変読みやすい。落ちには苦いものもあったが、そういう本だと分かっていれば問題ない。一番最初の短編が一番好みだった。

続けてしばらく布団でゴロゴロした後、シャワーを浴びて外出。学食の昼の部は終わっていたので、購買でお菓子・菓子パン・ラノベを買って帰宅した。

Universal Cup第2シーズンのチーム名を決めた。そろそろjapan〇〇も出尽くした感じがするので自然数以外にしようと言って、いろいろ案を出し合った結果分数を $\bmod{998244353}$ で表記することになった。japan406364961である。元となった分数は簡単に復元できるのでここでは説明しない。本当は黄金比がいいなと思っていたのだが、残念ながら $\sqrt 5$ が存在しなかった。

布団に入って買ってきたラノベを読もうとしたら、瞬く間に寝た。午後4時から午後9時くらいまで寝ていたはず。起きてからラノベを2冊読了した。

1冊目、「ネットの『推し』とリアルの『推し』が隣に引っ越してきた」2巻。1巻はVTuberの炎上しそうな行動に冷や冷やさせられたが、2巻では別のヒロインがクローズアップされており逆にVTuberヒロインが空気になっていた。アイドル声優はVTuberより知らない分野の話なのでデートに出かけていても気にならない。好みのシーンもあり面白く読めた。

2冊目、「ログアウトしたのはVRMMOじゃなく本物の異世界でした」4巻。ここにきていきなり動画配信者たちが登場した。好きな設定なので歓迎。この巻では出てきただけといった感じだが、さすがに顔だけ出して終わりということはないだろう。次巻以降の展開に期待。

午前7時くらいに寝たようだ。

08/30(水)

午後3時半起床。今年のMHCの開催が告知されていた。サイレントで消滅するといったことにならなくて非常に嬉しい。

It's Happening! Meta Hacker Cup 2023 Schedule - Codeforces

ずっと布団でラノベを読んでいた。午後7時前に「S級冒険者が歩む道」を読了。面白かった。追放モノはざまぁパートの前振りに耐えられないことが多いので避けていたが、挑戦ということで読んでみた。するとどうやら追放した側にも焦点を当てた作品だったようで、過剰にギスギスしたり逆に見返すシーンがやりすぎだったりすることがなく、かなり読みやすかった。

シャワーを浴びてセミナー準備を始めた。今週も金曜日がセミナーの日だが、先生から今日までに原稿を送るよう言われている。先週火曜日の計算は、その後少し捏ねたら参照していた論文に出てくる感じの等式になってくれた。目的の式でこそなかったものの仮定を弱めることに成功しており満足。うっかり満足してしまって、以降何一つ進捗がなかった。

別の方法ですでに証明した等式の別証明を作ろうとしたのだが、これがかなりうまくいって大興奮。目的の式にまではたどり着けなかったもののかなり綺麗な形にまとまってくれた。
週記（2023/08/21-2023/08/27） - kotatsugameの日記

とりあえず行った計算の発表メモを作ってから先生に送る前にちょっと調べておこうかなとサーベイ論文を見たら、自分が示したものとほとんど……いや全く同一の式が書いてあってひっくり返ってしまった。全然新しい成果ではなかったらしい。今更どうしようもないのでそのまま送信。

午後11時半からCF combinedに出た。

Dashboard - Pinely Round 2 (Div. 1 + Div. 2) - Codeforces

Aはオンラインになっている人数と延べ人数を管理して判定。Bは $p$ において $i$ が $i-1$ より前にあるとき入れ替えるためには $x=i$ で操作しなければならず、逆にそれを全部行えばソートが完了する。一瞬で思いつけて良かった。

Cは操作のどの瞬間においても $0\dots n$ の中で数列にない数が一意に定まる。自分はここから「どの数からどの数に遷移するか」を求めダブリングしたが、遷移先が操作を繰り返しても不変であることは自明ではなかった。後からよく見たら各要素が同じ周期 $n+1$ を持っており、そこから従う。ただこれが分かっていれば周期で計算したほうが速い。

Dは同じ行にある縦置きドミノのペア、同じ列にある横置きドミノのペアに分解できればそれぞれで塗り分けることで条件を達成できる。そうでなければできないことの証明をしようとしたが細部が詰められない。信じることにして出したら通った。

Eは各クエストについてそれを最速で終わらせるためには何時までに最初のクエストを開始しなければならないかをトポロジカルソート順のdpで求めた後、全体の開始時刻をずらしながら計算した。開始が間に合わないクエストは丸1日遅れる。

FはXORだからと性質を考えてみたもののよくわからず、 $n\le 10000$ という制約に注目して $O(n^2)$ では？と疑ったところ区間dpが書けた。累積XORを取っておくと、区間からそのprefix・suffixに遷移する際の条件がそれぞれ右端・左端の特定のbitの状態で記述できる。この条件を逆の左端・右端に集めておくと、判定がbit演算によって対応するbitが立っているかいないかチェックするだけで可能になる。この判定結果自体は保存する必要がないため、空間計算量が $O(n)$ になる。

Gはfunctional graphの辺を張り替える問題に読み替えた。木の部分はdpでよいがループ部分が面倒。長さ2とか3のループに辺を生やしたもので実験し、それに合わせて式を立てたら通った。長さ $n$ のループにおいてその上の辺を $n-1$ 本以上張り替えようとすると勝手に $n$ 個の自己ループが出来上がり状態を区別できない。よってその重複分を削除すればよく、逆にそれ以外は区別できるようだ。

Gは難しいと思ってかなりじっくり取り組んだが、実はFと250点差しかなかったらしい。それでGのACは遅めだったもののそれまでの速度が効いて7完23位。レートは2871→2935(+64)と、何とか2900台に戻ってきた。

www.youtube.com

大学生協のサイトで以前見つからなかったHJ文庫の新刊が登録されているのを見つけたので注文しておいた。

いざ大学生協のサイトで注文しようとしたところ、なぜかHJ文庫の新刊が一部しか登録されていないらしく、見つからなかった本が3冊もあった。
週記（2023/08/21-2023/08/27） - kotatsugameの日記

あとは日記を書いていた。何やら腹の調子が悪く、頻繁にトイレに行っては下痢便を出しておりなかなか辛い。午前7時半就寝。かなり寒気があって、結局夏もずっと出していた冬用の布団を引っかぶりながら怠惰な自分に感謝した。

08/31(木)

正午くらいに腹痛で起床し、トイレに駆け込んだ。その後二度寝したものの2時間くらいでまた腹痛に叩き起こされたため、以降は布団でラノベを読みつつトイレとの間を往復していた。夜になって熱を測ったら7度3分あった。

「お嬢様（じつは庶民）、俺の家に転がり込む」を読了。上流階級ラブコメと書いてあって期待していたものの、ずっとノブレス・オブリージュを連呼しているだけだった。まあこんなことを感想として書いたところで、では何があったら上流階級っぽいのかは自分もラノベ由来の知識しかないのだが……。

午後11時半からECRに出た。直前に熱を測ったら6度6分まで下がっていた。熱を測り始めるタイミングが遅くて、直前というかA問題を読んでいる最中に温度計を確認している様子が動画に映っている。

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

Aは17か71。後から調べたら13と31、37と73、79と97の計4種類があるようだ。Bは同じ位置に01があることが必要十分条件。十分であることはすぐわかる。必要性がわからないまま出したが、コンテスト後に考えたら、最終的な状態が両方とも/^0+1+$/になると固定してよく、その境界は初期状態から不変であるということから言えた。

Cはソートされているとわかっているprefixの長さ、ソート関係が壊れているとわかっている最も先頭に近い位置を持って頑張ってシミュレート。Dは負にする区間と正にする区間（と0にする要素）を固定すると、区間をまたぐような操作はしなくてよいため個別に計算できる。大小関係が壊れている位置ごとに1回操作が必要なので、それをprefix・suffixに対して前計算。

Eは順列を左から貪欲に見つけていけばコストが計算できる。そこで「長さ $i$ の列で右 $k$ 個しか順列になっていない」ような列を除原理により数え上げておけば、それを $+i$ の遷移の係数としてdpすることで「コストに寄与する順列が $[j,j+k)$ にある場合の数」を求められる。寄与ごとに足し合わせることでコストの合計が求まる。

Fは解けず。人とスートを固定したときそこに最大まで配ってよいことはわかる。その後他の人に配る際最大値 $M$ を二分探索しようとして、判定を $b_j\le\sum_i\min(M-a_{i,j},T-\sum a_{i,\ast})$ （ただし $T$ は一人当たりのカード枚数）みたいな自明な必要条件で行ってみたものの、WAだった。

5完15位。Eは末尾に連続する相異なる数の個数を持つdpで解けるようだ。頭が良い。

www.youtube.com

ラノベを読んだり少し論文を読んだりして、午前8時就寝。

09/01(金)

ギリギリに起きて午後1時からセミナーに参加した。昨日は明らかに体調不良だったため、オンラインで参加したいということを先生にメールしておいていた。

今日発表する証明は適当に計算したら思いがけず出てきたものだし、結果自体は既出だしで先生に「進捗ないんですよね？」みたいなことを言われてしまったが、強い意志で「これが進捗です」と言い続けていた。それが正しいかどうかはともかく、そう思わないとやっていられない。ひとしきりチクチク言われてから発表。全部合わせて1時間半くらいで終わった。

夜までラノベを読み、午後7時から2時間くらい仮眠した。起きてから8月分の読書記録をツイートした。今月は中旬がカクヨム三昧で、公式の読書データによれば150万文字ほど読んだらしい。下旬はかなり頑張っていて1日1冊を超えるペースで読了したが、買った冊数にはまだ遠かった。これ積読減らすの無理じゃないか？

8月の集計
買った：28冊
読んだ：20冊
積読：+8冊

積読（累積）：+107冊
— こたつがめ (@kotatsugame_t) 2023年9月1日

午後9時20分からyukicoder 403に参加した。

yukicoder contest 403 - yukicoder

Aは9だけか判定。Bは操作が全体デクリメント＋選んだ要素に $+N$ なので、 $A_i\bmod N$ が一致するか見る。Cは等差数列の初項を $a$ 、交差を $d$ としたとき $0\le a\le M$ かつ $0\le L\le a+(N-1)d\le R\le M$ が条件。 $a$ を固定すると $d$ の範囲が床関数の差で書けるのでfloor_sumになる。制約がやたら大きいのでRubyで実装した。

Dは各政党の残っている最もスコアの高い候補者が優先度付きキューに入った状態を保って $M$ 回pop。EはZ-algorithm。Fは桁dpをしようとしたが桁数の異なる数の辞書順比較を考えるのが面倒だったので、辞書順の大小関係が決定する桁を決め打って算数で数えた。Gは二分探索。

Hは各マスが白のまま残る確率を求める。操作で選べるペアの個数が $c$ 個減って、確率は $T=(H-K+1)(W-K+1)$ と置くと $(1-c/T)^N$ となる。 $c=1\dots K^2$ に対し該当するマスが何マスあるかを算数で求め、確率を計算して足し合わせた。IはLi Chao Treeを窃盗してきてdp。

JはHのHard版で、 $K$ が非常に大きい。丁寧に算数をすると $c$ は $ij$ （ただし $1\le i\le I,1\le j\le J$ ）や等差数列や定数に分類できて、定数は直接、等差数列は $N$ 個より少し多く計算してラグランジュ補間で対応できる。よって問題は $ij$ 。

$(1-x/T)^N$ を多項式と見て展開すると、 $0\le n\le N$ に対し $(ij)^n$ の和が求まればよいことになる。これは直ちに $i^n$ と $j^n$ の和をそれぞれ求めることに分解される。 $n$ 乗和はファウルハーバーの公式というものを使えばベルヌーイ数の前計算により $O(n)$ で求まるが、それをすべての $n$ に対してそれぞれ計算するのは間に合わない。

ここで時間切れ、9完最速で8位となった。直後にmaspyさんの記事に載っていたのを発見しupsolve。すぐ上の一つだけ求める項は見ていたのになぜここが目に入らなかったのだろうか。ちなみに、ファウルハーバーの公式もよく見るとEGFの畳み込みになっていて計算できた。

[多項式・形式的べき級数] 高速に計算できるものたち | maspyのHP

将来のために、Wikipediaのファウルハーバーの公式ページに関する注意点についてメモ。このページにあるベルヌーイ数の定義は一般的なものと少し異なり、 $(-1)^n B_n$ を計算しているようだ。実際には3以上の奇数 $n$ で $B_n=0$ なので、 $B_1$ の符号が反転しているのみである。

ファウルハーバーの公式 - Wikipedia

昼までかけてラノベを2冊読了。「男子禁制ゲーム世界で俺がやるべき唯一のこと」の1巻と2巻。ハイテンションなセリフ回しが肌に合わないところもあったが非常に面白かった。

1巻は設定の導入。魔法の理論はかなりしっかりしているようだし学園も巨大で好みの要素が多い。原作知識を自重せず使うのは爽快。またそうしなければ乗り越えられないほどの困難が次々襲い掛かってくるため決してヌルゲーにはならないのも読んでいてドキドキした。2巻はバトル。ここでも原作知識で強大すぎる敵に立ち向かっており、どうやって倒すのかとハラハラしながら読んだ。

午前11時就寝。

09/02(土)

午後8時前に起床。食事して午後9時からABC318に参加した。今回のスポンサーは自分のインターン先である株式会社THIRD。

THIRD PROGRAMMING CONTEST 2023 ALGO（AtCoder Beginner Contest 318） - AtCoder

Aは $\lfloor(N-M)/P\rfloor+1$ なので意気揚々とdcで実装……したが $M\le N$ の条件がなくて1WA。 $\lfloor(N-M+P)/P\rfloor$ に書き直した後Pascalで実装していたらもう一度WAが出て、何も信じられなくなった。恐る恐るPascal実装を出したら通って一安心。dcの実装が $P=1$ のとき壊れることに気づいて納得した。

Bは愚直で通る。Cは購入するセット数を全探索して $F$ が大きいものから置き換えていく。DはbitDP。Eは $A_i$ を固定し、 $A_j$ が任意の場合の数から $A_i=A_j$ の場合の数を引いた。

Fは $L$ が昇順なので近い宝から順に取ってよい。宝までの距離が変化するタイミングは $O(N^2)$ 個の $(X_i+X_j)/2$ だけなので変化しない区間に分割し、それぞれで条件を満たす $k$ の区間を求めた。このとき宝を距離でソートしたため $O(N^3\log N)$ 。距離の順序は関係が変化するときにswap操作を行うことで管理できるので、この $\log$ は落とせる。

GはBlock Cut Treeだと思って窃盗してきてコネコネしたが2ペナ。よく考えると頂点倍加してフローを流しても流量がたったの2なので十分間に合う。

Exはまずループを一つずつ作っていく $O(N^2)$ のdpを書いた。ループごとにAliceが削除する辺、Bobが削除する辺は一意なので、そこが $Q$ の最小値になっているかどうかで二人が間違えるかが決まる。2²状態持って遷移し、二人とも間違える場合の数を求めた。

結構遷移がややこしいのでこの方針には見切りをつけ、形式的冪級数による解法を探りに行った。まず包除原理によってAliceが正解する場合の数を求めることに帰着。長さ $l$ のループが $c_l$ 個あるとして立式してみた。

まず $P$ の決め方について。ループに対する頂点の割り当ては、多項係数 $N!/\prod_l(l!)^{c_l}$ に同じ長さのループを区別しないための $1/\prod_l c_l!$ が掛かる。各ループでの並べ方は円順列なので $\prod_l((l-1)!)^{c_l}$ 。

$Q$ の割り当ては $P$ によってループが区別されているので多項係数そのまま、またループ内で最小の $Q$ だけAliceが削除する辺の重みに決まっており、残りで $P$ と同じく $\prod_l((l-1)!)^{c_l}$ が掛かる。全部まとめると $(N!)^2/\prod_l l^{2c_l}\cdot c_l!$ となった。このあたりで確かめるためにdpを書いたら合わず、間違いを探している間にコンテスト終了。7完遅めで71位となった。

そのままExを解き切った。書いたdpがバグっていただけで式は正しいらしい。ここから $l$ の寄与だけ取り出して多項式にすると $f_l(x)=1+\frac{x^l}{l^2\cdot 1!}+\dots+\frac{x^{nl}}{l^{2n}\cdot n!}+\dots$ になるが、これは $\exp(x)$ に $x\leftarrow\frac{x^l}{l^2}$ と代入したものに他ならない。

よって求める多項式は $\prod_l f_l(x)=\prod_l \exp\left(\frac{x^l}{l^2}\right)=\exp\left(\sum_l\frac{x^l}{l^2}\right)$ 。FPSのexpを窃盗して出したら通った。ちなみにこの窃盗先は昨日のyukicoderのJ問題でもお世話になったライブラリである。

https://judge.yosupo.jp/submission/53187

www.youtube.com

午前0時からUniversal Cup 1回目、Qingdaoセットに出た。ABCの動画は撮影終了がギリギリになって、アップロードだけしておき公開はUC後になった。

The 2nd Universal Cup. Stage 1: Qingdao - Dashboard - Contest - QOJ.ac

書く

朝までABCのコードゴルフをしていた。Aはコンテスト中に提出した10Bのdcが最短らしい。BはNibblesで解こうとしたらTLEが取れず、仕方なくAWK。Cは $F$ を降順ソートして $D$ 個ごとに区切り、それぞれ和を求めて $P$ とのMINを足し合わせるのが良さそう。今言ったことをそのままNibblesで書いたら20Bになった。他は手付かず。

午前10時になってAHC023が開始したので、問題を読んだ。

10th Asprova Programming Contest（AtCoder Heuristic Contest 023） - AtCoder

TLにUniversal Cupの感想ツイートが続々流れてきたので読んでいた。新ジャッジシステムではちゃんと設定を行うと提出を公開することができる。自分たちのチームアカウントでも設定したはずだと思っていたが、どうやら見えていないらしい。何度設定をやり直しても元に戻るという不具合を見つけて公式Discordで報告したところ、なんとたったの5分で運営から直したとの返答があった。改めて設定するとうまくいって感動。

布団で少しラノベを読み、午後1時就寝。

09/03(日)

午後6時半起床。1時間ほど布団でスマホを触ってから起き上がった。食事してシャワーを浴び、午後9時からCFの5hコンテストにソロ参加した。

Dashboard - COMPFEST 15 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred) - Codeforces

最初のほうは順位表情報がなかったので先頭から順番に読んでいたが、Cまでは難易度順だったらしくポンポンと解けた。あとはAC数が多いものから解いていった。

Aはよい。Bは $X/Y$ の各素因数を $p$ と $q$ のどちらに振り分けるか。Cはトポロジカルソートの逆順に計算。

Hはまず列 $S'$ を数えた。 $x\in S'_i$ と $x+1\in S'_{i+1}$ のような対応する要素をつなぐといくつかのパスができて、各パスをどこから集合に入れるか独立に考えられる。これは算数によって $O(1)$ で求まるので、すべての $n=1\dots N$ について求めることで $S'_1\ne\emptyset$ であるような長さ $n$ の列を数え上げ、 $N-n$ 個の $\emptyset$ と合わせて並び替えると $S$ が数えられる。

Gは二分探索。シミュレートは左から見て、移動できる限界を比較しながら貪欲に割り当てていくとよい。Dは基本的に貪欲に取りつつ、取った場所にそれより前の要素を入れた。こうすると後から移動した要素を取ることで貪欲でない選び方が再現できる。

Mは「高さ $i$ の状態からかかる操作回数の期待値」を $\mathrm{dp}_i$ として求めた。 $i$ の昇順に $\mathrm{dp}_i$ を $\mathrm{dp}_{i+1}$ の漸化式で表す。このためには $k=0\dots i$ についての $(P_{i+1}/100)^{k+1}\mathrm{dp}_{i-k}$ の和を $\mathrm{dp}_i$ の式として表す必要があるが、 $P_{i+1}$ は100通りしかないのでそれぞれ計算しておくことで対応できる。

Lは $K$ を全探索。インデックス $\bmod K$ で分類すると、それらの要素がいつ選択されるかが簡単な一次式で表せて、あとは $O(1)$ 算数で取れるボールの個数が求まる。 $N\lt K$ で壊れていたらしく1WA。Iは負けマスを右下から追っていった。 $K=0$ なら一直線に並ぶが、special tileがあると少しずつずれるらしい。

Kはクエリを全部読んで整理すると1次式の $x=K$ でのtop 2を求める問題になる。CHTで凸包を作ると、それに含まれる直線のtop 2は最大値の左右1本ずつ見ればよい。凸包を作る際に削除された直線についてはもう一度集めて改めてCHT。pop_backで出てきたものは当然傾きが単調ではないのにソートせずCHTしてしまったり、傾きが同じ直線の扱いに失敗してしまい2WAした。手元でランダムケースを作ってチェック。

Jは区間dp。 $l$ 降順・ $r$ 昇順で計算すると区間長の2乗かかるdpも一緒に計算できるテクで、区間の両端を同じpacketに入れる場合のコストを計算した。最初はdpが必要なことに気づいておらず1WA。

Eは各エレベーターについて最後に運んだ人を持つdp。状態数 $O(Q^3)$ で、各状態に対し次に処理するクエリがわかるので遷移は $O(1)$ 通り。エレベーターを $x$ 階に運ぶのは動いていなかった間で最も電気料金が安い（かつonであった）日に行ったとしてよい。ここはエレベーターごとにセグ木を作って区間MINで取得できる。クエリ1だけ取り出したりしていたら添え字回りで頭を壊し2WA。

残り10分ちょっとではFは不可能。12完で11位、ソロ参加では4位だった。

www.youtube.com

朝は日記を書いていたが、途中で集中が切れラノベに手を出した。「迷宮狂走曲」。ハーメルンで一度読んだもののここ1年ほど更新を追っていなかった。相変わらず面白い勘違いものだった。イラストがあると結構印象が変わる気がする。世界観は結構陰惨なのにどことなくほんわかしているような……。主人公視点のギャグみたいな軽さともちょっと違う。

今週インターンの進捗を一切産めていないことに気づき、恐怖から3時間ほど稼働した。今週頭に方針だけ決めてやっていなかったことがあったのでそれをこなし、あとは少しコードを書いて実行した。まあ最低限進んだと言えるだろう。正午就寝。