04/07(月)

午後1時過ぎ起床。今日は数学専攻のガイダンスがあるため、インターン先定例会は欠席する。準備して登校した時間にはもう学食の昼の部は終わっていたので、生協で買ったパンやおにぎりで昼食を済ませた。それから事務室で少し用事を済ませ、午後4時からガイダンスに出席。

内容については例年通り。これまで何度も聞いた話をまた1時間以上に渡って聞かされるのは面倒だったが、院生室が離れているなどの理由でなかなか会えない人々と久しぶりに会える、非常に重要な機会である。ガイダンス後に学食で夕食を摂った際は、学部からの同期が自分を含めて5人も集まっていた。

今年度は修士の学生が多いらしく、教室が一つ新しく院生室として改装されていた。ここは自分が修士2年のころセミナーで使っていた部屋で、元からある院生室の向かいのため人通りが多く、いつも少し気にしていた。院生室になるには適当な部屋だと思う。

院生室の霊圧が……増えた pic.twitter.com/3U3MaiRUnv
— こたつがめ (@kotatsugame_t) 2025年4月7日

夕食後に面子を探して麻雀を1半荘打った。普段とは違うメンバーでみんな玄人っぽかったため、打牌速度についていけるか不安だったが、リアルで打つのは初めてだという同期が参加してくれたのでのんびり打てた。ただでさえ満貫の手に裏が四つ乗って倍満へと化けた局が序盤にあり、このリードを保って1着。

リーチタンヤオ赤赤裏裏裏裏、倍満
1着 pic.twitter.com/qVtvujvwzq
— こたつがめ (@kotatsugame_t) 2025年4月7日

午後9時過ぎ帰宅。AHC045が終了していた。自分はグループ分けが難しいと思ったので、初めに位置情報だけで分割を固定してからクエリで全域森を改善していった。2点間の距離を求めるとき、単に矩形の中心を使うのではなくランダムにサンプリングした点同士の距離をたくさん求めること、またクエリで聞く頂点集合をランダムではなくできるだけまんべんなく分布させることを行い、12073181点。

THIRD PROGRAMMING CONTEST 2025（AtCoder Heuristic Contest 045） - AtCoder

先週の週記を書いて、日付が変わるくらいに投稿。そのあとすぐ寝た。

04/08(火)

午前5時半起床。今日は一日、寝ることとラノベを読むことを繰り返していた。2冊読了。

「エロゲの伯爵令嬢を奉仕メイド堕ちさせる悪役御曹司に転生した俺はざまぁを回避する」。文章が合わない。気に入らないところは他にもいくつもあったと思うが、読み終えたら記憶に残っていなかった。イラストは良い。

「エロ漫画の悪役に転生した俺が、寝取らなくても幸せになる方法」。面白かった。主人公がかなり好印象。憑依転生して人が変わったような振る舞いをするのはよくあるが、性欲を持て余している描写などにより憑依前からの連続性が保たれていた。過剰に影響を受けることもなく、ちょうど良い塩梅。また原作主人公に対する過度なヘイト展開は好みではなかったものの、原作との対比があまりなかったのでその設定が気にならなかった。

食事して日記を書き、午後11時半からCF #1016 div.3に出た。

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

Aは $k$ の偶奇。Bは1桁の数にしてコスト1を達成するのが最善。leading zeroをどれだけ残せるかという話になる。Cは $x=1$ または $k=1$ が必要条件で、そこだけ素数チェックを行う。Dは再帰的に解く。Eは二分探索。区間を貪欲に分割してみれば判定ができる。

Fはちょっと詰まった。最初に $c=b_i$ とし、それから一つずつ入れ替えていくのが最適。 $i$ を全探索する。Gは $i$ を固定したとき、 $(a_i\oplus a_j)\ge k$ なる $j\ge i$ の最小値が求まればよい。binary trieのインデックス $a_j$ に値 $j$ を乗せ、区間MIN取得ができるようにライブラリを書き換えた。

40分で全完して2位。

www.youtube.com

ラノベを読んで午前5時就寝。

04/09(水)

午後2時起床。ほぼ二月ぶりとなるセミナーに向け準備を行ったものの、読もうと決めていた論文に手も足も出なかった。いくらself-containedを謳っていても、これまで触れてきたものと全く異なる道具について学ぶのは無理がある。

