12/09(月)

午後1時半起床。定例会が始まる前に学食に行って食事し、購買でラノベを買って帰ってきた。

午後3時半からインターン先定例会に出席。ウズベキスタンから無事帰ってきたと報告した。今週からまた1on1を入れてもらい、少しでも稼働していく所存。勉強会はジップの法則の一般化であるべき乗則について。Barabási–Albert modelという、次数分布がべき乗則に従うランダムグラフ生成モデルを知った。

解散後は週記を書いていたが、実質二日ちょっとしかないのでUniversal Cup以外を早々に書き終え、それからはYandex Cupの参加記のほうを書き進めていた。そちらは完成までまだまだ遠い。日付が変わる直前に週記のほうだけ投稿。

ラノベ「路地裏で拾った女の子がバッドエンド後の乙女ゲームのヒロインだった件」を読んだ。手ひどい裏切りを受けたばかりのはずのヒロインだが、主人公と出会って間もないうちから信用してしまっているように見えて、危機感のなさにちょっと冷や冷やした。

午前5時就寝。

12/10(火)

正午覚醒から二度寝を挟んで午後5時起床。セミナー準備をしなければならないが、とにかくやる気が出ない。布団でスマホを弄り、午後6時を過ぎて閉店直前の購買に駆け込みラノベを受け取った。学食で夕食を摂り帰宅。

ラノベを2冊読んだ。1冊目、「最強の悪役が往く」。ヒロインが複数人登場したが、ほとんどがやたら主人公に執着してベタベタしてくるのであまり好きになれなかった。その点では主人公と契約を結んだメインヒロインは好み。

2冊目、「地味なおじさん、実は英雄でした。」2巻。面白かった。主人公の強さもそうだが、女性関係の枯れっぷりにも安心感がある。

それにしても、このほとんど盗撮みたいな配信スタイルはかなり扱いが難しそう。主人公が配信のことを知らない状態が続くのにも違和感があるし、配信者としての話の展開もかなり制限される。ただ作家がベテランなので、うまく話を転がしてくれるのだろうと期待できる。とりあえず3巻への引きはかなり面白そうだった。

シャワーを浴びて午前6時就寝。

12/11(水)

午前10時起床。もともと今日この時間から留学生のセミナーに参加するという話だったのだが、先生から届いたメールでは木曜日の自分のセミナー後になっており、どちらが正しいかわからない。ということで、十中八九木曜日のほうだろうなとは思いつつ、念のため登校することにしていた。とはいえそういうあいまいな動機ではちゃんと起きられず、セミナー開始時刻の起床と相成ってしまった。

登校してみたら案の定セミナーはなかったので、院生室に移動。ウズベキスタン土産を設置した。これは空港で買ったもので、日本円にして1箱4000円弱する。ビターチョコレート32枚入り。16枚入りだと思って2箱買ってしまったので、1箱は実家に持ち帰ろうと思う。

院生室にお土産設置 pic.twitter.com/dvk1EaZehp
— こたつがめ (@kotatsugame_t) 2024年12月11日

人と話したり昼前に学食に行ったりしていたが、どうにも眠い。家に帰ると夜まで寝てしまうだろうなと思ったので、院生室で少し寝ることにした。

思ったよりしっかり寝てしまい、気づいたら午後3時だった。眠気覚ましで外に出たら路面が濡れていた。少し雨が降ったらしい。原付で登校したので、夜また降られると困る。雪になったらもっと困る。

とは言いつつも、特に帰宅せずそのまま院生室でセミナー準備を行った。午後11時半になってようやく完了。本当は、今日準備した内容は今後使う予定が一切ないので、セミナーで話す必要もない。しかし準備を終えてから気付いてしまったのでどうしようもない。

それから立体四目並べの実装をした。今日は高速化のため、これまでのコードをビットボードによる表現に書き換えた。判定の並列化などにはまだ手を付けていないが、これだけでも少し速くなって面白い。午前2時前に帰宅。路面は乾いていた。

