週記（2024/11/18-2024/11/24）

11/18(月)

午後3時過ぎ起床。

JOI一次予選の第3回が公開されていた。そこそこタイミング良く発見したらしく、FAではなかったものの0msでのFastestは4問とも獲得できた。コードゴルフも行ったが、数日後に確認したらB以外すべて縮められていた。どれも書き方だけの問題でなく、そもそも短く書けるアルゴリズムを思いつけていなかった。

JOI 2024/2025 一次予選 (第3回) 過去問 - AtCoder

午後3時半からインターン先定例会。先週伝えたように稼働はしていない。論文は無事書けて、今週金曜日の学内での発表も何とかなりそうだと報告した。勉強会はヘッドマウントディスプレイの紹介。操作はコントローラーで行うものと考えていたが、視界に映った手のジェスチャーを認識することもできるらしい。

先週の週記は午後7時半に投稿し、それからCFの5hコンテストに参加した。もともと先週木曜日に予定されていたと思うが、トラブルがあったらしくこの日にずれてきた。

Dashboard - 2024-2025 ICPC, NERC, Southern and Volga Russian Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams) - Codeforces

順位表に従ってNJACLBGKDFIMをこの順に解き12完、20位。

N、Jはよい。Aはよくわからなかったが解かれ具合を見るに後ろの人に貪欲に押し付けてよいらしい。Cは大きな方と小さな方から2個を組み合わせる。Lは切り出し方7パターンのうち二つを全探索する。もう二つは高々1回しか使わず、残りは貪欲でよい。Bは式を立てて解くと\frac{a_1+2a_2+\dots+2^{n-1}a_n}{2^n-1}が登場。これが整数なら商を使っていろいろ決められる。2進数表現を見ながら無理やり計算した。

Gは結構面白い。1と11を聞いて差を取ると1の連結成分数がわかり、その値を01と比較することで先頭が確定する。Kはc(i,j)=2となる最後のマスを必ず通るべき。そこまでのコストは算数、それ以降は十分狭いのでdpできる。Dは最後の区間のORを持ちながらdpすると状態数がO(n\log n)になる。

FはE\ge lとなる選び方を数え上げることにする。FPSで立式するとテイラーシフトになっているので、窃盗。nononさんのコードを開いてみたらACLを使いめちゃくちゃシンプルに実装されていて非常にありがたかった。

https://judge.yosupo.jp/submission/211045

Iはよく解釈すると行列を適切に左シフトしてから辞書順最大の行を求めよという問題になっている。2倍にしてすべて連結しSuffix Array。Mは各スート必要なカードを何枚持っているか管理してメモ化再帰し、計算結果を埋め込み。手札に残すスートは一種類だけでよいと思っていたが、サンプル2で落ちてくれて助かった。

ここまで3時間。残りの2時間はEと格闘していたが最後まで通らなかった。後ろから埋めていくのが最適であるというのは正しく、実装ミス。後日WAだったテストケースを確認して直しておいた。埋めるタンクを先に取り除いてから頑張って算数していた部分を、単に粘土を追加して水位を均してから取り除くようにしたら通った。なぜわざわざ面倒な実装をしていたのだろうか。

www.youtube.com

午前2時半就寝。

11/19(火)

本来なら発表準備を進めなければならないが、先週スライドが完成したので危機感が失せてしまい、この日は一日中布団の上でなろうを読んでいた。午前8時起床、正午から午後5時半まで二度寝、午後10時就寝。

11/20(水)

今日も夜中までずっとなろうを読んでいた。午前3時起床、午前8時から午前10時まで二度寝、午後5時から午後10時まで三度寝。

昨日の時点で今夜のCodechefがRated for Allであるという情報をキャッチしていた。モゾモゾ布団から抜け出して、午後11時半からCodechef Starters 161。

https://www.codechef.com/START161A

RGBMはP_i=iなる要素があれば1手で全体を一致させられる。そしてそのような要素がなかったとしても、N\ge 3であれば1手で一つ作ることができる。

