11/25(月)

午後3時半起床。インターン先定例会に出席した。

研究における特大のイベントは先週で一段落したはず、ということで今週から稼働を再開したい。とりあえずタスクの確認のために1on1をお願いした。ただ、来週一週間はYandex Cupに参加しているのだが……。勉強会はCursorというAIと連携したエディタの紹介だった。自分はそもそもAIをほとんど使わないので、まともなコードが生成されていくのを見るだけでびっくり仰天してしまう。

午後9時半まで先週の週記を書いて、投稿し、TROC #41に出た。もともと日曜日午後6時からの予定だったが、CFの5hと被ったのでずらしたらしい。この5hは午後4時5分から午後9時5分で、さすがにAGC前に走る気にはなれなかった。

https://tlx.toki.id/contests/troc-41

Aはよい。Bは初項 $a$ と公差 $d$ について $N\times a+N(N-1)/2\times d=M$ を拡張ユークリッドの互除法で解く。係数が大きいように見えても実際は $N$ または $N/2$ で割り切れるため、解が存在すれば $|A|\le 10^{18}$ は十分満たす。Cはギャグで $\max x$ と $\min x$ の中点。

Dは最初のステップで作った $0$ をどんどん後ろにずらしていくことになる。また、最初のステップは最小値二つを足し合わせるのがよい。Eはsatayを順に見てひっくり返した時間の集合を管理しながら差分更新するだけ。

ここまでかなり早かったらしい。Cのギャグには反応が遅れてしまったが、ABDEの4問はFAだった。

Fは面倒。答えを $x_0,\dots,x_{N-1}$ とおくと $C_i\equiv x_i+\dots+x_{i+T-1}\pmod K$ で、 $C_i=C_{i+1}\pm 1$ なら $x_i$ と $x_{i+T}$ がそれぞれ確定し、 $C_i=C_{i+1}$ のときは $x_i=x_{i+T}$ だけ分かる。これらの情報をまとめると、未確定の $x$ は等しいと判明しているもののグループに分かれる。

このグループは、 $g:=\gcd(N,T)$ とすると $x_j,x_{j+g},x_{j+2g},\dots$ という形をしている。つまり任意の $i$ について $C_i$ への寄与が $T/g$ となるから、validな割り当てを求めるのに部分和問題を解く必要がない。未確定の $x$ をいったん $0$ として足りない数 $v$ を求め、 $T/g$ で割った数のグループを改めて $1$ とする。

ただし $C$ から計算できるのが $v$ そのものではなく $v\bmod K$ であることに注意。自分はここで1ペナ＋20分消費してしまった。

Gは解けず。すごいデータ構造を使うものと勝手に思い込んで、ずっと2乗の解法を高速化していた。最終的に全完が6人出て、自分は7位。レートは3031→3030(-1)となった。Gは解説を開いたら重心分解と書いてあって卒倒。反省しながらupsolveした。うしさんのCHTを窃盗してくれば、他の実装はそんなに大変ではなかった。

少し日記を書いて午前1時半就寝。

11/26(火)

午前7時半起床。少しハーメルンを読んで、午前10時から午後1時半まで二度寝した。

Yandex Cupの旅程を確認した。今週末、日曜日の深夜午前2時に出る飛行機に乗る予定。そこから逆算して、東京駅に午後10時ごろ着くような新幹線を取ることにした。また12/06の帰りについては往復乗車券の有効期限ギリギリだったが、別に往復割引があるわけでもないので分けて買い、日程に余裕を持たせることにした。

決めるべきことを決めたので大学へ行き、生協で切符を購入。その後散髪と食事を済ませて帰宅した。今日は「サンキュー！夕食」というキャンペーンで定食が390円になっていた。お金に困っているわけではない身でこういう値引きの恩恵にあずかるのはちょっと罪悪感があるが、ほかに食べたいメニューもないししょうがない。

帰宅してシャワーを浴びたあと、先週のAGC-Dをupsolveした。小さい番号の頂点だけ考えたときにいくつの連結成分ができていて、何本の辺が大きな番号の頂点へ出ているかを状態に持つdp。 $O(N^4)$ を適当に高速化して $N$ を一つ落とす。連結成分数は一意に決まらなそうだが、できるだけ大きくして問題ないようだった。

