週記（2024/02/05-2024/02/11）

02/05(月)

午後4時過ぎにふと目を覚ました。起き抜けは謎の喪失感だけがあり、何が何だか分かっていなかったが、少し考えてインターン先の定例会に寝坊したことに気づいた。どうやら昨日寝る前に目覚ましをかけ忘れたらしい。慌ててPCに向かうも進捗報告のフェーズは終了しており、勉強会から参加した。

今日のテーマは汎用ビジュアライザについて。来月開催されるマスターズ選手権の予選で使おうとしているそうだ。このコンテストは決勝が社会人対象ということで話題になっていたが、他にもチーム戦だったり、ビジュアライザが提供されなかったりと特殊な点が多い。特にそのチーム戦向け機能として、サーバーを立てることでリアルタイム共有・同時操作を可能にしたとのこと。何がどうなっているかわからないものの、かなり便利そうなことはわかる。

解散は午後6時。先週までならこの時間から大学生協に行けたのだが、今週から春休み期間で学食は昼の部2時間のみ、購買も午後5時までですでに閉店してしまっている。しょうがないのでずっと先週の週記を書いていた。

週記は体裁だけ整えて午後9時くらいに投稿してしまった。博士課程進学試験が明日に迫り、それに向けて修論発表会のスライドを更新しなければならないので、あまり時間をかけていられない。ところがそのスライド更新もどうにもやる気が出ず、食事したりなろうを読んだりで2時間ほど溶かしてしまった。

何とか気持ちを奮い立たせて取り組み、午前8時くらいまでかけて24ページから39ページに増やした。もちろん重要なのはページ数ではないが、内容についても書きたかったことは盛り込めたのではないか。発表会で話した内容を深掘りしたり、飛ばした部分の説明を加えたり。さらに、当時来た質問に対してちょっとした回答を用意した。

外を見ると雪が積もっていた。明日は早めに起きる必要がありそうだ。シャワーを浴びて午前9時就寝。

02/06(火)

正午、起床。なんとか布団から出て地下鉄で登校し、午後1時過ぎに大学に着いた。30分ほど時間に余裕が持てたので学食で腹ごしらえ。まともなメニューがないと勘違いして「ガリたま唐揚げ丼」というこれから人前で話すとは思えないメニューを選択してしまったが、注文してからカツカレーの存在に気付いた。

午後1時半から進学試験開始。この試験は数人の先生の前で40分ほど修論の内容について説明し、その後10分質疑応答に答えるという形式。普段のセミナーのように、と声をかけていただいいて、緩めの雰囲気で行われた。こうなるとスライドを用意してきた分、むしろいつもより話しやすいとさえ言えるかもしれない。

冒頭で早口すぎることを指摘されたのでゆっくり喋ることを意識したほか、途中途中で質問が来たり少し議論が行われたりした結果、全体で1時間かかった。ただ感触は非常に良いし、何より楽しかった。そういえば最後に博士課程卒業後の進路を聞かれたことを記録しておく。自分はプログラマーと答えた。まあ定番の質問という話だし、これで落とされたりはしないだろう。

自分だけ退室した後、先生方が相談して合否を決める時間がある。暇なので誰かいないかウロウロしていたら、同じ教室で次に試験する人が教室の前で待っていて、それが知り合いだった。スーツを着てきていてびっくり。自分は今日も私服だった。

しばらくすると指導教員の先生が教室から出てきて、合格を伝えられた。ツイートは数時間後のもの。

同時にコメントとして「修論の結果があまり苦労せず出たもののようだから、博士課程で頑張っていけるか心配」といった感じのことを言われていたらしい。まことにその通りでございます……。結果についても複雑なことをしていないのはそうだし、関連を調べるうちにどんどん自明になってしまった。正直、自分に近い分野を専門にしている先生がいないから審査をすり抜けただけなのではないかと疑っている。

