01/20(月)

午後3時過ぎ起床。半からインターン先定例会に出た。

昨日寝る前に少し作業をしたのでその進捗を報告。何をすればいいかが明らかだった準備段階は終わり、この先はいろいろ考えながら進める必要があって大変そう。勉強会はゲーム木探索の手法についてだった。自分が昨年末から院生室で書いている四目並べのAIは、いまだに適当な深さまでdfsで潜っているだけなので、このような手法を実装する下地すらない。

解散後、閉店間際の購買に駆け込んでラノベを購入。先日注文したものが一気に届いたため19冊溜まっており、レジをかなり詰まらせてしまった。学食で食事して帰宅。

└( ＾ω＾ )┘♪ 買った♪└( ＾ω＾ )┘♪ 買った♪ pic.twitter.com/SzF6zNn7ne
— こたつがめ (@kotatsugame_t) 2025年1月20日

深夜まで先週の週記を書き、午後11時半に切り上げて投稿。CF #999 combinedに出た。このコンテストは香港で行われるオンサイトの予選らしいが、その日程02/27-03/02はICPC プレーオフと完全に重なっている。

Dashboard - IAEPC Preliminary Contest (Codeforces Round 999, Div. 1 + Div. 2) - Codeforces

書く

www.youtube.com

シャワーを浴びた後は論文修正に取り組み、午前10時就寝。

01/21(火)

午後4時起床。すぐ地下鉄で登校し、何とか事務室が閉まる前に先週届いたiPadと教科書を受け取れた。

注文したiPadと教科書1冊が事務室に届いたらしい
週記（2025/01/13-2025/01/19） - kotatsugameの日記

✌ pic.twitter.com/zXnJyoaXch
— こたつがめ (@kotatsugame_t) 2025年1月21日

院生室に移動して、まずiPadにガラスフィルムを貼った。これも一緒に注文したもの。貼る際のガイド枠や画面を清掃するおしぼり・クリーナー・粘着シールが付属しており、埃っぽい部屋でも無事綺麗に貼り付けることに成功した。

そのあとは人と話しながらポチポチ設定を行った。Apple製のアプリを使う人はあまりいないようで、自分も軒並みアンインストールしたうえGoogle製のものを入れていった。アプリストアのトップページにはデカデカと有名ゲームタイトルが並んでいて、興味を惹かれること甚だしかったが、入れたら最後プレイを止められなくなることは目に見えていたので必死に自制した。

午後7時くらいに学食で食事してからは四目並べの話をしていた。コードに埋め込んだパラメータを昨年から延々手作業で最適化してくれている友人がおり、現在最強のものを写させてもらった。彼は今M2で、修論執筆の息抜きとしてやっていたそうだ。それに見合うだけの熱意をこちらが持ち合わせておらず、彼の作業の効率化は全然できていない。

update weights · kotatsugame/yonmoku@aa5ea0c · GitHub

終電1本前に乗り、コンビニに寄って帰宅。午前1時就寝。

01/22(水)

午前4時に目を覚ました。

DDCCがDECCと名を変えつつ今年も開催されるらしい。ところが本戦開催日の03/23はちょうどTUPC2024の日。4連続で本戦に参加できているので残念ではあるが、今年は不参加となる。

DISCO Equipment Coding Contest コードで装置を意のままに。 | マイナビニュース

夜までずっと寝たり起きたりしながらなろうを読んでいた。夜にCFがあることは知っていたものの、いつもより早い午後9時開始であることをすっかり忘れており、30分前にふとclist.byを確認して気づいた。慌てて起床し、シャワーを浴びてCF #1000 div.2。ついにラウンド1000。

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

Aは基本的に長さ2の区間を数えればよく、 $[1,1]$ だけ特別扱い。答えがずれるのは $(l,r)=(1,1)$ のケースのみである。Bは区間内と区間の右、あるいは左どちらかから同じ数だけ要素を選んでswapだと思える。Cは選んだ2頂点の次数から1または2を引く。dfsしながら求めた。

Dは上向きの三角形と下向きの三角形をそれぞれいくつ作るか決めれば面積の最大化は自明。そして作る個数については、面積が最大の三角形を貪欲に作るケースか、あるいはどちらか一方が上限ギリギリになるケースのみ試せば十分である。

Eは非常に面白かった。 $\operatorname{lca}(u,v)=:w$ としたとき $f(u,v)=2\min(\operatorname{dist}(w,u),\operatorname{dist}(w,v))-1$ である。ここで $\min(\operatorname{dist}(w,u),\operatorname{dist}(w,v))$ を $w$ と $u$ 、 $v$ の間にある同じ深さの辺で作ったペアの数と見て、逆に同じ深さの辺のペアに対してそれをカウントする $(u,v)$ を数える。この値は部分木のサイズの積になる。