ONETOTHREEは3をできるだけ1にしたくて、いろいろ手で試した結果3の連結成分ごとに考えて良さそうという結論になった。1と隣り合っていれば一つを残してすべて1にすることができ、また2,3,2を2,1,2にすることもできる。出したら通った。

QUICKEXIT0は頂点Nの祖先の子それぞれにKより小さい強さを割り当てたい。各部分木の中途半端な頂点にKより小さい強さが割り当てられていることはないとしてよいから、ある頂点がKより強いならその子もすべてそうであり、つまり脱出までの時間が部分木のサイズだけ増える。あとは貪欲。

そのままQUICKEXITも解いてやろうと意気揚々と進んだが、なんと解けなかった。残り時間が少なくなってきたので諦めて前2問に戻った。

MINMAXSUBは0と1のみで考えてみた結果両端の値で決まることが判明。具体的には、Nが偶数なら両端のMIN、Nが奇数ならMAXとなる。FREQXORはX\oplus(L+i-1)をセグ木の要領で\log個の区間に分割し、それぞれimos法でカウントした。

5完遅解きで22位、レートは2922→2900(-22)。残念。

MHC Tシャツ発送の受付が始まったらしいので、さっそく手続きしておいた。12/13までらしい。またホスフィンとの家飲みに向けてお酒をAmazonで注文した。日付は日記で言及していなかったと思うが、来週水曜日である。

発表の日がいよいよ近づいてきたので、原稿の作成を開始した。本来であれば火曜日の時点でパパっと書いてしまい、留学生にチェックをお願いした上で、内容を覚えたり発表練習したりする時間をゆっくり取れるという見込みだったのだが……。

午前9時半を過ぎてようやく完成し、留学生に送って寝た。

このくらいの時間には先週走ったDMOJのコンテストが終了していた。19分49秒で全完し、21秒差で2位。Bの実装が下手くそだったのと、Eを二分探索だと思い込んである程度実装してしまったのが敗因。しかしまあ簡単セットだったので、各問題の感想は特に述べない。

Arcadia Computing Contest 1 - DMOJ: Modern Online Judge

11/21(木)

正午前に起床し、原付で登校して学食で食事。今日は午後1時からワークショップに参加する。組み合わせ論の超有名人・Richard P. Stanley先生が東北大学に来られることになり、それに合わせて開催された。ちなみに先週から言っている自分の発表は二日目、つまり明日に予定されているものである。

Combinatorics@Sendai2024

Stanley先生は御年80歳。もともとこの秋ごろ、数週間の長い日程で日本に遊びに来る予定だったらしいが、それを聞きつけた人々がぜひ大学に来て話をしてほしいと持ち掛け、結果7週間に渡って中国・韓国・日本を練り歩く旅程が組まれたようだ。日本では、自分が知る限りだと他に津田塾大学・東京大学でもご講演されたらしい。Webページに掲載されたabstractを見るとわかるように、内容はすべて同一である。

【談話会】Richard Stanley 氏（11月5日） ｜ 数学科 ｜ 津田塾大学

Lie群論・表現論セミナー | 東京大学大学院数理科学研究科理学部数学科・理学部数学科

東北大学のワークショップはこの行脚の掉尾を飾る。長旅の疲れとここ数日の冷え込みからか仙台に到着されたときは体調を崩し気味だったとのことだが、今日教室に見えられた姿、また発表の様子はずいぶん矍鑠しておられたように感じた。内容も分かりやすく美しかった。

二つ目の発表は、今年2月の日本数学会東北支部会と同じものだったはず。もともと非公式のセミナーという話だったのが公式ワークショップになったので急遽内容を変えたと言っておられた。四つ目の発表は出張して来られた先生のもので、黒板を使った大変エネルギッシュなものだった。自分が修士のときやっていたこととも関わりがあって、非常に面白かった。

本来予定されていた懇親会はStanley先生の体調が思わしくないということでキャンセルに。しかしせっかく来られた先生もいらっしゃるということで、教室に残っていた数人で店に行くことになった。ノコノコ着いていったら先生4人に対して学生が自分だけとなり、緊張で張り裂けるかと思った。