ほかの文献を漁っていたが、序盤も序盤で躓いているためセミナーで発表できる量の内容には程遠い。間に合わないことを悟り、明日のセミナーは休みにすることとした。正確には、まだセミナーをすると連絡しておらず日程があやふやなままだったので、そのまま何も連絡しないことにした。

ラノベに逃避。「嫁に浮気されたら、大学時代に戻ってきました！」を読了。自分の想像し得る大学生活とあまりにもかけ離れていて拒絶反応が出た。また元嫁の思考・行動が不可解すぎて気持ち悪い。ただそれ以外の部分は面白かった。逆行転移モノにおいて典型的な未来知識や転移前に得たスキルの活用というのはそこまでなかったように思うが、自らの振る舞いを改善してより良い未来を掴もうとするのは読んでいて楽しい。

午後11時半からCodechef Starters 181に参加。

https://www.codechef.com/START181A

書く

ラノベを読みつつセミナー準備を続け、午前6時就寝。

04/10(木)

午後1時半起床。川内キャンパスの学食で食事しつつ登校した。3限後半の時間帯だったのでレジ待ちの行列はなかったが、テーブルは埋まり気味という混雑具合。

昨日挫折した道具について学ぶため、図書館で教科書を借り院生室で読んでいた。今日は1章のpreliminariesに取り組んだ。論文で必要になるのは2章前半の内容らしい。

午後6時過ぎに夕食を摂り、麻雀。2半荘打ってどちらも3着となった。今日は赤ドラなし・オープンリーチありのルールだったが、そもそも焼き鳥になりかけていたのでほぼ関係なし。ただ1局にツキが偏っていたらしく、七対子を目指した手がツモり四暗刻に育った。これは残念ながら対面のオープンリーチへの当たり牌をツモってきてしまい上がれず。ちなみにこのときは6索がドラだったので、そちらも切れなかった。

このときプンリー69萬がいて手を崩さざるを得なかった pic.twitter.com/cmuIhDsU8O
— こたつがめ (@kotatsugame_t) 2025年4月10日

解散後はまた教科書を読み、午前1時、最後まで残っていた友人と一緒に院生室を出て帰宅。家でも教科書を読み進めてついに2章の内容に突入したが、やっぱりわからない。大変。

日記を書き、少しラノベを読んで午前7時半就寝。

04/11(金)

午後1時半起床。

ラノベ「非科学的な犯罪事件を解決するために必要なものは何ですか？」2巻を読了。1巻発売から1年、何度かの延期を挟みつつも無事刊行されたことに、まずは感謝したい。そろそろ主人公の自己評価のズレ具合が表れてきたんじゃないだろうか。本当の強さはまだこんなものじゃないんだぜ、とニヤニヤしたりもどかしく思ったりしつつ読み進めていた。後者のほうが少し強いかもしれない。まあ、そんなある意味制限された状態でも見せ場はあったし、面白かった。頻出する「え゛」がそのまま縦書きになっており、濁点の位置がずれていたのはちょっと残念。

今日は夕方から「理数花見」と言って、数学科・数学専攻の学生と教員が集まる花見が開催される。コロナ禍前にあったものを昨年度復活させ、2年目ということらしい。昨年参加していないのは確かだが、その前はどうだったか記憶にない。

てっきり数学棟周辺で開催されるものと思い、青葉山キャンパスへ登校した。生協で買い食いしたあと近くの広場に行ったり院生室を覗いたりしたものの、誰もいない。掲示されていた案内をよくよく確認したところ、川内キャンパスの図書館前集合となっていた。

慌てて山を降りて図書館に行ったがここにも誰もいなかった。困って友人に聞いたところ、図書館から道路を挟んで向かいにある萩ホールの近くに集まっているらしい。そちらに向かうと花見のグループがいくつかあり、そのうち一つ、明らかに人数が多く男女比が偏っている集団を発見。案の定、理数花見の面々だった。無事合流。

午後4時半から暗くなるまでの2時間半ほど、延々立ち話を続けていた。同期はほとんど来なかったものの院生室のいつもの面子はいたし、組合せ論やグラフ理論に興味のある学部生に話しかけてもらうことも多かった。その熱心さに見合う話を自分ができたかというのは、あんまり自信がない。また競プロサークルのメンバーとも話した。

最後の最後まで残り、解散してからは山に戻って一人で学食。それから院生室に行くと麻雀の卓が立っており、今日も2半荘打った。3着と4着で良いところなし。攻めすぎだったとのこと。午後11時帰宅。