先ほど床屋で考えていたら、わりとすぐに正しそうな方針を引き当ててびっくりした。実装してみたらサンプルが一発で合ってさらにびっくり。これなら本番Dに行くべきだったなと思うも、コンテスト後のTLでDの解法ツイートを見たような記憶もあって、もしかしたらそれが考察に影響したのかも。終わったコンテストの難易度見積もりは不可能。

atcoder.jp

日記を書いたりなろうを読んだりして、眠気に逆らわず午後11時就寝。

11/27(水)

午前3時から3時間ほどなろうを読んでいたらしい。午前10時起床。今日は夜からホスフィンと食事、そして家飲みをする予定である。

午前中は指導教員から降ってきた解析学の問題を解いていた。Wolfram|Alphaで検算しようとしたら全然クエリを理解してくれなくて大変だった。午後からはなろうを読んだり、部屋の掃除をしたり。すると明日のセミナー準備をする時間がなくなって、1時間ほどで先週のワークショップのフォローアップみたいなものをでっち上げた。

午後5時過ぎに出発。仙台駅前でホスフィンと合流し、「別館すが井」というあなご料理の専門店に入った。季節のおまかせコース・松の全九品に加え、あなご酒・サラダ・ふろふき大根・自家製シャーベットを食べた。

食事 pic.twitter.com/0HNN8k60bj
— こたつがめ (@kotatsugame_t) 2024年11月27日

着席したらすでに四品ほどセットされていた。正面の空いたスペースに何か来るのかと思ったが、食べるペースが早かったためかそういうことはなかった。写真1枚目の右端から白子とあん肝、お造り盛り合わせ、穴子一本すし、茶碗蒸し。茶碗蒸しは下のほうにご飯か白身魚かが入っていて、非常においしかった。

あなご酒は飲む前にマッチで火が付けられた。どうやらこれによってアルコールが少し飛んだとのことだが、自分は相変わらず日本酒の苦さにやられており、よくわからなかった。飲み切った後に残った穴子を少し齧ってみたら、乾いて味が薄く食べられたものではなかった。味がちゃんとお酒のほうに移っていたらしい。

椀物のつみれは手間暇かかっており、骨がすっかり取り除かれていたのか非常に柔らかく食べやすかった。写真4枚目は塩焼きと蒲焼き。塩焼きは薄めの味付けで、右下のわさびやしょうがが合う。自分は蒲焼きより好きだった。試しに蒲焼きにしょうがを付けて食べてみたら全然ダメで、そちらには山椒でなければならない理由があるんだなと思った。

食事 pic.twitter.com/XN8J9b7VU1
— こたつがめ (@kotatsugame_t) 2024年11月27日

追加注文のサラダ。散らされている穴子は燻製になっていて、食べると煙たい感じが口いっぱいに広がった。次に揚げ物、これは特に穴子が使われていない。海老天がぷりぷりではなくふわふわで、想像していた食感とはだいぶ異なった。締めのそばとデザートの柿でコースは終了。

食事 pic.twitter.com/t3q9axT5fn
— こたつがめ (@kotatsugame_t) 2024年11月27日

追加注文のふろふき大根はわさびのよく合うまったりした味。自家製シャーベットは上からメロン・キウイ・バナナの味で、300円にしては量があってびっくりした。

ドンキに寄って帰宅し、家飲み開始。

飲酒します pic.twitter.com/Jng89isWKE
— こたつがめ (@kotatsugame_t) 2024年11月27日

今日は「逆転裁判1」の5話を8時間ほどかけてプレイした。信じられないくらい盛りだくさんで満腹になった。逆転裁判は真面目に考える必要のある場面が多く、しかもちゃんと考えると結構分かるので、程よく頭を使えている感じがして非常に楽しい。ただどうしてもわからない部分や、どうやってフラグを立てればよいのかわからないところはいくつかあった。

午前6時前にホスフィンが帰宅。自分は部屋を片付けて午前7時半に寝た。

11/28(木)

午前11時過ぎ起床。幸い二日酔いはないが、信じられないくらい眠い。二度寝したら今度何時に起きられるかわからなかったので、必死に目を開けた。