それから1時間半ほどゲーセンで遊んだ。8クレプレイして14+のAJが一つ。

帰宅してからしばらく明日の発表練習をした。いつの間にかスライドの内容を記憶していたので何とかなりそう。午前2時就寝。

11/22(金)

午前5時に起きて、二度寝できないままずっとなろうを読んでいた。午前11時くらいに登校。昨日原付を大学に置き去りにしたため今日は地下鉄を使った。

学食で食事してから教室に行き、設営と発表練習をした。昨日の時点でStanley先生の体調がどう転ぶかわからなかったが、幸い今日も対面で参加していただけるらしい。

午後1時半から自分の発表。最初Zoomの音声トラブルで少しもたついたが、以降はそれほど問題なく進められたものと、自分では思っている。Stanley先生や他の先生からの英語の質問も聞き取って返すことができた。発表時間が予定より短かったのはちょっと失敗。もう少しゆっくり喋るべきと指摘されたが、一方で別の先生からは自分の英語が十分聞き取れるものだったという感想を頂いた。

休み時間にStanley先生と黒板を使って議論する機会があった。ここは反省するべきところが多い。無言になると何か喋らなければと思って、自分のアイディアばかり口走ってしまったのだが、あの無言はたぶん考えている時間だったのだろう。じっくり待つべきだったのだと思う。それでも研究の方向性についていくつかご意見を伺えて、貴重な時間だった。

その後Stanley先生の発表。自分が今やっている研究の源流がStanley先生にあるということで、来仙の話が回ってきたとき発表していただけるようお願いしたのだが、昨日飲み会の場で聞いた感じだとかなり特別なことのようである。もともと観光メインで旅行しているところに、今日ここでしか使わない内容での発表をお願いしたのだから、それを承諾していただけたところにStanley先生のお人柄の良さが表れている。大変ありがたい。発表も非常にためになった。

解散後、2時間ほど別の先生と議論した。Stanley先生が自分の研究の源流ならこの先生は直接の親みたいな関係で、かなり細かいところまで踏み入った話を聞くことができた。同じ研究対象についての未出版のものを含む結果や、これからの研究の具体的な方針について。

学食で食事した後三人麻雀を1局打った。オーラスでリーチ・役牌・ドラ1・赤1・抜きドラ4の倍満を上がったが、トップが独走状態だったので順位は変動なしの2着。

午後9時少し前に帰宅。急いで準備してABC381に出た。

AtCoder Beginner Contest 381 - AtCoder

A、Bはよい。CはLとRの連続する長さを前計算した。Dは隣接する2項を圧縮してから尺取り。特に(2k-1,2k)と(2k,2k+1)のどちらをマージするかは両方試す。Eは二分探索して、LとRをできるだけ端に寄せる。Fは右端としてあり得る位置の最小値を持つbitDP。

Gは全く分からなかった。というか眠すぎてまともに頭が回らない。ろくなことを喋られないので録画も打ち切ってしまった。6完20位。

日付が変わったくらいに就寝。

11/23(土)

午前5時起床、午前7時から午前10時半まで二度寝、合間はなろう。昼に学食へ行こうと思っていたが、なろうを読み進める手が止められなかった。しかしそもそも今日は祝日で休みだったらしい。

午後1時半を回って起床し、食事。また届いてから2週間くらい放置していたコンテストTシャツを開封した。

午後2時からUniversal Cup 18回目・Southeastern Europeセット。

https://qoj.ac/contest/1849

書く

シャワーを浴びて午後9時からARC188。

estie Programming Contest 2024 (AtCoder Regular Contest 188) - AtCoder

書く

www.youtube.com

午後11時半からはCF combined、CodeTON Round 9。

Dashboard - CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!) - Codeforces

書く

www.youtube.com

