03/11(月)

午後3時過ぎ起床。半からインターン先定例会に参加した。

先週話に出たミーティングは1週間何も音沙汰がなかったのだが、3月中にやりたいですと言ったらいつの間にか自分が関係者に連絡を取ることになっていた。自分の認識ではトップダウンで動いてくれるという話だったはず。ただ、お手間をおかけすることになって気が引けていたからむしろありがたいことなのかもしれない。先延ばしにしてしまうのを避けるべく、すぐさま連絡の文面を練って定例会後に送信した。

勉強会はChatGPTを組み込んだゲームの話とVRChatでアバターにプログラムを仕込む話。後者はプログラムを書くために用意されているわけではない機能を使ってプログラムを書くという点でEsolangと似たようなものを感じないこともない。

さて、来週の勉強会は自分が発表者である。テーマはいまだ未定。困ったら研究の話をしようと思っていたのだが、面白そうでも理解できていない話と理解できているけど面白さを伝える自信のない話しかない。困った。

3月中旬に勉強会の発表をさせてもらうようお願いした。
週記（2024/02/05-2024/02/11） - kotatsugameの日記

ABC344の飛び賞が当たって5000円ゲットした。どうやら3か月ぶりの賞金らしい。最近全然勝てなくて困っている。

お世話になっております。AtCoder株式会社です。AtCoder上で3月9日に開催された「トヨタ自動車プログラミングコンテスト2024#3（AtCoder Beginner Contest 344）」において飛び賞に選ばれましたのでここに賞品を贈呈します。

￥5,000
Amazonギフトカード
— こたつがめ (@kotatsugame_t) 2024年3月11日

週記を書いて午後11時過ぎに投稿。半からCF #933 div.3に出た。

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

Aは頑張って問題文を読んでいたら最後の一行にまとめてあってがっくり。やるだけ。Bは左から順に貪欲に操作するのが正当。Cは末尾がp、pi、m、ma、それ以外であるという5状態でdpを書いたが、冷静になると1文字削除するごとにmap、pie、mapieのどれかを破壊できるのでカウントするだけだった。Dはこれまたやるだけでなぜこの位置にあるのか不明。

Eは1行ごとに最適化すればよい。貰うdpをセグ木で書く。Fは $a_{i+1}-a_i$ が最大のところに挟む形でないと改善されない。答えを二分探索しても変わらず置ける範囲は区間一つで表現できるため、尺取り法によって線形時間でチェックできる。

Gは改札を出入りするイメージで路線ごとに超頂点を用意するテク。最初は入ってきた辺の色も持つ拡張dijkstraを考えていたが、次数の2乗にならない実装が面倒だった。よく考えたらこれも超頂点を用意するのと同じ感じで特別な色を用意すれば対処できる。

全完20位だったがopen hacking phaseでGがポコポコ落ちて15位になっていた。

www.youtube.com

しばらくグダグダしていたが、本来そのような暇はない。明日の家飲みに向けて部屋をきれいにする必要がある。重い腰を上げ、コロコロや濡れ布巾を用いて2時間ほど念入りに掃除した。終盤は朝になっていたので掃除機もかけた。

シャワーを浴びて午前6時半。睡眠時間が足りないのになぜかすんなり眠れず、布団で30分ほどハーメルンを眺めてから寝落ちした。

03/12(火)

午前10時半起床。着替えて外出し、ゴミを出したりクリーニング屋にスーツを出したりATMでお金を下ろしたりしながら、昼食会の店に向かった。予約の午前11時半には少し遅れた。

学位記授与式のため実家に置いてあったスーツ一式を送ってもらった
週記（2024/02/26-2024/03/03） - kotatsugameの日記

今日は焼肉「仔虎」。前回行ったのはクリスロード店で、今回は国分町店に来た。この店舗ではしゃぶしゃぶが食べられる。

食事 pic.twitter.com/dcnNz1I715
— こたつがめ (@kotatsugame_t) 2024年3月12日

食事 pic.twitter.com/nBU7bqAi5X
— こたつがめ (@kotatsugame_t) 2024年3月12日

書く：1130-1330