原付で登校し、学食で食事して午後1時半からセミナー。信じられないくらい薄っぺらい準備しかできていなかったが、内容はなぜかペラペラ話すことができて、なんだかんだ普段と同じく2時間くらいのセミナーとなった。今後の研究については結局未定のままで、今はとにかく書いた論文を出してしまうべきということになった。

午後4時半から5限。先週の続きで、4年生が外積代数の説明をしていた。なんの講義なのかわからなくなってきた。午後7時解散。

学食で食事して院生室に戻ってきたら、今日も立体四目ならべの対戦が盛んに行われていた。麻雀は一過性のブーム……というわけではないはずだが、人を4人集めなければならないし手積みで時間もかかるし、修論に追われて遊ばなくなった人も多く、以前ほど頻繁には打たれなくなった。

立体四目ならべをプレイするAIの開発について相談され、興が乗ったので実装してみることにした。Pythonを勉強しているらしいので、何かの参考になればと言語はPythonを選択。盤面・ゲーム進行・プレイヤーもしくはAIのクラスをそれぞれ定義していった。

この設計については、以前インターン先の勉強会で見聞きしたものを流用している。盤面クラスはまあ普通で、ある瞬間のゲーム状態を表現する。ゲーム進行クラスはプレイヤークラスを先後それぞれ受け取り、盤面を作って手番を回していく。

プレイヤークラスは自分が先手か後手かを知っており、盤面が与えられると有効な手を一つ返す。それは例えばプロンプトを出して入力を受け付けても良いし、AIを動かしてもよい。いずれであってもゲーム進行クラスから見れば違いはないという点で、上手いやり方だなあと思い記憶に残っていた。

とりあえず対戦ができるようになると、次はAIを強くしていくフェーズ。盤面の評価については他の人に考えてもらい、自分は言われたことをひたすら実装していった。まずリーチへの対応ができるようになり、次に盤面の評価値を最大化できるようになり、さらにそれを数手先読みできるようになり……。

午前2時くらいには概ね出来上がった。完成させるのを優先させたので高速化にはそれほど気を回せておらず、4手先読みするのが精一杯。これだと人間のほうが強いようだ。

もっと速くするなら、例えばビット演算を駆使したりすることが考えられるが、いずれはインタプリタ言語をやめることになるだろう。そこでC++へと書き換えることにした。ChatGPTに投げたら肝心のAI部分をまるまる無視されたので、自分で翻訳していった。

これには2時間ちょっとかかったが成果は上々で、6手先読みが動くようになった。この時間まで付き合ってくれた二人と対戦してもらうと、どちらもAIが勝利した。

充実感を覚えつつ午前5時ごろ帰宅。ARC188の参加賞が当たったらしく、アマギフ5000円分が届いていた。

なろうを読んで午前7時半就寝。

11/29(金)

午後1時前に起床。チュウニズムの大型アップデートの情報が出ていた。レーティングシステムが変わること、スキルが軒並み削除されてGRADEの引き継ぎもないことが自分にとって影響の大きい点。削除される曲はかなり少なめだったので助かる。

12/12(木) CHUNITHMのバージョンアップにともなうお知らせ｜ニュース｜CHUNITHM LUMINOUS PLUS (チュウニズムルミナスプラス)｜セガ新作音ゲー

午後1時から1時間1on1、シャワーを挟んで午後3時からもう1時間1on1をした。それぞれ別の方とで、自分の近況報告をしたり今後のタスクについて相談したりした。詳しいことについてはほとんど決まらず。

今日はYandex Cupに向けた買い物をする。それで少し調べものをした。コンセントについてはCタイプで、昨年カザフスタンで使った変換器がまた使える。ついでにホテルの部屋に給電できるUSBポートがあることも確認した。

大学生協に行ってラノベを買い、食事して、ATMでお金を下ろして一旦帰宅。その後TCBの2024/11月回に出てから再度外出し、まず薬局で歯磨きセットとニベアのスキンケアクリームを買った。

https://techful-programming.com/techful/event/6691

ほかはドンキで買えるので、深夜でもよい。そこで次はゲーセンに行き、10クレ遊んだ。大型アップデートに伴う楽曲削除で取得できなくなる称号を集めた。MASTER以下全AJを条件とする称号が二つあって面倒だった。