Fは区間の重なり具合で各位置を分類し、それぞれで正しい括弧列を作ればよい。クエリを逆順に処理した。最初に括弧列から木を作り、ノードが消える度上下を圧縮し、さらに自由になったぶんの長さを親ノードに足していく。こうして管理している長さが区間の重なり具合による分類に対応している。

72分で全完して10位。div.2にしては序盤が結構大変だった。

www.youtube.com

午後11時半からCodechef Starters 170に参加した。おそらく毎週開催されるこのコンテストを回避するためにCFが前にずれたのだろう。

https://www.codechef.com/START170A

書く

ラノベ「なぜ逃げるんだい？僕の召喚獣は可愛いよ」を読了。妙にのんきで快活な主人公と周囲のギャップが良いなと思った。ただしそのギャップの原因、例えば主人公と周囲の認識はどこが食い違っているのかや、召喚獣は主人公のことをなぜ好ましく思っているのかが最後まで全く明かされなかったため、釈然としない読了感。

召喚獣の話す言葉は、主人公視点でのみ日本語訳を併記されていたが、おそらく常にUTF-8→Shift_JISの文字化けとして復元すると意味の通るものが書かれていたはず。電子書籍を買った気合いのある人は全部読めるのだろう。

もう一冊、「戦地から帰ってきたタカシ君。普通に高校生活を送りたい」2巻も読んだ。コテコテのテンプレ展開すぎて逆に恥ずかしい、みたいなボーダーのギリギリ手前という感じがした。

論文修正作業をしてついにarXivに投稿した。Overleafの日本語対応のために用意したlatexmkrcをずっと使い続けていたため、arXivと環境が食い違ってTikZが壊れてしまったが、幸いlatexmkrcを消したらOverleafでも同じ壊れ方をしてくれたので、デバッグはやりやすかった。\documentclassのオプションでdvipdfmxを指定せよという記事を見つけて、指定しているけど……と思いつつ試しに削除してみたら動いた。

午後1時就寝。

01/23(木)

午後7時起床。

「モンスターの肉を食っていたら王位に就いた件」4巻を読んだ。面白かった。やはりフラウが好み。主人公との関りが一番深く、内心を理解している様子だし、また設定上主人公の様子を常に監視することができるため、何を知っていても不自然ではない。この巻のラストもフラウが転移で主人公を迎えに来たことでオチが付いた。もはや何でもあり。

3月頭の北海道の研究集会では自分も発表することになっており、それに向けたテクニカルレポートを提出する必要がある。期限は今週金曜日まで、つまり残り24時間しかない。昨日少しだけ書いてみた程度の進み具合なので大変まずい。夜中からずっと執筆していた。

合間に「世界で一番『可愛い』雨宮さん、二番目は俺。」3巻を読了。前巻から1年以上空いたものの無事続刊し、校内四大美少女がついに全員揃った。Web版だと連載中の四章に相当する。この章は最初の1話を除いて書籍1巻が出たのと同じタイミングでスタートしたのだが、ついに書籍版に追いつかれてしまったこととなる。このあたりが刊行に時間がかかっている原因かもしれない。

朝までキーボードを叩いていたがまだしばらくかかりそう。夕方から大学でセミナーを聞きに行きたいとも思っていたため、徹夜することに決めた。日記の日付はここで変えておく。

01/24(金)

昼過ぎになってテクニカルレポートの内容がようやく形になった。あとは文章を直し、例や図を追加すればよいはず。夕方のセミナーに向け、残りの作業は大学で行うこととした。

シャワーを浴びて学食に行った。麺コーナーがセルフレジになっていてびっくりした。食後にラノベを購入。9冊もあったので一旦帰宅して荷物を置き、また登校した。

麺コーナーがセルフレジになってた pic.twitter.com/tR1IiEi4Kn
— こたつがめ (@kotatsugame_t) 2025年1月24日

arXivに投稿した論文、正確にはpreprintが公開された。理論での貢献ではなく数値計算の結果をまとめているだけだが、既知の事実からすぐ出るようなものではないし、計算も別にやるだけではなかったので、春に投稿した修論の内容よりは自信がある。

arxiv.org

かなり大きな多変数多項式行列が正則でないことをdeterministicに示そうとしています（3.2章）。運ゲーみたいなことをしているので、まともな方法を募集中です https://t.co/dT43qCMQb2
— こたつがめ (@kotatsugame_t) 2025年1月24日