帰宅後にビットボードを用いた処理の並列化をいくつか実装した。またコードをメールで共有するのはさすがに卒業するべきと思い、GitHubに公開した。

GitHub - kotatsugame/yonmoku

午前6時就寝。

12/12(木)

午後0時半起床。さすがにセミナーで話す内容は変えるべきな気がしてきた。読んでいる論文にある別の命題と証明を頭に入れ、考えながら登校。学食で食事しているうちに考えがまとまり、何とか話せるようになった。

午後1時半からセミナー。慌てて準備した内容だが幸い特に勘違いなどはなく、無事話し終えることができた。その後先生とこれから申し込む発表の題目・abstractについて相談していると、5限の時間になった。見覚えのない学生が来たので何かと思ったら、先生が担当している別の講義で追試が発生したらしい。同じ教室で試験を受け始めてびっくりした。まともに集中できたものではないと思う。

それはそれとして5限開始。今日は本題に戻り、学部2年生が課題本「天書の証明」から一つ発表していた。3章の「 $4\le k\le n-4$ のとき $\binom{n}{k}$ は整数の（非自明な）べき乗にならない」である。本で証明の核とされている部分は面白かったが、それ以外は延々不等式評価をしていて、かなり長く非常に疲れた。

学食で食事して院生室へ。今日も立体四目並べの実装をした。リーチがかかったときに勝てる手を列挙するのは、ビットボードとビット演算を駆使するとなかなか高速になった。あとは言われるがままに盤面の評価関数を実装。実際に試し強さをチェックするのは皆に任せっぱなしだった。日付が変わって帰宅しても、もうしばらく実装を続けた。

Yandex Cupの参加記を書き進めた。進捗は全然良くない。今日はブログ更新ページに直接書いていた内容がいつの間にか消えており、ショックを受けた。投稿済みのブログだと当然下書き保存はできないので、今後は別のところに保存するようにしたい。

午前7時半就寝。

12/13(金)

午後3時前に起床。1時間ほど1on1をし、タスクをいただいた。

シャワーを浴びて大学生協へ。今週末のTTPCと来週末のICPCで2回東京に行くため、その新幹線切符を買った。今週末の切符はさすがに直前すぎたらしく、帰りの席は3人掛けの真ん中になってしまった。それから学食で食事。

このときLINEが来て、立体四目並べの強いAIがつい最近公開されていることを教えてもらった。当然ビットボードを使っているし、ゲーム木で真面目に戦略を考えており、完敗という感じ。ただ判定の並列化まではしていないようだ。

note.com

帰宅せずそのまま地下鉄に乗って仙台駅まで出た。本屋とドラッグストアに寄りつつゲーセンへ。大型アップデート翌日だったが待ちは多くて三人というところで、閉店までの4時間ちょっとで22クレ遊べた。

新曲をいくらか埋めて、成果は理論値8個、14+のAJ二つ。「Igallta」は最後のトリルを全力で押すと微妙に追い越してしまうらしく、速さを理解するまで全部赤になってかなり大変だった。ちょっと前に14+のAJが99個になってウキウキしていたが、バージョンアップで譜面定数を全体的に高くされ、今日見たら101個になっていた。きれいにキリ番が消えてしまい残念。

今日は22クレ　理論値8個 pic.twitter.com/zaARdfmVRb
— こたつがめ (@kotatsugame_t) 2024年12月13日

ラーメンを食べ、ドンキとコンビニに寄って帰宅。

Universal Cup Finalsのフライトを他の日本人参加者とすり合わせた。羽田空港から香港国際空港と、その逆。実はなんとも都合の良いことに、ちょうど同じくらいの時間に仙台空港と香港国際空港を結ぶ便も存在し、それを使えば仙台と羽田を自腹で往復する必要がなくなる。ただ、他の参加者と合わせずとも香港くらい一人で行ける気がするが、安心を買うことにした。

日記を書いて午前8時前就寝。

12/14(土)

