04/08(月)

午前7時くらいに目を覚ましてハーメルンを読んでいた。

「勝ち逃げツインターボ」を読了。面白かった。ウマ娘二次創作で人間のスポーツに触れるものはほとんどないから目新しい。また担当ウマ娘が大逃げというのも新鮮だった。いないわけではないものの、その場合も大抵は圧倒的な強さで相手をすり潰すあっさりしたレース描写になりがちで、この作品のようにドキドキする展開にはならない。強いのは好きだが手に汗握るレースも好き。

syosetu.org

布団を出て先週の週記を書き、午後2時を回ったあたりでシャワーを浴びて大学に向かった。コロナ禍以来学食は昼の部と夜の部に分かれていたが、今年度からついに間の時間の営業も復活。授業開始日の混雑を警戒しこの時間を狙った。席は問題なく確保できたものの思ったより人がいて残念。しばらくすればこの時間帯はもうちょっと空いてくれるだろう。そうして弛緩した雰囲気の中で食事するのが好き。

購買でパンやラノベを買って帰宅。昨年度末、ミールの適用範囲が元に戻るだろうと言っていたが、実は臨時措置から通常ルールに格上げされるだけだったようだ。ミールのパンフレットにも明記されていたのにすっかり見落として騒いでいた。まあ特別な告知もなしに今までできていたことができなくなるなんてことは考えにくいか。

理由というのは、ミールの適用範囲拡大措置についてのもの。コロナ禍が始まってから何度かの期間延長を経て続いてきたこの措置だが、今のところ今日までということになっている。これまでの延長は数か月前の時点で告知されていたから、春休み突入に合わせて終わるのだと思う。いつもこの制度を利用してお菓子だったりパンだったりを買っていたので、残念。
週記（2024/02/19-2024/02/25） - kotatsugameの日記

帰宅して午後3時半からインターン先定例会。先週もミーティングをした。今週は特にそういう予定はなく、またタスクについてもいったん確認待ちだったり相手方のアクション待ちだったりする。

勉強会はAHC031の話。短冊状に切るのが正解というのはTLでも見ていたが、それでちゃんと面積が足りない場合のペナルティを小さくできるのはやはり驚き。また領域の切り分けが決まっていると割り当ては貪欲が最適になるというのは、アルゴの問題っぽくて面白かった。

解散後はずっと週記を書いていた。午後11時を回ったころに投稿し、半からのCF #938 div.3に備えた。

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

Aは難読。自分が読んだときは「ちょうど」 $n$ 個というのが太字ではなかったため、そこを探すのにしばらく時間を使わされた。Bは $a_{1,1}=\min b$ から構成してチェック。Cは前から $\lceil k/2\rceil$ 回、後ろから $\lfloor k/2\rfloor$ 回攻撃する。 $k\ge\sum a$ のケースだけ別で処理すれば前後で独立に考えられる。Dは幅 $m$ の区間をずらしながら頻度配列の差を管理。

Eは $k$ を固定するごとにimos法の更新と累積和の計算を同時に行って $O(n)$ で判定できる。なんだか見覚えがあって、0と1が隣り合っている箇所から端までの距離が重要だったはずだが、この問題とは合わないのでおそらく設定が少し違うのだろう。Fは $4$ だけ別で処理し、 $1,2,3$ についてはあらかじめdpしておく。

Gは $a_{1,1}$ の約数それぞれについて $O(nm)$ で判定。約数列挙は $\sqrt{a_{1,1}}$ まで見る愚直で十分だったが、間に合わないと勘違いし、エラトステネスの篩で素因数を一つメモしておく方法の素因数分解を持ち出した。Hは少し丁寧に評価すると $r\le 11$ が言えるので、各塔と各 $r$ について減らせるHPを計算し、bitDPした。手数が多くて面倒。

全完6位。

www.youtube.com

動画を投稿して午前2時半就寝。

04/09(火)

午前9時前に起きたが、ハーメルンを読んだりゴミを出したりダラダラYouTubeを見たりしていたらすぐ午後2時を回ってしまった。シャワーを浴びて外出。郵便局で用事を済ませた後、生協で散髪し、食事して帰ってきた。

再度シャワー。床屋帰りには切った髪を洗い流すため必ず浴びるようにしている。床屋でも洗髪してもらっているのだが、首元から服の中に入り込んだ毛はこうするしかない。今日は昨日浴びずに寝てしまった分を出る前にもこなしていたし、なかなか非効率的な段取りだった。

今週のセミナーで発表する内容を決めるため、論文を読み始めた。正直に言って何もわからない。日付が変わる前くらいに眠気がやってきたので逆らわず寝た。

04/10(水)