このpreprintも引用しつつテクニカルレポートを書き進めた。院生室だと周囲の人と話してしまうためそこまで捗らないが、締め切りには間に合いそうだったので別室に引きこもるほどではなかった。

午後4時半から確率論セミナー。今日の内容はM2三名の修論発表の練習。今日の発表者たちは昨年度自分のセミナーに来て発表してくれたし、修論の要旨を見るとそのとき扱っていた内容をずっと続けていたらしく興味もあったため、顔を出した。一部組合せ論的な話もあって非常に面白かった。セミナー後に声を掛けたら詳しい話を聞かせてもらえて嬉しい。結構な時間拘束してしまったのは申し訳なかった。

午後7時に解散して学食で食事。院生室に戻ってテクニカルレポートの仕上げに取り組んだ。今日はみんな普段より早い時間に帰ったため、夜遅くになると集中して黙々と作業を進めることができた。ギリギリまで見直しをして、日付が変わる直前に提出した。

全員帰ったと思っていたら、図書館で勉強していた人が閉館時間となって追い出されてきた。彼としばらく喋り、午前1時半に帰宅。すぐ寝た。

01/25(土)

午前6時半に目を覚ました。スマホでハーメルンを読んだりYouTubeを眺めたりしていたら二度寝できず、そのまま昼になってしまった。

午後0時半からyukicoderで「第1回岩井星人アンソロジープログラミングコンテスト」があったため参加した。

第1回岩井星人アンソロジープログラミングコンテスト - yukicoder

FGHIBCDEAの順、つまりレベルの降順＋タイブレークを問題の昇順として解いた。

Fは端から貪欲に操作。Gは左右から累積和。Hは毎回答えるのを見落として実装やり直しになり、結構時間がかかった。Iは常に2回でできる。Bはたまご2個で強度を計る話かと思ったら全然違った。Cはサンプルの図を睨みながら頑張る。Dは星1.5ならdijkstraだろうなと思って読み、実際にそうだった。Eはdp。 $C$ の制約がやたら大きいのは嫌がらせか？Aは入力フォーマットとサンプルが食い違っていたらしいが、自分が解くころには直っていた。

FGHでFAを取って優勝。

シャワーを浴び、午後2時からUniversal Cupに参加した。今日は27回目のLondonセット。

https://qoj.ac/contest/1901

書く

論文でやっていることが名前の付いた問題だということを教えていただいた。このことは論文に書いておく必要がある。また、サーベイするともしかしたら自分と同じ手法で取り組んでいる論文が出てくるかもしれない。非常にありがたいご指摘。

ネガティブな参考情報ですが、次数を 1 に限定したものは (decision version of) Edmonds' problem と呼ばれていて、例えば https://t.co/VOUgN4oUNr のイントロ最初の二段落は参考になるかもしれません。
— Mori (@Ryuhei_Mori) 2025年1月25日

午後9時からABC390に出た。

AtCoder Beginner Contest 390 - AtCoder

A、Bはよい。Cは極小な長方形を作る。Dは全探索。Eは二分探索に見えるが、3種それぞれdpした後は全探索でよい。Fは操作 $(l,r)$ に対して区間右端の $l$ をマークし、このマークを数えた。 $R$ をfixすると、各要素についてそれがマークされる $L$ が区間になり、更新も定数時間で行える。

Gは数を桁数で分類して扱う。ある数が総和にどれだけ寄与するか求めるには、桁数 $i$ の数が右に $k_i$ 個来るとして $\sum k_i$ と $\sum ik_i$ が必要。しかしよく見ると後者は $10$ のべき乗という形でのみ寄与するため、最初から $\prod 10^{ik_i}$ として係数に掛けておくとわざわざ値を持つ必要がなくなる。これで1変数の畳み込みになった。

38分でノーペナ全完し3位。D問題はsetを使うとTLEする問題だったらしい。自分はたまたまvector＋sortを使っていたためセーフだった。コードゴルフはAのみで、 $\sum|A_i-i|=2$ であるか判定するコードをNibblesで書いた。

www.youtube.com

yukicoderのリジャッジで落ちた問題が6問溜まっていて、そのうち5問を埋め直した。怪しいテクで縮めたコードしか提出しておらず、言語アップデートでREになったものもあれば、単純に当時解けなくて嘘で無理やり通したものもある。後者もスイスイ解けるようになっていて感動した。

午前3時就寝。

01/26(日)

午前9時半に目を覚ました。