午後4時起床。夕方までゲーセンに行くつもりだったがもうそんな時間ではない。夜は院生室で環境構築の手伝いをする予定がある。昨日見つかったAIを動かしてみたいらしい。g++はあるので、makeコマンドをインストールさせて基本的な操作を教えれば終わりだろう。ABCの時間には十分間に合うはず。しばらく布団でなろうを読み、午後6時過ぎに登校した。

環境構築はすぐ終わったが、動かしたいプログラムが日本語を出力しており、文字化けで苦しんだ。コマンドプロンプトの文字コードをUTF-8に切り替えてもダメ。コンパイラのほうで弄る方法もあることに気づき、オプション-fexec-charset=cp932を指定することでなんとか解決した。

帰宅して午後9時からABC384。

Toyota Programming Contest 2024#12（AtCoder Beginner Contest 384） - AtCoder

A、B、Cはよい。Dは長さ $N$ のブロックからはみ出したprefixとsuffixをそれぞれ考えたが、ブロックは適当にずらせるのだから、どちらか片方を空としてよかった。Eは優先度付きキューでBFS。

Fは $k\ge 0$ について $2^k$ で割り切れる $A_i+A_j$ の和を求め、足し引きして解いた。しかしあまりにも適当に実装した結果、mapを使っていて遅いのと不要な $k$ まで調べているのとでTLE。 $k$ の範囲を絞り、存在しない要素でmapにアクセスするのを止めたら通った。

GはMo's Algorithm。最近次のようなツイートを見たので、ドンピシャだなと思いながら解いた。

これは予測ですが、ABC は 100 回周期で全ての基礎アルゴリズムを網羅することを目指してるぽいので、Mo's が想定解になる問題が ABC392 までに出る
（最後が ABC293-G のはず、違ってたら教えて欲しい）
— ryusuke (@ryusuke__h) 2024年11月25日

全完11位。AをNibblesで縮めた。 $S$ の各文字について1行目におけるインデックスを求めると、出現しない文字には0が返ってくるが、これはPythonにおける-1のようなもので $c_2$ のインデックスにもなる。よってそのまま添え字として使えばよい。

www.youtube.com

部屋が寒くてなかなかシャワーを浴びる気になれず、ダラダラなろうを読んでいたら午前4時を回ってしまった。明日はTTPCに現地参加するため早起きしなければならない。慌ててシャワーを浴び、午前5時就寝。

12/15(日)

今日はTTPC2024。

TTPC2024 - connpass

午前8時起床。荷物を準備して家を出た。会場の教室の椅子が固いとのことで、運営がクッション持参を推奨していたが、荷物になるので自分の臀部を信じ持っていかなかった。

仙台駅構内で立ち食いそばを食べた。朝から新幹線に乗るときはたいてい食べているが、いい加減このそばが口に合わないことに気づいてきた。少し太めの麺はブニブニした食感で、汁の中で絡み合いうまくすすれない。もうちょっと早めに駅まで来て、少し歩いて「そばの神田」に行くようにしたい。

午前9時半発のはやぶさで東京へ。車内では寝ていた。午前11時過ぎに東京駅に着き、そこから大井町駅での乗り換えを挟み大岡山駅まで移動。記憶が正しければ、ここに来たのは2017年のSuperCon以来である。東京科学大学のプレートの写真を撮り、connpassページの案内をガン見しながら会場へ移動した。

正午少し前に到着したらもう開場していた。教室入り口で名札を貰ったが、アイコンがデフォルトのものになっていた。名札のアイコンについてはconnpassでの参加登録時に選択肢がいくつかあったはずで、そこで自分はデフォルトのまま変えていないことを忘れてAtCoderのアイコンを選んだらしい。もう何も覚えていない。

立ち歩く時の利便性を考えて最後尾の長机を確保し、持参した延長ケーブルを這わせるなど用意を整えていたら、noya2さんに話しかけられてサインをお願いされた。あとはmtsdさんと話していた。

#TTPC2024 pic.twitter.com/Jf9N8xjD2p
— こたつがめ (@kotatsugame_t) 2024年12月15日