午前9時起床。論文を読んでいたがやっぱり何もわからず、途中2時間ちょっと二度寝していた。

午後3時外出。本当はゲーセンに行くつもりだったがセミナー準備が全然終わっていないため、用事だけこなしてすぐ帰ることにした。

まず入学式で着たスーツ一式をクリーニング屋に持って行き、ついでに近くの花見会場の桜が満開になっていたので先週と同じ構図で撮ってみた。毎年この時期は写真を撮っているのだが、きれいな構図を見つけられた試しがない。

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

あとは学食で食事し、ラノベを買って帰宅。セミナー準備をする。今週は木曜日のセミナーに加え金曜日にも他大学の先生を招いて話を聞くことになっており、そこで参考となる論文が送られてきたので、木曜日のセミナーではこれを扱うことに決めた。午前4時まで準備を進め、さらに1時間ほど修論の英訳修正を進めて今日は終わり。

その後、準備の合間に読み進めていたラノベ「迷宮狂走曲」2巻を読み切った。主人公の勘違いの理由が毎回丁寧に説明され、都合が良すぎることもあるものの分かりやすくて良い。装備を性能だけで選んでいるから統一感がなく気持ち悪いという設定は、別にそんな重要でもないかなと思うが、挿絵で忠実に表現されておりインパクト抜群だった。

午前6時半就寝。

04/11(木)

午前11時に起床し、1時間ほど布団でグダグダしていた。明日のセミナー後の夕食会で使う店を予約し、登校して学食で昼食を摂った。

午後1時から2時間は自分の発表。昨日準備したのは結局preliminariesの範囲だけで細かい証明は正直どうでもよかったので、もっと前に準備した分からまだ話していないところを扱った。次の2時間は先生が最近の研究内容について発表。予定されている学会発表に向け、この先数回は先生も話すらしい。

解散して後輩とともに学食に行き、しばらく話した。セミナーの途中で競プロの話が出たのだが、彼もQuizKnock・鶴崎さんがされているところから興味を持っていたらしい。APG4bを紹介しておいた。夕食の後も東北大学の学生向けサイトの案内等でしばらく立ち話をしていた。

帰宅後は気力が尽きたのでラノベを読んでいた。「凡人転生の努力無双」を読了。昔カクヨムでも読んでいたがやはり面白い。

大人の精神を持って転生したため幼少期から努力を積み重ねることができ、結果伝説的な力を手にするという、言ってしまえばテンプレ通りの流れ。ただし設定や描写がちょうど良いため面白いのではないかと考えた。努力を全部描写するわけではなく、ただし一気に飛ばしすぎるわけでもない。身に着けた技術も設定上あまり多くはならないが、無双するには十分であった。

修論の英訳修正を進めて午前3時就寝。

04/12(金)

午前9時起床。ちょっとハーメルンを読んでいたら、地下鉄ではなく原付で登校しないと間に合わない時間になってしまった。夕食会に行く際どうしようか迷いつつ、急いで出発した。

午前10時から2時間弱は招いた先生によるセミナー。最初は知らない用語しか出てこなくて絶望しかけたが、雰囲気で解釈したら正解を引き当てたらしく、内容には結構ついていくことができたと思う。今日は紹介していただいた論文の背景について話したとのこと。そういうのは分野に詳しくないと見えないくせ、論文を深く理解するには必須となってくるから、話を聞けたのは非常にありがたいことだった。

昼休みに入り混み合う直前の学食で昼食を摂り、近くの広場を散歩してからいったん解散。修論の英訳についてしばらく先生と話していた。

午後1時半から再開し、今度は自分の発表。修論の内容の説明だったが、前提知識から主定理までじっくりねっとり説明したら休憩を挟んで午後4時くらいまでかかった。発表順序もあまり考えていなかったせいで、ちょっと行き当たりばったりだったり手戻りが発生したりして反省。ただ最終的には必要なすべてのことを伝えきれたようで良かった。

その後の時間は修論の応用に関する議論に充てられた。自分が以前考えていた方針について取り上げたせいか、午前中学んだ話はほとんど出てこずちょっと失敗したなと思う。今日しか話せないことが他にあったのではないか。それはそれとして話は盛り上がりいつまでも続きそうな具合だったが、店を予約した時刻である午後6時が近づいてきたため切り上げた。少し遅れると店に連絡を入れ、地下鉄で移動。

店はいつもの武屋食堂。定食を頼むのではなく、一品ものをいくつか頼んでシェアする形式で注文した。また全員お酒を飲むようだったので自分も飲むことにした。さらば原付。飲み食いしたものは以下のツイートとそのツリーにまとめてある。