昨日のUCが通常とはかなり異なる雰囲気の問題ばかり集めていたこと、またそれらの問題の質について、公式Discordで盛んに議論が交わされていた。そこで知ったが、F問題の問題文中にもヒントが隠されていたらしい。この問題は $O(nq)$ のベクトル化を要求する問題で、実際「パスに値を加算する」クエリが変数 $a,v,x$ で表現されていることからavxに思い至れるというもの。しょーもな。

2時間ほどで二度寝し、次に起きたら午後7時過ぎだった。食事してシャワーを浴び、午後9時からARC191 div.2。

AtCoder Regular Contest 191 (Div. 2) - AtCoder

Aは適当な貪欲を書いたらサンプル2で落ちて、「必ず書き換えなければならない」ことに気づいた。必ず $T_M$ が現れるようにして提出。無理やりサンプルを合わせようとした感じの修正だったので不安だったが、無事通った。

Bは $r:=X\bmod N$ を固定して考える。条件は $(N\oplus r)\equiv r\pmod{N}$ であり、 $(N\oplus r)=N+r-2(N\mathbin{\operatorname{AND}}r)$ と $r\lt N$ より $(N\mathbin{\operatorname{AND}}r)=0,N/2$ が得られる。 $N/2$ となることはあり得ないので $(N\mathbin{\operatorname{AND}}r)=0$ のみが条件となり、 $N$ で立っていないbitを取り出すなどすれば $K$ 番目が簡単に求まる。

Cは大変だった。 $M=kN+1$ を素数となるように取り、法 $M$ での原始根 $g$ を求めて $g^k$ を出力するという方針を思いついたのだが、素数判定を試し割りで行ったのが論外でTLE。仕方なくカーマイケル関数 $\lambda(M)$ が $N$ の倍数となるような $M$ を取って同様のことを行った。ちなみにそのような $M$ は $N$ に $N$ の素因数を掛けることで構成され、もっと言うと $M=N^2$ がvalidである。

Dは頑張る。 $ST$ 最短距離を $D$ としたとき、最短パスが2種類以上あるなら $2D$ 、そうでなくて距離 $D+1$ のパスがあるなら $2D+1$ が答え。さらに $ST$ 最短パスの途中の頂点が次数3以上になっていれば $2D+2$ が達成できる。

これらのケースを除くと、 $ST$ 最短パスがグラフにおいてほぼ孤立していることがわかる。このパスを一旦削除すると次に短い $ST$ パスが求まり、その距離と $D$ の和は答えの候補。さらに $S$ または $T$ の近くに次数3以上の頂点があれば、そこから伸びた辺2本を使って二つのコマがすれ違える。この二つのMINが答え。

残り20分弱でEに進んだ。解かれ具合に比して思いのほか簡単だったが、残念ながら間に合わず。まず一つの袋に注目すると、その袋を使って操作する回数は最初に持っていた人のほうが相手より1回多くなるか、そうでないかの二通りしかありえない。そして袋同士は独立であるから、操作回数が相手より1回多くなる袋を多く持っているほうの勝ちだとわかる。

よってそれぞれの袋について解きたい。よく考えると結局銀貨の枚数の偶奇で決まるのだから、 $X$ と $Y$ も偶奇だけ考えればよさそう。そこで4通りに対して実験してみると、かなり単純な法則性を見出すことができた。それぞれの袋について高橋君・青木君が取った場合の結果を求めると、袋は4種類に分類できる。あとは適当に畳み込みで数え上げが完了する。

3分遅れで書き上げたものはWAだったが、 $2A+B$ をint型で計算したことによるオーバーフローだった。テストケースの名前を見て $X\equiv Y\equiv 1$ のケースでのみ落ちていることを把握した状態からこのオーバーフローに気づくまで、追加で7分弱。これがロスタイム10分で通ったと言えるかは微妙。

4完33位。東北大学の人が自分より上に3人もおり、しかも全員C問題をwriter解で通していてひっくり返った。AGCの構築でも負けがちだし、こういうアイディア勝負が自分はかなり苦手らしい。

振り返りをするには時間が足りなかったので、CFが終わった後別撮りして編集でくっつけた。

www.youtube.com

午後11時半からはCF #1001 combined。#999もcombinedだったのに#1000だけdiv.2というのは、記念すべき回にしては格が足りなかったんじゃないの、という気持ちが少しある。

Dashboard - Ethflow Round 1 (Codeforces Round 1001, Div. 1 + Div. 2) - Codeforces

書く

www.youtube.com

朝は日記を書いていた。午前10時くらいに学食で食事し、帰宅して就寝。