ぼちぼちチームメイトも集まり午後1時にコンテスト開始。我々japan406364961はUniversal Cupのほうで参加した。こちらは日本語問題文が提供されなかった。また一度はAtCoderの順位表を見てはいけないと通達されたのだが、教室前方スクリーンに順位表の1ページ目が表示されており、それなら見てもよいという話になった。

https://qoj.ac/contest/1872

今回のセットは簡単枠が存在せず、序盤の順位表に動きがほとんどなくてかなり苦しい立ち上がりだった。F問題が8分で解かれたのでrisujirohさんが読みに行ったが、まったく解けるようには見えないらしい。実際、この速度で解かれたのは既出だったからのようだ。

Symmetry: Closure - Problem - Universal Cup Judging System

しかし我々はギャグであることを疑いしばらく粘着していた。というのもスクリーンの順位表では、すなわちAtCoder上では続々とF問題が解かれていたのである。しかししばらくしてその順位表がdiv.2のものであることに気づき、ようやく諦めがついた。

ぼちぼちACが出始めてもまだ各問題一桁ACで、どれに取り組むべきか区別がつかない。自分はB、risujirohさんはE、NyaanさんはLを考えていたはず。結局最初の1時間はPCを使わなかった。

Bは後ろから考えるとよい。まず1が末尾にしかないことに気づき、とりあえず末尾が1のケースを解いた。こちらはそこそこ簡単で、3の連結成分に対しカタラン数を掛け合わせればよい。ところが末尾が1でないケースはもうちょっと面倒らしい。正確には、最後に $C=3$ となった直後の $A$ が $2,2,\dots$ であるようなケースが問題。

ウンウンうなっていたらCも同じくらい解かれ始めた。確認すると見覚えのある問題設定。たしかUCのどこかでやったことがあるはずで、セグ木のノードについてその両端に移動するまでの距離をそれぞれ管理し、適当にマージなり親への移動なりをしていくとよい。雰囲気で書いてサンプルを合わせたら通った。

NyaanさんがLを通し、risujirohさんのEが落ちたのを尻目にBの解法を詰めた。冷静になるとカタラン数が出てくるのは当たり前で、グリッド上の移動を考えると問題だったケースも数えられる。丁寧に実装した後、さすがに自信がないので愚直を書いたら、見事一発で合っていた。提出してAC。

次はEのhelpに回った。解法を聞くとそれっぽい貪欲ではあったが、計算量が $O(N)$ で何かおかしい。落ちるケースを見つけたので、それに対応できる $O(N^3)$ の解法という線で考えを進めた。履歴を管理する貪欲に考えを引っ張られつつも何とか区間dpにたどり着き、そんな面倒な遷移はしなくてよいだろうという読みで思いついたそれっぽいものをrisujirohさんに伝えた。トイレに行って帰ってきたら通っていた。

次に通ったのはNyaanさんのM。これは論文ゲーだったらしく、Cartesian Treeが一致する条件が以下の定理3に書かれている。あとはあんまり工夫せず $O(N\log N)$ になるらしい。

[1905.08974] Cartesian Tree Matching and Indexing

その間自分はrisujirohさんとAを考えていた。言われた通り構築することも少し考えたが、こちらは何をすればいいのか全く分からない。辺を1本ずつ消す方針で解けた。まず橋は無視できるので、グラフを2辺連結としてよい。このとき、消す辺の端点に次数3以上のものがあると、その頂点は2辺連結であることから存在を保証される閉路に含まれており、条件を満たさない。よって次数2の点同士を結ぶもののみが消せる。これを $O(m)$ 回繰り返す。

最後に取り組んだのはFで、これもrisujirohさんと。1次元の場合は簡単で $2\gcd(x)$ 周期の話になる。これで $X$ 軸・ $Y$ 軸に平行な直線しかない場合は解ける。そうでない場合が問題。

点を移すだけでなく、軸となる直線そのものを別の直線を軸として移して考えてみる。サンプルの二つ目は、斜めの直線が $X$ 軸と有理数でない角度で交わっている。このとき、直線を移すのを何回も繰り返すと、交点を通る任意の直線を軸として使用できるようになると気づいた。そのような交点は $Y$ 軸との交わりも合わせて二つあるので、任意の点を任意の点に移せる。