昨年度の年次報告書を提出する必要がある。締切は今日、金曜日までということだったが、事務室の方が確認するのが週明けになることを考えればこの週末中に提出するのも変わらないだろう。ということで昨年度行った発表なりをまとめていた。研究概要を書こうとして手が止まったので、今日はここまでとする。

ラノベを読んで午前7時就寝。

04/12(土)

午後2時半に目を覚ました。ラノベを読んで二度寝して、起きたら午後9時。食事とシャワーを済ませて午後9時からABC401に出た。午後10時から別のコンテストがあるのでそれまでに全完したい。G問題が575点なので、できない話ではない。

AtCoder Beginner Contest 401 - AtCoder

A、Bはよい。Cはmodがいつもの数でないことに注意。Dは1文字固定したときにその左右でいくつoを置けるか予めdpして求めた。この値が $K$ 以上ならOKとしたが、もともと $S$ にoが $K$ 個存在する場合を見落としており1WA。Eは $\{1,\dots,k\}$ 内の辺だけで連結になるか判定し、 $\{1,\dots,k\}$ に隣接する頂点を数えた。

Fは二つの木に対して直径を求めておけば、繋げたあとの新しい直径の候補はそれら直径自体か、その端点を結んだものとなる。後者については $i$ と $j$ をほぼ独立に扱えるので、畳み込みを用いて頻度配列を作成し、全通りに対して真の直径を計算した。Gは二分探索＋二部マッチングやるだけ。

32分弱で全完、3位。ペナがなければ優勝だった。1時間以内に全完できればよいと思っていたが、そのまま駆け足で振り返りまで撮り終えることができた。動画投稿まではさすがにする暇がなかったので、明け方の公開となった。

www.youtube.com

午後10時からMidnight Code Cup予選。24時間コンテストと聞いて面白そうだったため参加を希望したが、ICFPC系らしくFinalだけでなく予選も普通の競プロコンテストではないようだ。ちょっと出鼻をくじかれた感じはあるものの、楽しそうという思いは変わらずある。

MCC Qual Wrap Up - Codeforces

3問あったので一人1問担当する感じで進めていくこととなった。C問題が未知のプログラムを解読するものだと判明したため自分がかっさらって抱え込み、以降risujirohさんが担当したA問題、Rubikunさんが担当したB問題にはノータッチだった。

C問題はKotlinのソースコード二つと10個ずつの入力ファイルが与えられ、各コードに対応する入力を与えて実行したとき得られる計20個の出力結果のうち、正しく求められたものがスコアとなる。まともに実行して解が得られるのは数個のみであるため、如何にプログラムの処理を読み解いて効率化するかが問われている。

では肝心のソースコードはというと、Kotlinで別のプログラミング言語を実装し、そのプログラムを構成して実行していた。Kotlinは特殊な言語ではなく、雰囲気で十分読めるため、実装されているプログラミング言語の仕様を把握し何のプログラムか見抜けばよい。

まずは一つ目のソースコードと格闘。

しばらくコードとにらめっこして頭だけで頑張っていたが、まったく歯が立たない。幸いそのプログラミング言語にはデバッグ用の機能が豊富に搭載されていることが分かったので、実行を繰り返しつつ取り組めと言われていることを理解し、手元にKotlinの環境を構築した。ここまでで30分くらい浪費。

いざ実行してみると、標準エラー出力にログがドバっと吐き出された。思っていたより親切設計。それらとコードを見比べてこのプログラミング言語の仕様を把握した。

いくつかのレジスタと大きなメモリが存在する。
メモリ上にはbyte列にエンコードされたプログラムが置かれていて、その上をinstruction pointerが動き実行していく。
スタックに対するpushとpopが行える。そのスタックもメモリ上に置かれている。
メモリにはランダムアクセスできる。レジスタから/レジスタへのread/writeも行える。
mod 2³²での加・減・乗の演算が存在する。
ジャンプ命令が存在する。条件は直前の演算結果が0かどうかや、オーバーフローが発生したかどうか。
即値を記述できる。

また簡単のため、以下のような機能も搭載されていた。

プログラムの任意の位置にラベルを付けることができ、ラベルからメモリ上のアドレスを引くこともできる。
ラベルを利用した疑似的な関数呼び出しが存在する。callで関数に入り、スタックを呼び出し時と同じ状態にしてretすると元に戻ることができる。
callの代わりにcallPreservingRegistersを用いると、指定したレジスタの内容がret後に復元される。
任意の位置にデバッグ命令を置くことが可能で、レジスタの内容をすべて出力できる。判別のため指定したタグを表示してくれる。