指導教員の先生に自分の博士課程進学を承認していただけた決め手もよくわからない。修士2年間ずっとD進したいと駄々をこねていたら折れただけか？それとも何かを評価してもらえているのか？こればかりは人と比較できることでもないし、面と向かって聞く勇気もないので、不安だけが付きまとう。

とまあネガティブなことばかり書いてみたが、合格自体はもちろんおめでたいことだ。とりあえず3年の期間を追加で与えられた。修士課程、特に前半は正直何もわからないまま終わってしまったので、そのあたりの反省を活かしていきたい。

数学棟の談話室に移動して、春休みの予定について2時間ほど先生と話した。修論の修正、学会発表、投稿論文準備。毎週のセミナー発表準備とは異なり、重くて締め切りの少し遠いタスクが積みあがる。一番苦手なタイプだ。何とかなってほしい。

その後留学生と合流し先生含め3人で街に繰り出した。自分の試験合格記念に加え、留学生がもうすぐ母国に帰るのでそのお別れ会で食事に行く。彼の留学プログラムは秋学期のみで、その集大成として今日、同じキャンパスの別会場でポスター発表をしていた。本当は見に行こうとしていたのだが思ったより会場が遠くて足が向かなかった。

約束の30分前に最寄り駅に到着したため、駅直結の藤崎をしばらく練り歩いて時間を過ごした。午後5時半に集合して入店。メンバーは3人に加え、我々のセミナーに参加していた競プロサークルのメンバーのうち二人が来てくれた。店はそのサークルでもよく使う武屋食堂。

生成拡張botみたいな写真を撮ってしまったなと思っていたが、実際にTLでそういう言及を見かけた。よく見ていますね。

話題はもっぱら競プロの話になってしまった。日本語だったこともあり留学生には申し訳ない。午後7時に解散し、他の人が帰宅するのを尻目に自分はゲーセンに行った。

夜中にCFがあるので今日は10クレのみ。今日は手元動画を撮っていた。素手でのプレイだったがゲーセンにおしぼりが用意してあって、毎回手を拭くことを心掛けたところかなり快適にプレイできた。新しいゲーセンで台が綺麗ということもあるかもしれない。スライダーをおしぼりで拭くと誤反応が生じて面倒なことになる。

午後10時くらいに帰宅し、撮ってきた手元動画を3本ツイートした。上のツイートとそのツリーにまとめてある。その後急いでシャワーを浴び午後11時半からのCFに備えていたが、10分こどふぉった。今日はCF #923 div.3。

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

Aはよい。必ずBがあるのがありがたい。Bはs_i=s_jなるインデックスjを記録しているものと誤読してしまった。毎回O(\sigma)かけて条件に合う文字を探す。ここで\sigma=26。Cはaにしかない数とbにしかない数をカウントする。

Dは各インデックスiについてa_i\ne a_jなるj\gt iのうち最小のものを前計算。右から見て要素を2種類管理していくと求まるがかなり面倒だった。クエリへの回答はi=lに対する値を調べるだけでよい。Eはp_{i+k}-p_i=\pm 1が条件。値が被らないよう丁寧に埋める。Fは辺を重みの降順に並べてクラスカル法をすることで、閉路に含まれる最も軽い辺がわかる。閉路の復元は適当に。

Gは左から順に見るdp。塗られたマスは基本的に連結となりそうなので境界を持てばよい……かというと、まだ不十分。連結成分が二つになることがあるらしい。まあ二つだろうが二つ以上だろうが区別する必要はなく、区間を一斉に塗ることから塗られたマスの最右と塗られていないマスの最左のみ持てばよい。O(n^3)のdp。

全完12位。

www.youtube.com

しばらくボーっとTLを眺めていた。午前4時就寝。

02/07(水)

午後4時半起床。購買はもう閉まりかけなので、外出を諦めた。布団に横たわったままなろうを読みふけり、午後9時くらいに寝落ち。

02/08(木)