ドンキに寄って買い物をしつつ帰宅。満腹すぎておつまみはポテチ1袋とアーモンドチョコレート1箱だけしか買わなかった。

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

書く：家飲み

03/13(水)

何度かの覚醒を挟みながら午後11時まで寝ていた。二日酔いではなく単なる寝不足で、気分は悪くなく頭痛もない。朝に目を覚ましたときは家飲み翌日とは思えないくらい快調で良い一日になることを確信したものだが、眠気には勝てなかった。

部屋の片づけを終えるとちょうど半になったので、1分強遅れつつCodechef Starters 125に参加した。

https://www.codechef.com/START125A

BILMは $K$ が1の数以上なら全部削除するべきで、そうでなければ前から0に変えていって最初に出現する1をできるだけ後ろにするべき。BGMEは $A=2$ に対して操作するのが損なので、まず $A=1$ を交互に取った後は全部 $A=2$ になるまでポイントは変化しない。全部 $A=2$ にした側が総取りする。

ATBOはまず、操作で総和が変わらないことに気づいた。累積和を取ってみると一つ間を開けたswapになっている。これが分かれば判定は簡単。累積和の最後の項は弄れないことに注意。MNXRは面倒。点 $(X,Y)$ から見て左上、右上、右下、左下の四つの長方形に分割して求めた。一つの長方形について求める関数を気合いで作り、4回呼び出す。

ARLRはなかなか面白い。基本的には出現する数の種類数がbeautyとなるが、ある値 $x$ の出現が必ず $x-1,x,x-1$ という形になっていた場合のみその $x$ をカウントできない。カウントできない列の数は $x$ に依らず、行列累乗で求まる。すべての列に対する種類数の総和は、逆にそれぞれの数が出現する列を数えることにすれば直ちに $M\times(M^N-(M-1)^N)$ とわかる。写像12相を考えている時間が少しあった。

PRBWは面倒。矩形が交差しないらしいので、あらかじめ全部列挙して平面走査することで包含関係を木構造として表現できる。このときクエリ1は部分木に対する更新となるため、オイラーツアーをしておくことで区間クエリに書き換えられる。あとは遅延セグ木でOK。解法は自明だが手数が多くて大変だった。

最終問題のACが最後まで一人のみで、単独全完の一位。出遅れたかと思ったがATBO、ARLRでもFAだったらしい。余った時間で下のdivision向けの問題も解いておいた。

勉強会のテーマを思いついた。先週のUniversal Cupで2次元遅延セグメント木が欲しくなったのだが、チームメイトに聞いたら知られていないどころか存在しないことがほぼ確信されていると言われてひっくり返ったのだった。これについて発表することにし、朝まで調べものをしていた。

その後作業を二つ。まず03/18までだった博士課程の入学手続きを行った。修士のときもそうだった記憶があるが、提出物と言いつつGoogle Formに入力するだけのものが多い。振り込みが必要なものは起きてから済ませ、物理的に提出するものについては金曜日にセミナーで大学に行ったときついでに片づけてくることにしよう。郵送は面倒。

学生証用の顔写真もGoogle Form経由での提出だったが、これだけ期限が早めに設定されていてびっくりした。03/15までと書いてあったのでギリギリセーフ……かと思いきや「03/15(水)」と書いてあって様子がおかしい。今年のその日は金曜日である。おそらく昨年のままになってしまっているのだろう。正確な期限がわからないため間に合ったのかどうか不明。

次にMHCの賞金受け取りの手続きを行った。以前作業してから3か月経っても届かないので不思議に思っていたが、確認したところ賞金受け取り方法の設定が反映されていなかった。改めてPayPalを指定したところ、30分も経たずに入金されてびっくり。

今年からHackerOneというバグバウンティプラットフォームを使用するとのこと。アカウントを作ってW-8BENを書いたら終わりだった。PayPal経由で受け取る設定にしておいた。
週記（2023/12/11-2023/12/17） - kotatsugameの日記

もうしばらく調べ物を続けてから午前10時就寝。

03/14(木)

正午過ぎ起床。半から1時間ほど、月曜日にセッティングしたミーティングに参加していた。