地元の蟹が丸々一杯自分のところに回ってきたので、1時間ほど格闘して完食した。母親に食べ方を聞いたが、ふんどしを取って脚を外すだけで見たことのある状態に分解され、後は流れで食べることができた。使った道具は箸1本だけで、あとは手で脚を折りまくって何とかした。鋏の部分だけはどうしようもなく、箸で身を突き崩して吸い出した。しかし疲れた……。

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

11/24(日)

午後3時くらいに目を覚まして、二度寝できないままゴロゴロしていた。もともと午後6時には起きる予定で、それからちょっと外食して英気を養おうと思っていたのだが、その午後6時を目前にしてついに眠気が到来。

二度寝から目を覚ましたら午後8時半だった。急いで食事して午後9時からAGC069。

AtCoder Grand Contest 069 - AtCoder

Aは区間[l_1,r_1]と[l_2,r_2]をマージして[\max(l_1,l_2),\max(r_1,r_2)]を作るものと捉える。このことから、rを伸ばすのは常に1円で可能。一方lを伸ばすのは難しい可能性があるが、よく見ると1次関数の和になっているようだった。適当にマージしてみるとサンプルが合ったので、提出。しかしWA。

このWAの原因は、傾き-1の線分と傾き1の線分を同時に扱っていたせいらしい。あるいはf(x)ではなく\min_{x'\le x}f(x')を管理するべきだったとも言うことができる。よくよく眺めてみると、傾き1の線分は常に傾き-1の線分と相殺することができた。こうして傾き-1の線分と定数のみを管理するようにすると、何とかAC。

Slope Trickという直感は正しかったし、最後までそういうふうに解釈していればMINを取る操作もごく自然なものだったはず。アドホックに実装してしまったせいで1ペナ、さらにWAの原因に全然気づけず30分ほど追加で消費してしまった。

Bは最後のほうまで「以前の質問に対する返事」を有効利用できていなかった。行と列の適当な入れ替えで聞くマスを対角線に並べ、(1,1)から(N-1,N-1)までを一気に聞くことを考えていた。

このときYesが0回または2回なら確定。(i,i)を聞いた1回だけYesだったときに特定するには、(i,i),(i,N),(N,i)のいずれか1マスは0でなければならない。これを判定するにはN行目・N列目を固定したうえで最大2部マッチングを求める必要がある。N行目を固定した後DM分解を使って頑張ってみたが敢え無くTLE。さらにWAも大量に出ていた。

残り14分くらいでようやく見落としに気づき、正しい解法へ1歩踏み出した。つまり、(i,i)を聞いたタイミングで(i,i)\dots(i,N),(i,i)\dots(N,i)のどこかに0があればよい。しかしその実装方法がわからず時間切れ。1完125位でパフォーマンス2521、レート2922→2887(-35)。

コンテスト後もしばらくBを考え、エスパーでほぼ正しい実装方針にたどり着いた。質問する度、同じ行または同じ列の適切な位置に0があればよいから、その0と質問を対応付ける。逆に対応付けられた0の集合を選ぶとき、適さないものはどうなっているかというと、例えば(i_1,j_1),(i_1,j_2),(i_2,j_1),(i_2,j_2)のように2x2に並んでいる。これを許さないためには、辺(i,N+j)を考えて閉路を作らないようにすればよさそう。

ということで、S_{i,j}=0に対し辺(i,N+j)を考えて、閉路を作らないようにN-1辺選べるかという解法を投げた。しかしこれもWAの数が全然減っていない。ここで諦めてTLを見たら、次の盤面がYesであると言われていた。

011
111
111

手で試してみると、確かにそう。つまりN\ge 3の場合はN-2辺選べればそれでよかったらしい。半信半疑で修正して出したら、見事通ってしまった。このコーナーケースは1ペナ払って愚直を提出し気付いた人が多かったらしいが、自分はそもそも愚直が書けると思っていなかった。やはり長い間N-1手まとめて考えていたのが特大の誤りだろう。

www.youtube.com

12月のラノベ新刊をチェックして16冊注文した。またそうやって本を眺めているうちにAGCで落ち込んだ気分が元通りになってきた。日記を書き、学食で食事して、午後1時前就寝。