食事 pic.twitter.com/qfaL88C4St
— こたつがめ (@kotatsugame_t) 2024年4月12日

帰宅して午後9時20分からyukicoder 427に出た。

yukicoder contest 427 (ゲーム問題コンテスト) - yukicoder

Aは戦略も何もない。約数の個数の偶奇つまり $N$ が平方数かどうか。Bは一つ目の敗北条件が気になって初手で $i=1$ を選んだケースを考えたら、後手の戦略を盗むことで先手必勝であることに気づいた。ただし $N=1$ のケースだけ後手勝ち。ところで一つ目の敗北条件に引っかかるのは $N=1$ のケースのみだから別にいらなかったのではないかと思う。ただしその場合は常に先手必勝になるから、それを嫌ったのかもしれない。

Cはなかなか考えがまとまらなかった。-でない文字による連結成分が一つの場合を考え、おそらく各連結成分の両端の文字がどうなっているかが重要だとエスパー。それっぽく書いたら通った。Dは「互いに素でない」という関係で $2\dots N$ に辺を張ったときの $N$ を含む連結成分のサイズが重要。 $N$ が $2$ より大きな素数でなければ $2$ と連結で、そこから $N/2$ より大きな素数以外すべてと繋げられる。

solved数を見てFへ。木の深さが1ならNimだから一般のケースも似たような感じだろうと思って考え、深さ偶数が無視できることに思い至って、それ以外の頂点によるNimという解法にたどり着いた。この考察には見覚えがある。そもそも問題自体既出だった気もする。

Eに戻った。 $N$ の約数でない最小の数 $m$ を初手で選ぶことができれば先手勝ち。そうでない場合は $m$ が持っていて $N$ が持っていない素因数を見て云々……と判定していたが、そんなものはないため後手必勝。余計な場合分けをいろいろ入れていただけなので問題なく通った。

Gはまず四面体の体積を行列式に言い換える。操作はある行の $A$ 倍をどこかの行に追加するものだから行列式は変わらないと思ってしまったが、冷静になると $j=k$ のとき行列式を $A+1$ 倍する操作になる。行列式の絶対値を $\bmod{(6\times 101)}$ で持ってメモ化再帰した。手番が交互ではなかったり、 $A+1$ 倍を $A$ 倍としていたり、行列式が $0$ の場合引き分けであることに気づかなかったりしてかなり手間取った。

全完7位。午後11時半からはECR164に出た。

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

AはBobが連続する区間を選ばなければならないと勘違いしてタイムロス。さらに判定もミスってWAを出してしまった。Bは $a_1$ に等しい要素の連続区間を一つ削除すればよい。Cは3桁の手計算によれば最上位桁と残りの桁で大小関係が逆になっているのが最適っぽい。同じ数字の桁を無視して考えることに注意。

Dは $a$ から取り出した列 $b$ に対し $\max(\sum b/2,\max b)$ がvalueとなる。 $\sum b\lt 10^4$ までは値に対して場合の数を持つdp、それ以降は $\sum b$ の偶奇に対して場合の数と総和を持つdpを書いた。

Eは $a_i\leftarrow\lceil a_i/k\rceil$ とすると $k=1$ のケースに帰着できる。これは有名問題で、 $a_0$ とした上での $\sum\max(a_i-a_{i-1},0)$ が答え。ところでこれを $k$ 一般に戻すと、区間 $[a_{i-1},a_i)$ に存在する $k$ の倍数の個数となる。つまり、あらかじめこの区間をimos法で集計しておき、 $k$ の倍数それぞれに対して覆う区間の数を数えればよい。調和級数で愚直が十分高速。

Fはわからなかった。極大な1の連結成分とそのサイズ、個数をもとに重複を頑張って取り除くdpを考え、コンテスト終了後しばらく粘って一応サンプルを合わせることには成功したものの、実行時間が長すぎてお話にならなかった。5完52位。

www.youtube.com

なろうを読んで午前6時くらいに寝た。

04/13(土)

午後1時起床。少しなろうを読んで午後2時からUniversal Cupに参加した。28回目、Chengduセット。これがシーズン2の最終回となる。

https://qoj.ac/contest/1596

書く

食事して午後9時からABC349。

AtCoder Beginner Contest 349 - AtCoder

Aは問題名から解法がわかる。ただ零和ゲームを知らなければ難しいのではないかと感じた。Bは問題名の意図が分からないが言われたことを実装。Cもまあそのまま。Dはセグ木の区間の話をしていると分かればおしまい。ただしACLのような非再帰セグ木はノード番号のみで扱っているため、区間の復元を求められる今回はあまり使えなそう。再帰による実装が楽。