普段の1on1とは異なる方との打ち合わせで、今後やるべきことを探っていく。ほんの少しだけ聞くことの準備をしておいたので必要最低限の情報は得られたかと思う。エクセルマクロを使っていると聞いたので衝動的にプログラムで置き換えることを考えたが、VBA以上にエクセルファイルを十全に扱えるプログラミング言語など存在し得ないのだから、置き換えたところで差異に苦しむだけだと気づいた。

外出する前に久しぶりに機械学習を回しておこうと思ったら環境が古くなっていて、バージョンアップに時間を取られた。CUDAドライバーを入れなおすところから始めたが何事もなく完了して一安心。以前適当に入れたらUbuntuが起動しなくなったので戦々恐々としていた。

改めてコードを動かしたところ警告が出て、lr_schedulerのverboseオプションが廃止されたことを知った。まあ勝手に標準出力に出されてもプログラム中でログを取るときには意味がなかったから、分かる。

Deprecated verbose parameter in LR schedulers by thomasjpfan · Pull Request #111302 · pytorch/pytorch · GitHub

そうこうしているうちに午後5時を過ぎ郵便局の窓口が閉まってしまったが、振り込みはATMでも可能。外出してまずそれを完了した後、駅の券売機で今週末と来週末の新幹線の切符を買った。週末パスは学割より安いしみどりの窓口に並ばなくても買える。しかし実際買ってみると思ったより高くて不安。これを解消したいがため、これまで頑なに窓口で買っていたのだった。

行きはともかく帰りはARCのことを考えて選ぶ必要があった。ARC前に帰宅するのは不可能だから車内から出るとして、どの時間なら良いかと調べていたら、完璧な列車を見つけた。ARC開始直前に東京を出て終了直後に仙台に着く。指定席の料金をかけてはやぶさではなくやまびこに乗るのは抵抗があるが、絶対に席を確保しなければならないため必要経費である。

見てこの完璧な列車　ARC用 pic.twitter.com/9ECsIWayMt
— こたつがめ (@kotatsugame_t) 2024年3月14日

本を買ったりつけ麺を食べたりしてからゲーセンに行き、10クレプレイ。新曲埋めで理論値を三つ出した。ドンキに寄って午後10時前に帰宅。

朝方までセミナー準備をしていた。2週間何もやっていないが前回の準備が丸々残っているからセミナーはできるだろうと思っていたところ、先生からのメールを確認すると論文のまだ読めていない箇所についての説明を求められていたので、慌ててそこの準備をした。本当は修論の英訳もしなければならないのだが手付かず。

何とか終わらせて満足したため、2次元データ構造に関する調べものを再開。ウェーブレット行列を用いた実装は通常の圧縮と比べると二分探索が回避できて定数倍速いためよく使われるらしい。実装を眺めていたら取得する値域として $[0,u)$ のみならず $[d,u)$ にも対応できることに気づいたため、Nyaanさんのライブラリを窃盗して書いてみた。これで逆元のない演算に対してもセグ木の代役を任せられる。

data-structure-2d/fenwick-tree-on-wavelet-matrix.hpp | Nyaan’s Library

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

しばらく日記を書いて布団に入った後、なぜかハーメルンを開いてほぼ1作丸々読み返してしまった。午前9時就寝。

syosetu.org

03/15(金)

午後1時起床。30分ほど布団でウネウネしてから原付で登校し、進学書類の提出と昼食を済ませた。

午後2時から2時間セミナー。読んできた論文については自分の修論とそれほど関係ないということが分かった時点で後回しになり、今後の研究について延々話し合いをしていた。あとはさっさと修論の英訳をせよとのこと。これに関しては自分でやると宣言したのにやっていないので、かなりまずい。

思いのほか早く終わったので院生室を覗いたら同期の友人がいて、夜まで研究のことなど話していた。その後学食に行ったら普段別の棟にいる整数論の人々を発見し、そちらの院生室にお邪魔することに。置いてあったボドゲから「語彙の王様」を2戦ほどプレイした。文字数制限のある状態で語彙を捻り出すのはかなり難しい。7文字以上という縛りは長くて大変なように見えて、当たり判定が広いからむしろ簡単に感じられた。