例えばcallPreservingRegistersなどはいくつかの操作の塊として実装されている。真面目に読んだが関数名から雰囲気で分かるのかもしれない。

これらをもとにさらに読み進めていった。なかなか興味深くて、言語で提供されているスタックのほかにメモリ空間の一部を自分でスタックとして扱っているようだ。プログラム上にスタックの両端のポインタを書き込み、適宜更新しているらしい。このあたりの操作はラベル"push"、"pop"でまとめられていたので、ここも雰囲気で飛ばせたのかも。

三つの数 $a,b,c$ を受け取り、 $3^{a+b+c}$ 回ラベル"check"の関数を呼び出して、その結果を集計している。"check"関数にはレジスタA～Dのそれぞれをデクリメントする部分があって、何をしているのかわからないし、instruction pointerが指すアドレスを用いた計算があるためうかつにデバッグ命令も置けない。

しかし幸いこのデクリメント操作は特徴的な演算のため、ログ出力からgrepで抜き出してくることができた。すると、レジスタA～Cのうち一つを選んでデクリメントする、ということを $a+b+c$ 回行うすべてのパターンを探索していることが分かった。

あとは集計結果と見比べた。集計とは単にカウントらしく、その条件は「レジスタAを $a$ 回、Bを $b$ 回、Cを $c$ 回、同じレジスタが連続しないようにデクリメントするパターン」であることがエスパーにより判明。 $O( (a+b+c)^3)$ のdpを書いて出力を求め提出し、ついに一つ目のソースコードについては満点が得られた。

ここまでで2時間半が経過。残り1時間半でもう一つのソースコードを処理するのは無理そう、と思いつつ開いてみたところ、大部分の処理が共通していたので光明が見えた。

今度は入力が一つの数 $n$ で、 $3^{2n}$ 回"check"関数を呼び出している。そして先ほどの3種類の操作は、それぞれレジスタAに $\pm 1$ を代入するか、レジスタFに $0$ を代入するか、となっていた。あとはどのパターンがカウントされているのか列挙してエスパーすることを目指す。実験結果は $n=1,2,3$ に対してこんな感じ：

02
12

0122
1022

本当はミスで一部分が反転しており何もわからなかったのだが、それがなかったとしてここから何か掴めるかは不明。何もわからないままコンテスト終了間際を迎えた。

入力データとして与えられていたのが小さいほうから $n=3,10$ だと思い込んでおり、実は裏でずっと $n=10$ を回していたのだが、全然終わらない。しかし順位表を見ると2問、3問解いているチームが多い。どうしたことかと改めてデータを確認したところ、 $n=6,8$ の存在を発見した。

慌てて実行を開始。途中でログ出力が律速になっていることに気づき、全部コメントアウトして改めて走らせ、何とか $n=6$ だけは間に合わせた。コンテスト終了時間を5分早く勘違いしていたので肝が冷える思いだった。

結果は、他二人がA問題とB問題でそれぞれ90%以上得点してくれたことが効き、11位。自分の得点率だけかなり低くちょっと残念だが、周囲のチームと比べて自分だけC問題で点数を落としているというわけではないので、そういうセットだったと納得するしかない。

しかも予選通過が上位25チームだったので、結論から言えば自分が最後に慌てて取った点は不要だったということになる。上位8チームだと思い込んでおり、その場合は $n=8$ を通せていれば通過だったため、戦犯を覚悟していた。予選について無知すぎた。

いずれにせよ、決勝進出！Finalは6月上旬、セルビアはベオグラードで行われる。また海外旅行をする機会が得られて非常に嬉しい。チームメイトのrisujirohさんとRubikunさんには改めて感謝を申し上げます。Finalでもよろしくお願いします。

その後tatyamさんのツイートを参考にupsolve、というかコードの読解を最後まで頑張った。上で言及した「何をしているのかわからない」部分はinstruction pointerが指すメモリの値、すなわちプログラムを動的に書き換えていたらしい。そういうことができる難解プログラミング言語は実際かなり多いが、コードゴルフなどで使用するほど切り詰めた経験がない。

[C2]
動的にコードを書き換えていると思ったら switch 文だった　非自明すぎ

ABC からなる長さ 2N の文字列であって…