今直線の傾きの $\tan$ が有理数なので、0度・45度・90度という自明な角度以外はこれが適用できるらしい。そのような斜めの直線が存在する場合をまず考える。その直線が原点を通っていなければ、サンプル2と同様なんでもできる。原点を通っていても、ほかに $X$ 軸・ $Y$ 軸に平行な直線があれば同じこと。そうでないとき、つまりすべての直線が原点を通るとき、原点からの距離が一致していることが必要十分条件になる。

傾き45度の直線がある場合が最後に残った。適当に反転して、直線 $x+y=a$ があるものとすると簡単。このとき $X$ 軸平行の直線と $Y$ 軸平行の直線を同一視でき、さらに直線 $x=a$ 、 $y=a$ があると思える。よって正方形領域の周期が続く形になり、傾き45度の直線は重複を除いて高々2本、 $x+y=0,\gcd$ しかありえない。

risujirohさんによれば斜めの直線を使う回数は高々1回らしいので、2²通り全探索できる。あとは $X$ 軸・ $Y$ 軸に平行な直線しかない場合と同様。これらの場合分けを紙で丁寧に詰めて実装し、サンプルを合わせて投げると……WA！

残り20分ちょっとしかない。NyaanさんがJを解けていたのでPCを交代し、コードをにらんだ。すると実装ミスが二つ見つかった。少しPCを空けてもらって書き直し、再度投げると見事AC。小躍りした。

残りの時間はNyaanさんを応援していたが、残念ながら実装ミスが取り切れなかったらしく、ACならず。その後9分ちょっと遅れて通っていた。そのくらいの時間であれば、例えばF問題の実装をもう少し早く始めるなどでいくらでも捻出できたはず。非常に残念。

結果はCLBEMAFの7完で11位。7完のチーム中でペナが最大なので、もう一問通せていれば大きく違っただろう。

AtCoder側の順位表はUCのものとかなり雰囲気が異なる。Mが解かれておらず、JのACが結構多い。Nyaanさんが最後Jに取り組んでいたのもこの順位表を見てのものであり、情報が真に多いことは明確に有利だった。

7完までの速度差でsemiexpさんに、部分点でチーム🇧🇴liviaに負けた。しかし結果発表では我々のチームが1位だとされていて謎。聞くところによると、AtCoderのdiv.1とUCの結果を混ぜる際、部分点を無視し、最後にACした時刻のみ・ペナなしで順位を付けたらしい。

懇親会ではlumaさんに話しかけてもらったほか、もっぱらUniversal Cup勢と話していた。会場が午後8時に閉まり、夕食でもどうですかという感じになって駅前のサイゼに移動。メンバーはチームjapan406364961、チームtritr、Rubikunさんの7名。昨日のAJO決勝の余興について、Twitterで内容が一切流れてこないので一体何だったのか聞いてみたが、口止めされていそうな雰囲気だった。

新幹線の終電があるため自分だけ午後8時40分に離脱。ちょっと余裕を持って出たら1分での乗り換えに成功したりして、思ったより早く東京駅までたどり着けた。午後9時36分、満員のはやぶさで仙台へ。車内では寝ていた。

午後11時半帰宅。何とか間に合ったのでCF #993 div.4に参加した。

Dashboard - Codeforces Round 993 (Div. 4) - Codeforces

Aはよい。Bは正確な定義がないが雰囲気で。Cもよい。Dは順列にするギャグであると気付くまで時間がかかった。Eは算数。Fはすべての $x$ に対して予め判定する。同じ $a_r$ を何度も調べないようにすれば、調和級数で十分高速になる。

Gは二つに分かれている。G2から解いたが、G1とは異なる問題だった。どちらもサイクルの外が消えるまでの時間を求めればよく、G1は深さ、G2は木の頂点数になる。G2でサイクルの同じ頂点から生えている複数の木をまとめてしまい1WA。Hは二次元累積和。

全完10位。

www.youtube.com

日記を書いて午前9時就寝。