Eはちょっと気合いを入れて実装。Fは $M$ の素因数が高々13種類しかないので、素因数分解してどの素因数を必要なだけ持っているか考えればよい。状態数2¹³のbitDPで、遷移も $N$ 個それぞれ行うのではなく2¹³パターンに分類してから行うことで十分高速になる。 $M=1$ のとき空集合を数えてしまい1WA。

Gは文字の一致・不一致の条件をUFで表現する。Manacharを書き換えて実装すると張るべき辺の本数が $O(N)$ になるため、あとは先頭から復元すればよい。 $A$ がManacharで得られる回文半径から1引いた値であることに気づいておらず少し手間取った。

全完9位。コードゴルフはAをNibbles、BをRaku、CをPerlで書いておいた。Aは2行目の総和を求め $-1$ を掛けた。Auto Valuesを用いて2Bで、これが最短の符号反転。ただし今回は $N$ から入力された数の総和を引くほうが短くなるらしい。2行目を抜き出す部分で1B差がついた。

www.youtube.com

午後11時半からはCF #939 div.2に出た。

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

Aは $n=100$ でシミュレートした結果を見て答えた。こういう問題は難しかったはず、と思ってあんまり考えなかったが、難しいのは出ていく人の順番が関係する場合であって、実は最後に残る人だけなら $1\dots a_1-1$ のみだとすぐわかる。

Bは各プレイヤー、自分が2枚持っているカードを優先的に出していく。その枚数を比較して互いに1枚ずつ持つカードがどちらの得点になるかも考えたが、そんなのは当然一致するに決まっていた。余計な場合分けでタイムロス。

Cは $p=(1,\dots,n)$ として $n$ 行目、 $n$ 列目、 $n-1$ 行目、 $n-1$ 列目、……と操作していくと $a_{i,j}=\max(i,j)$ が構築できる。最適っぽさがプンプンするので深く考えずにすぐ出した。その後考えてみたものの証明はよくわからなかった。

Dは長さ $L$ の区間の値を全部 $L$ にすることができる。操作を1点更新だと思い込んでいたが区間更新でも帰納的に示せて、この証明から構築も得られる。あとはどの区間を残すか全探索。操作回数は見積もっておらず、最後に $L=18$ で確認して提出した。

Eは難しい。適当に見積もると、 $O(\sqrt{\max a})$ 回くらい操作した時点で三つ連続して生き残ることはなくなるらしい。例えば $0,x,y,z$ という連続部分列があると、 $t$ ターン後に $y$ が死んでいないなら $z$ は $\sum_{i=1}^t(y-ix)$ だけダメージを受けている。先頭が0でない場合は……知らないがそう大きくなることはないだろう。

とりあえずこれでE1は解ける。700回操作しておいた。E2については、 $z$ が2乗オーダーで減っていくのだからその次の値は3乗オーダーで減るだろうということで、 $O(\sqrt[3]{\max a})$ 回操作することにした。これで最大連続三つとなり、 $z$ の生き死にについては上の式で判定できる。2000回操作してもassertで落ちたので見積もりをやり直したり四つ連続して生き残る間追加でループを回したりしたが、単純に実装ミスだった。

Fは領域に対して辺を張りたくなったので2次元セグ木を用いた区間辺を頑張って書いてみた。コンテスト後追加で1時間格闘し何とかサンプルは合わせたものの、当然のようにTLE。

E2までの6完で、他の人のE2が落ちまくったため11位。ただし間もなく自分のE2もuphackされた。2000回操作した後0を探してそこを起点に見ていったが、探す際にも操作を行わないとちょっとずれてしまう。E1は連続二つしか生き残らないため、そこをミスっていてもうまくいくようだ。

www.youtube.com

なろうを読みふけり、午前10時くらいに寝落ち。

04/14(日)

午後2時過ぎに起きてなろうを読んでいた。ここ数日は「最強魔法師の隠遁計画」を読み返していた。見せ場のシーンを覚えている限りで拾い読みしたが、どれも書籍版の描写に比べるとあっさりしている印象。やはり続刊が待ち遠しい……と思ってHJ文庫の新刊情報を見に行ったら、ちょうど5月に18巻が出るらしい。なんともタイミングの良い話だった。

https://ncode.syosetu.com/n5606cq/

firecross.jp

午後7時からは日記を書き始め、同時並行でラノベも開いた。「凶乱令嬢ニア・リストン」4巻を読了。3巻巻末の予告通り対魔獣・対人ともに大暴れ。侍女を隠れ蓑にしての行動だったため、主人公その人が注目を浴びるような描写は存在しなかったが、それでも無双による満足感はあった。魔獣狩りの描写がかなりスキップされていたのも、むしろ作業感が強くなくて良い。

午前6時半就寝。