あとは適当に選曲していたが、大きな成果が二つも出た。一つは「キラメケ→Shoot it Now!」理論値で、急に出たからド緊張して最後の短ホールドを押し損ねかけた。タイミングによっては始点で音が鳴らないので心臓に悪い。

もう一つは「What's up? Pop!」SSS+。ラスサビ突入時に9100点くらいで更新も怪しいかと思っていたら、なんとその後AJで通過した。最後に点数を見たらギリギリ9000点で腰を抜かした。

今日は10クレ pic.twitter.com/6alJA9hNRI
— こたつがめ (@kotatsugame_t) 2024年11月29日

ラーメンを食べ、ドンキでポチ袋・USBケーブル・USBアダプタ・服を小分けにできる袋を購入。最後の袋については自分が想像していた通りのものが売っていたのだが、値段は3000円と高めだった。

帰宅して日記を書き、午前5時就寝。

11/30(土)

正午起床。Universal Cup Finalsの参加登録フォームが出ていたが、期限が12/02まででひっくり返った。急いで作業。PDFを印刷してサインしてスキャンするなど、そこそこ面倒だった。

午後2時からUniversal Cup 19回目、Shenyangセット。

https://qoj.ac/contest/1865

書く

感想戦で再来週のUniversal Cup東工大セットの話になり、せっかくなのでとTTPCに現地参加することを提案した。

TTPC2024 - connpass

午後9時からABC382。

AtCoder Beginner Contest 382 - AtCoder

Aは $D$ に.の個数を足していくとよい。Bはやるだけ。Cは $B$ をソートしてpop_backしていく。Dはあまりにも適当にやるとTLEで、ちゃんとvalidな列のprefixだけ見るようにしなければならない。

Eは結構難しかった。1パックにレアカードが $i$ 枚入っている確率 $P_i$ を求め、 $1-P_0\gt 0$ で割って、パックに必ずレアカードが入っているものとするところまではよい。その後は悩んだが、パックを剥き終えて入手したレアカードの枚数がちょうど $k\gt X$ 枚になる確率を足し上げた。Fはまあできる。

Gは大変だった。とりあえず $k=0,K-1$ のみに注目して良さそうで、始点と終点の周りは全部試すことにする。間をスキップする算数パートについては、あまり複雑なことをしたくなかったので、 $(i_s,j_s,k_s)\rightarrow(i_t,j_t,k_t)$ であって $i_s+j_s\equiv i_t+j_t\pmod 2$ かつ $k_s=k_t$ なるもののみ考えた。

これだと $(i\pm 1,j\pm 1)$ への移動にコスト2、 $(i\pm 2,j),(i,j\pm 2)$ への移動にコスト4とシンプルに考えられる。ただし $K=2$ のときだけ後者のコストが3になる。このコーナーケースは以前のTile Distanceでもあったので、もう見た、という気持ち。

細かいことを考えていないので不安があったが、投げたら通った。しかも順位表を見たらFAだった。相当遅いかなと思っていたのでびっくり。ノーペナ全完1位。

www.youtube.com

午後11時半からCF #989 combined。このコンテストの上位60人、ただし1国から3人まで、がイラン・テヘランで行われるオンサイト決勝に招待されるらしい。イランは外務省によれば現在危険度レベル3で、渡航中止勧告が出ている。

Dashboard - Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2) - Codeforces

Aは全探索。Bは左から貪欲。Cはどうやっても外に出てしまうと確定しているマス以外ループさせることができる。具体的には長さ2のループを作ればよい。

Dは0と1、1と2のswapのみ行えるのでソート後の列が決まる。どの数をどの数に置き換えたいか求め、あとは手で気合いで構築した。

Eは $k$ が偶数なら $p$ と $n+1-p$ を使えばよい。 $k$ が奇数のときが問題なので、例えば $k=3$ でできないか手で試していたら、 $p=(1,\dots,n)$ 、 $q=((n+1)/2,\dots,n,1,\dots,(n-1)/2)$ と $3(n+1)/2-p-q$ を見つけた。あとはnext_permutationで実装。 $n=1$ にやられて1WA。