午前2時に目を覚ましてずっとなろうを読んでいた。途中午前9時から正午までは寝ていたらしい。午後3時前に布団を脱出して、久しぶりのインターン先1on1に臨んだ。

今日の議題は自分が稼働を再開するにあたってのタスク確認。昨年末、取り組んでいた機械学習プロジェクトがうまくいっていないという話をしていたが、結論から言うと引き続きこれを進めることになった。本当は「進めてよいことになった」のほうが近かったりするのだろうか。半年かけて成果が出ていないため何とかすべしと言われていたはず。

このことに関して、自分の稼働時間が長いほうに勘違いされていたらしいという話を聞いた。正社員が半年取り組んでダメなら方針転換の必要があるが、自分はその数十分の一しか働いていないのだからまだ判断は早い、とかそういう感じだろうか。インターン生という立場に甘え切っている点で申し訳なさは感じつつ、今のタスクを継続できるのは嬉しい。

また、3月中旬に勉強会の発表をさせてもらうようお願いした。その前に修論関係の話が一段落してくれている予定なので、久しぶりに何かやりたい。テーマは未定。

1時間弱喋って解散。ひどい空腹に襲われ購買に行ったが菓子パンやおにぎりはほぼ売り切れていた。仕方がないのでとりあえずラノベを受け取り、帰りにコンビニに寄っていろいろ買ってきて、その一部を食べた。

今日の夜中に開催されるConstructor Open Cupに参加登録した。4時間のコンテストということで、Open Cupという名前もあり歯ごたえありそうな雰囲気。TLで少し言及を見たので出る人はちらほらいるのだろうと思った。賞品には興味なし。

Constructor Open Cup 2024 - Codeforces

コンテストサイトはCFを間借りするようだ。Muscatキャンプと同じ。ただ、念のため練習問題を2問ばかり解いておいた。solved数が一番少ない問題を開いたらすんなり解けてしまったが、本番の難易度や如何に。

まだしばらく時間があるのでこの間にDMOJに出ようかと思っていたが、微妙に眠い。諦めて午後7時半くらいから3時間仮眠し、午後11時からConstructor Open Cupへ。コンテストサイトのURLは参加者のみに配布されたようだ。解法の議論は告知ブログのコメント欄で行われていたので、ここにも書いてよいだろう。

AからGまではよいものとして飛ばす。正直説明が面倒なだけ。Hはちょうどk回操作するというのが難しいので、「k回以下の操作で作れる」かつ「和がk以上」と言い換えておく。すると前者がO(nk^3)のdpで計算できて、そのうち後者を満たさないものはまあどうにでもなる。Iは人1\dots iのうちi-1ラウンドまで生き残る人の集合を管理した。Jはdpやるだけ。

Kはxとしてn-kの約数を全探索し、判定をO(n\log n)で行った。(n-k)/x文字の同じ連続部分文字列を重ならない・隣り合わないようにx個取り出せればよいので、まずsuffix arrayとLCP arrayで同じ連続部分文字列のインデックスを集めソートし、(n-k)/x+1文字以上間隔を開けるように貪欲に取り出してカウントした。

Lはaをソートした列をbとして辺a_i\rightarrow b_iを考えるのがよい。1回の操作でx\rightarrow yとy\rightarrow zをx\rightarrow zとy\rightarrow yにしていき、すべて自己ループになったら終了。辺がm本ある連結成分なら必ずm-1回操作できるかというとそうでもないようで、サンプル5で落ちる。長さ2のループばかりあるのが問題。

相異なる3頂点x,y,wについてx\rightarrow y、y\rightarrow x、x\rightarrow wが存在すれば、2回の操作で前2本の辺を自己ループに組み替えることができるので、これを使って長さ2のループを消せばよい。連結成分に頂点が三つ以上あるケースなら必ず可能で、m-1回を達成できる。二つしかない場合はm/2回になる。