遊んでいるうちに雨が降ってきてしまったため、原付は大学に置き去りにして地下鉄で帰る。午後9時に帰宅してyukicoder 421に出た。名古屋大学プログラミングコンテストとのことだからせっかくなので録画もしてみた。

yukicoder contest 421 (NUPC2023) - yukicoder

Aはランレングス圧縮かと思ったがそうではない。ともかく全部列挙してソートしておく。後から、1と2のどちらを先に列挙するかそれぞれで調整することで、ソートされた順序で得られることを確かめた。

Bは $A$ 全体とある空でない真部分集合の総XORをそれぞれ $0$ にできればよい。前者を判定した後、後者については基底が $N-2$ 本以下かをチェックすると分かる。 $N-1$ 本だとちょうど $0$ になるような選び方が空集合と全体集合の二通りしか存在できないから。

Cは操作の逆順にdpすると $O(NM)$ 。Dはひたすら場合分け。1頂点や2頂点しかないグラフが凶悪だが、一発で合わせることができてよかった。EはKMAを設置する点の候補が高々 $8N$ 個しかないため、全部列挙して一つずつbitDPの遷移に使う。

Fは根付き木にして各頂点に対し子の悪天候度の総和を持たせるとクエリ1に対する答えがほとんどパス上の和になる。HLDで実装。Gは誤読して、先手が頂点をいくつでも選べるという問題をしばらく解いていた。勘違いに気づいてみると全方位木dpやるだけ。Hは選んだ頂点の周りに長さ2のパスがあると塗れる頂点が全然減らない。それを4本持つ十字を重ねて繋げたらうまくいった。

Gで失速してしまい速度的には3位だが、yukicoderスコアでは優勝していた。

www.youtube.com

午後11時半からはECR163に出た。

Dashboard - Educational Codeforces Round 163 (Rated for Div. 2) - Codeforces

Aは $n$ が偶数のとき作れる。構築はAABBAA...という感じ。Bは先頭から貪欲に操作するかしないか選ぶのが正当。CはBFS。Dは長さを決めると文字列の前半になれる位置がわかるため線形時間で存在判定ができる。よって長さを全探索。

Eは連続する番号の頂点に連続する値を割り当ててクリークを作るのが良い。手でいくらか試していたら $1,2,3,4,5,6$ に $4,5,6,1,2,3$ を割り当てる感じのパターンで $k$ 頂点のクリークまで作れることを発見した。これをプログラム中で生成して適当にずらせばよい。

Fはかなり時間がかかってしまった。最終的にはFPSを経由して解法に辿り着いたが後からもっとシンプルな考え方に気づいた。銀のコインの価値を区間内なら $(0,1)$ 、区間外なら $(0,-1)$ として計算したい。ここで $(0,-1)$ ではなく $(-1,0)$ と見ると単に $-1$ するだけになるというもの。区間の内外に関する差が定数となったため、最初に確率分布を求めておけば適当な範囲の和が答えになる。

Gで $O(3^n)$ 系の解法に固執してしまい解けず、6完28位。Fは区間内の銀のコインを $X$ 枚、区間外の銀のコインを $Y$ 枚としたとき $\binom{X}{i+a}\binom{Y}{i}$ の $i$ 任意、 $a$ をある値以上とした和が求まればよい。これを $\binom{X}{i+a}\binom{Y}{Y-i}$ と見ることで $i$ に関する和を取ったものが $\binom{X+Y}{a+Y}$ になり、自分の解法と合流するらしい。このテクニックを完全に忘れていた。Gはマッチングを最小点カバーに言い換え、最小とは限らない点カバーを全探索すれば良かったようだ。盲点。

www.youtube.com

ノクターンノベルズで1作読んだ。「転生したので美少女幼馴染を俺好みに育てます」。時間の進みがかなり速い。幼少期が一瞬で終わったのはありがたいが、高校生時代も同じスピードで終わってしまったのは、入学式とその後のシーンが好みだっただけに残念だった。好みだった理由にはR18であることは関係しないから、そういうものはなろうで読めということかもしれない。

https://novel18.syosetu.com/n3854iq/

シャワーを浴びてから勉強会のスライド作成を始めた。午前11時過ぎ就寝。