A: 重み -1 の (
B: 重み +1 の (
C: )

で、先頭が ( かつ末尾が ) の括弧列を作り、各部分木の重みを -1 以上 1 以下にする方法の数

3 乗の DP をする
— tatyam (@tatyam_prime) 2025年4月12日

またレジスタFへ $0$ を代入するのが無駄であることは分かっていたが、このパターンは別のところの条件分岐で消費され、実際に実行されることはほとんどなかった。"check"関数内で再帰している"go"関数がreturnする際の条件。つまり括弧列における閉じ括弧というわけだ。3パターンの割り振りがコード上で固まっていない点でも、一つ目のソースコードより確かに難読である。

開き括弧の $\pm 1$ を集計し、最後に $+1-3$ を行ってオーバーフローが発生したかどうかを確認していたのが、カウントの条件。再帰であることから括弧列を連想し、このオーバーフロー判定が $-1,0,1$ の検出であることを見抜いていれば、実験結果からのエスパーもあり得たかもしれない。まあ結果をまとめるときにミスしていてはお話にならないかな。

TLを見る限り、このC問題にはChatGPTなどを利用して立ち向かったチームが多かったらしい。自分には全くなかった発想だが、確かに効きそう。しかし自分がgrep片手にログ出力と格闘していた時間は何だったのか……とちょっと寂しい気分にもなる。Finalに行く前には課金しておくべきかも？

ラノベ「サイバーパンク居酒屋『郷』」を読了。突拍子もないギャグが次から次へと展開され、ついていくのに多少の努力を要するが、その過程で世界観や設定を無理なく導入しているのは上手いなと思って読み進めていた。あとがきによればそういう構成を意図しているようだ。そうやって判明した細かい設定が主人公の特別性に絡んでくるところは、Web版で読んだときも今回も、やっぱり面白かった。

日記を書いて時間を過ごし、午前7時半からMIT Informatics TournamentのQualification Round 2。

https://mitit.org/Contest/ViewContest/qualification-2025-2

Dashboard - MITIT Spring 2025 Qualification Round 2 - Codeforces

書く

ラノベを読んで正午に就寝。

04/13(日)

午後5時起床。ラノベを読んだ。

「冒険者酒場の料理人」2巻を読了。信じられないくらい面白かった。章題から完結巻かなという感じはしたが、その最後の章がもう最高。もちろんそこまでの話も、生活感あふれる異世界描写や娘・ウカノの可愛らしい様子など読んでいてじんわり来る。しかし、たった単行本2冊分の話で最終話にこれだけの衝撃と感慨を持ってくることができるとは！

なろうもチラッと確認。文章量が倍以上に増えているようだが、根幹は変わっていないだろう。ただキャラクターも増えてより賑やかになっているし、やっぱり書籍版をおススメしたい。それにしても、黒留ハガネさんの作品は読んだことのある限り全部面白い。すごいお人だ。

https://ncode.syosetu.com/n4998ig/

午前0時半からCF #1017 div.4に参加。

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

Aはよい。Bは実際に $n-m$ 回縮めてみた。Cはやるだけのはずが、配列サイズを $2n$ ではなく $n$ にしていて1WA。Dはランレングス圧縮した。Eは $k$ を全探索して桁ごとに和を求める。Fは $g:=\gcd(n,k)$ として $g\times(k/g)$ のブロックを詰め、少しずつずらす。

Gは通常の列とreverseした列に対して操作1と3を差分更新したが、冷静になると操作2も簡単に差分更新できた。Hは次に $k\equiv 0\pmod{a_i}$ となる $i$ を高速に探索できればよく、 $k$ の約数を列挙してそれぞれ検索した。計算量は若干大きい気もするものの、そんなに非効率的になるケースは作れないはず。

32分で全完して8位。

www.youtube.com

ラノベ「アラサーがVTuberになった話。」2巻を読了。あまりの分厚さとWeb版4章ラストの大好きなシーンが収録されているという事実に怯み、買ってから2年くらい積んでしまった。いざ読んでみるとやはり面白い。掲示板パートが単なる挿話にとどまらず、そこでもストーリーが進行し、さらにはイラストまで付くというのはかなり特徴的。

朝までかけて年次報告書の研究概要の部分を書き上げ、提出。シャワーを浴びて学食に向かい朝食を摂った。ラノベを受け取って帰宅。この時間帯はちょうど1限が行われている最中で、特に2限に向け登校してきた学生で生協が混み合う少し前。無事混雑を回避できたし、登校してくる学生の列を尻目に帰宅するのは快感だった。

午前11時過ぎ就寝。