2時間13分で全完し、5位。歯ごたえがありそうと言っていたがそれほどでもなく、日本人も別に多いわけではなかった。

しばらくTLを眺めてダラダラしていたが、シャワーを浴びて気合いを入れ、午前3時半からDMOJに出た。今開催中のコンテストは3000以下Rated。明日には終わるため、ここに感想を書ける。

Yet Another Contest 8 - DMOJ: Modern Online Judge

P1は操作する区間をdisjointにするべき。移動元と移動先を見て、区間をできる限り分割していった。P2は実験すると2要素のXORが全部作れるらしいと分かった。よってaとa\oplus Xに共通部分があるか見て判定する。ただしX=0のケースだけは同じバケツを2回使ってしまいかねないので別で処理。

P3は、ノードu以下にある鉱石の頻度配列を\{c_i\}と書けば、k\times\#\{c_i\ge k\}の最大値がuに対する答えとなる。まず\{c_i\}はマージテクで管理することができる。またその更新はc_i\leftarrow c_i+1とインクリメントの繰り返しで表現することができ、このとき答えの候補としてはk=c_i+1についての値しか変化しない。

以上により、\{c_i\}のほかに\{\#\{c_i\ge k\}\}_kも持っておくことでマージテクと答えの更新が可能となる。このとき\sum c_iが小さいほうを大きいほうにマージしなければ計算量が壊れることに注意。頂点1からdfsしたらWAが出てしばらく首を傾げていたが、i=1以外でもP_i=0となることが許されているため頂点0から始めなければならなかった。

P4はまずN=1で先手が勝てるか考えた。距離2以下の2マスが黒く塗られた状態で回ってくればよい。3マス以上離れていた場合、その間のマスを選んで黒く塗ると、後手はそのマスに対して操作できないから、どのようにしてもより距離の縮まった2マスを残して返さなければならない。半々にしていけば2\log_2 Mターンくらいで終わるのでOK。

ここからNが一般のケースに拡張するのは簡単。最初2ターンで2マスの黒マスが得られるが、これが行と列ともに異なる場合、1マス目の行と2マス目の列を選ぶなどすることで4ターン目終了時に必ず同じ行、あるいは同じ列の2マスが黒く塗られた状態となる。あとは先ほどと同じ。

このテクニックはN=2またはM=2のとき使えず、後手必勝となる。例えばN=2なら、後手は必ず1行目と2行目に1マスずつ黒マスを残した状態で返せばよい。以上を丁寧に実装したら通った。操作回数については深く考えていない。

P5は適当に根付き木にして、頂点の深さと親の頂点番号を持てば良い。また制約から2頂点の深さが1だけ異なるときはどちらの親を答えてもよいため、深さとしては2で割った値を保存するだけで十分。これで73点を取った。

P6は\left(\mathbb{Z}/N\mathbb{Z}\right)^\timesの話。要素の位数を計算し集計することで|S|の候補が求まる。必ずSの頂点のどれかに1が割り当てられているため、1を根に置くことで0個が達成可能。また|S|の候補は少ないため適当に木dpすることで最大値も計算できる。ただしそのままだとMLEしてしまったので、以下のテクを適用した。かなり効いて感動。

[Idea] Using HLD to reduce memory - Codeforces

場合の数は難しい。Nが素数ならある|S|の候補に対しそれを達成するSが1通りしかないため、部分点3は解ける。部分点2は|S|=1,Nしか考えなくてよいため同様に解ける。部分点1は、調べるとN=8だけ変なふるまいをしているらしい。それっぽい計算をしたら何とか通った。しかし一般化できず残りは誤答、合計76点となった。

以上で549点。なんとtouristをも超え初優勝となった。レートは2978→3091(+113)で、初の3000オーバー。

人のブログを読んだり日記を書いたりしていたらいつの間にか昼になっていた。せっかくなので学食の開店を待ち、正午くらいに昼食。購買でこの時間はまだたくさん残っている菓子パンを買い込み、ラノベを受け取って帰宅した。

帰宅後はすぐ布団に入り、しばらくスマホを弄っていた。午後2時半就寝。

02/09(金)

午後5時から1時間起きていた記録がある。無事二度寝に成功し、次の起床は午後9時。20分後からyukicoder 417に参加した。

yukicoder contest 417 - yukicoder

Aはよい。Bは10100秒では足りないのでは？と思ってRubyで真面目に計算してしまった。ここで大幅なタイムロス。Cは客の番号を\bmod{(X+Y)}で集計してよい。あとは有名な貪欲。

Dは受験者数k、点数の総和をsとしたとき\lfloor 1000s/k\rfloor=Sが条件。式変形するとkS\le 1000s\lt kS+kが得られる。sは必要になる範囲ならどんな整数にもなれると思ってよいから、[kS,kS+k)に1000の倍数があることが条件となる。k\ge 1000なら必ずOKなので、それ未満を愚直に調べればよい。

EはA_0=B_0=A_{N+1}=0、B_{N+1}=10^5と置いて考えるとすべての条件がB_{i+1}-B_iたちの下限と総和で書ける。よって必要な分を割り振った後重複組み合わせで一発。Fは、一致判定はZ-algorithm、大文字・小文字の異なる箇所のカウントは畳み込み。

GはAに一律でオフセットtを加えた後、操作3と4を使って値の範囲を[0,U-L]に収めるものと見た。すると不自然さは、ある区間のtに対して\lfloor(\pm t+\bigcirc)/K\rfloor、のような情報の組み合わせで書ける。

tの代わりに\lfloor t/K\rfloorで考えると、\lfloor t/K\rfloorが1増えたときの差分で不自然さがだいたい求まる。t\bmod Kに由来する微妙な\pm 1は遅延セグ木を使った区間ADD・区間MINで扱える。よって区間の端点を座圧して端から舐めていけばすべてのtを試したことにできる。

1時間ちょっとで全完して4位。Bで手間取ったせいでyukicoderスコア形式だと後からどんどん抜かされる……と思ったら一人にしか抜かされなかった。上下どちらとも点数に結構な差がある。

一瞬だけAHC030に取り組んだ。

THIRD PROGRAMMING CONTEST 2023（AtCoder Heuristic Contest 030） - AtCoder

あとは朝方まで日記を書いたりなろうを読んだりしていた。午前7時就寝。

02/10(土)

正午過ぎに目を覚ましてしまい、案の定なろうを読むのに夢中になって二度寝ができなかった。午後2時からUniversal Cup 22回目、Hangzhouセット。

The 2nd Universal Cup. Stage 22: Hangzhou - Dashboard - Contest - QOJ.ac

書く：UC

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

KAJIMA CORPORATION CONTEST 2024（AtCoder Beginner Contest 340） - AtCoder

書く：ABC

www.youtube.com

動画投稿作業を後回しにしてTLを眺めているうち眠気がやってきて、午前1時くらいに寝てしまった。よってこの動画は次の日投稿されたものである。

02/11(日)

午前5時に目を覚ましてなろうを読み始め、午前8時半から3時間寝ていたのを除いてずっと読み続けていた。布団から脱出したのは午後6時。

昨日のABCの動画投稿作業を行い、半からCF #924 div.2に出た。

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

書く：CF

www.youtube.com

なろうを読んでいたらすぐ眠気が来て、今日は日付が変わる直前くらいにはもう寝てしまった。

ただいま2113話。今週は270話ちょっと読み進めたということで、先週までに比べ少ない。ところで最近「ねね」「ぽきた」ツイートができていないのだが、これは毎日布団に入った後、スマホでなろうを読んでいるうちに寝落ちしているからである。これも自分の睡眠の質を下げる要因の一つ。今週の日記で「就寝」という言葉を使っているのは、実はほとんど嘘であった。