週記（2020/11/02-2020/11/08）

11/02(月)

寝落ちしていて、午前9時に起きる。そこから2時間くらい二度寝しようと布団でもぞもぞしていたが、結局そのまま起きることにした。この時点で午前11時。

昨日は日記を書かず寝落ちしてしまったので、その分を書いて、投稿した。なんとなく興が乗って4000文字くらい書いたところ、この週の週記の文字数が14000文字となり、2000文字/日を達成した。実際にはリンクを貼ったりした分でいくらかかさましされている。

投稿した後ふと思い立って、ABC181のC問題のコードゴルフをもう少し考えてみる。2次元平面上の点を扱うなら、複素数で持つのが定石だったことを思い出した。原点と点x、yをそれぞれ結ぶ直線が平行であることの条件は、x=a+bi、y=c+diとしてad-bc==0を判定したいのだから、x*y.conjの虚部が0かどうか判定すればよい。y.conjはyの共役な複素数を表す。

これでcombination(3)したほうが短くなった。rescueも消えた。

atcoder.jp

食事をした後、AOJ-ICPCを埋める。無証明でテストケース見ながらごり押しするのは練習としては最悪なんだけど、やってしまう。解説ブログを読んだら枝刈りで計算量がよくわからないタイプの問題だった。止めよう！

そういえば、AOJにもレーティングが存在して、例えば問題の提出一覧を見るときなどこの値の降順にコードが並ぶが、最近更新されていない。結構気にしているので、また更新が再開されることを願う。

https://onlinejudge.u-aizu.ac.jp/problems/1233

このくらいの構文解析の問題はかなり楽しい。時間をあまり気にしていないので、設計をしばらく頭の中で練ってから実装した。

https://onlinejudge.u-aizu.ac.jp/status/users/kotatsugame/submissions/2/1233/judge/4962252/C++14

多項式を表現する必要がある。各項の次元を表す構造体Strと、それの線形結合である多項式を表す構造体expを作った。名前は適当。

Strでは、関係する変数を次数のぶんだけ並べて保持することにした。x3 y2だと"xxxyy"のような感じ。正直これはstringを掛け算する関数だけ作るのでもよかった。実装上の要請からいくつかメソッドを用意したが、ほとんどは元のstring型のメソッドを呼び出している。変数は文字コード順に並ぶようにしているが、これは毎回ソートしなくてもマージソートの要領で並べればよい。ただ実装上の手間を考えると毎回ソートしたほうがいいのかもしれなかった。

expは、map<Str,int>で各項の係数を持つ。ただ、係数が0の要素が残っていると比較の時にちょっとまずいことになるので、毎回係数が0になった要素を消している。足し算や引き算はそのまま足しこめばよくて、掛け算はStrの掛け算を呼び出して行う。

構文解析は普通に書けばよいのだが、スペース交じりの文字列なので、そこをどう扱うか少し悩んだ。多分関数内で適宜読み飛ばししてもよいのだろうが、いろんなところで読み飛ばしのコードを挟み込むとちょっとつらそう。なので、入力のstringをまずトークンに分解して、vector<string>に対して構文解析を行うことにした。数値は纏めるが、それ以外は全部1文字ずつに分解する。

そんな感じでゴリゴリ書いたところ、30分くらいかかった。クーリッシュを机に出していたことを完全に忘れており、解き終わってから見るとグズグズに溶けてしまっていた。食べごろを逃している。

メールをチェックすると、リクルートの冬アルバイトの書類選考を通過していた。

もし向こうが競プロerに興味があるなら、僕をエントリーシートで落とす理由はないと思う。

週記（2020/10/26-2020/11/01） - kotatsugameの日記

尊大な自尊心である。羞恥心が臆病かどうかは知らない。

面接日程を決める必要があるが、近くならないと自分の生活リズムがわからないので、しばらく放っておく。スキルチェックをやってみる。これどこまで情報を書いてもいいのかわかんねえな。問題を盗んで公開しているらしいLeetCodeはカス。

まずアルゴリズム関連の問題を選んで解いてみる。競プロチックな問題に見える。using namespace stdしないで書いたが、信じられないくらい読みにくくなった。

問題なくコードを書き上げて、別の問題を開いてみるが、もうわからなくなってきた。一応自分用に書いたコードで使用したことのある技術なので、まったくとっかかりがつかめないわけではない。必死にググり散らかしながら書いたが、半分もいかないうちに嫌になってきて布団にダイブし、そのまま寝落ちしてしまった。

11/03(火)

午前8時くらいに起きた。だんだん早起きになってきている。

寝落ちしてしまった昨日の分の日記を書いた。昨日1冊本を読んだはずなのだが、どの時間帯に読んだかさっぱりわからない。いっそのこと今日の部分に書いてしまおう。

「御執事様の仰せのままに」という本。貧乏大学生が実は日本一の金持ちの直系で、急に跡取り候補になって上流階級の生活に戸惑う……みたいな話だ。

内容はさておき、「上流階級の話」ということでちょっと考えていることがある。作者は別に上流階級の人間ではないそうだが（あとがきより）、描かれた描写はどれくらい現実味があるのだろう？この本で描かれた上流階級の話はほかのなろう小説とかで読むものとあまり変わりがないので、現実にどうなっているかはともかく、そういう共同幻想があって、それに沿って話が作られていると考えられる。

大富豪とか会社の社長とか芸能人といった人たちを主人公にしたなろう小説をよく読むが、各ジャンルの作品群にもたいてい共通する描写の要素はある。しかし読みながら現実ではどうなっているか気になってしまう。というか会社の社長って何をするんだろう？どれくらい忙しいんだろうか？

勝手な想像だが、極端な話アメリカ合衆国の大統領とかは1日のスケジュールが秒単位で決まってそうだと思っている。でも調べて出てくるようなインターネットの記事を見る限りだと全然そういうことはなくて、朝起きてからしばらく運動のために時間を使っていたり、ちゃんと毎日プライベートな時間があったりする。忙しい日は忙しいのだろうが、記録を1つ読んでみた結果、分単位のスケジュールがあるわけではなくて行動の描写の解像度が高いだけという感想になった。廊下を移動するのはスケジュールに入りますか？常に行動しているので、そういう点では忙しいだろうが、僕の想像が極端すぎた。

昨日から引き続きコーディングテストを進める。サンプルのデータが弱すぎるのでかなり心配になる。ジャッジしてくれても、正常に終了してファイルが出力されているかどうかしか教えてくれず、出力が要件を満たしているかは教えてくれない。それらの点数は提出を確定させて初めて知ることになる。

競プロで攻めていこうとしていたが、そんな狭い範囲の職業は存在しておらず、データを加工するポジション一般にカテゴライズされている。それについてのコーディングテストなので、例えばネットワークだったりSQLだったりの知識を求められていて、それらに対して競プロは何の役にも立たない。

多分どの設問もそのドメインの知識を持っている人にとってはやるだけの問題なんだろう。何も知らないような人をはじく目的か？

いやになってきたのでAOJ-ICPCを進める。

幾何ライブラリを設計した時の自分、何を考えていたんだ……。ちなみに以前、これで2時間くらいハマったことがある。その時は二度と間違えないという決意を抱いただけで済ませてしまったが、今日またハマりかけたので直した。元あったintersectをcount_tangentという関数名に変更して、新しいintersectは1<=count_tangent<=3を判定する。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1242

これかなりfloor_sumだと思って喜び勇んで実装したんだけど、実際は微妙なスキマを正しくカウントするのがどうしてもできなくてダメだった。ACコードでは辺に重なるマス目を愚直に列挙して、完全に含まれるマス目は平面走査でカウントする。

情報理学IIのレポート提出期限が明日に迫ってきているので、する。フーリエ級数とかの問題で重めの積分計算を要求される。計算が必要な個所は途中計算も書くこと、と書いてある。

グラフのプロットには計算機を使っていいらしいので安心。

かなり眠くなってきたので布団に近づいたところ、一瞬で吸い込まれてしまい、無事寝落ちした。

11/04(水)

午前5時半に目を覚ます。寝落ちしたことに気づいて絶望する。レポートが終わっていない。

いつもなら二度寝するのだが、今日は起きることにして、レポートを進める。面倒な計算をしたりWolframAlphaに投げたりして、とりあえず手で書くパートは終わる。あとはグラフのプロットをいくつかする。

グラフィカルなことは何もわからないけど、とりあえずJupyter notebookってやつを使えばよさそう。適当にググってコピペしながら書くと、グラフがプロットできた。凡例をグラフの外に表示したりとかも調べれば簡単にできて、うれしい気分になった。これを印刷する必要がある。

まず、ブラウザを拡大してスクリーンキャプチャしてみる。キャプチャしたものをWordに貼り付けて印刷すると、ぼやけてしまいなんとも悲しいグラフになってしまった。

TLに質問を投げつつちょっと調べてみたところ、画像としてダウンロードできるらしい。今度はこれを貼り付けて印刷したが、まったく同じぼやけ方をしていた。人からそれっぽい方法のリプライが来ていたのだが、僕はちょうどこのあたりであきらめてしまい、結局ぼやけたままのグラフを提出することにした。

そんなことをやっている間にちょっとサークルのSlackを確認すると、公欠届1人分をお願いし忘れていたことに気づいた。冷汗が出た。

幸い、11/05までにもらえればよいとのことだったので、まだ1日時間がある。今日顧問の先生にお願いして、今日の夜か明日の朝に返ってきてすぐ渡せばギリギリ間に合いそうだ。急いでファイルを作成し、先生にSlackで送ろうとしたが、まだ午前7時台だったので通知がOFFになっているらしい。このような場合、通知がONになったときに一気に送られるのだろうか？ちょっと自信が持てなかったので、通知がONになるのを待ってから送ることにする。

これまでは公欠届が出来上がってから各人にチェックしてもらっていた。学籍番号や氏名などがもし間違っていた場合は、署名と押印をもらうところからやり直しなのだが、それくらいの時間の余裕はあった。（今考えると、先生に負担を押し付けていることになってあまりよくなかった。）

今回はもう間違っていたら間に合わないので、同時にチェックしてもらうことにする。8時を過ぎて、先生の通知がONになったので、メンション付きでファイルを送った。送った後すぐにチェックしてもらった人からレスポンスがきて、間違いはなかったらしい。まさかこんな朝早くにレスポンスがあるとは思っていなかったので、チェックの結果を待たなかったのはしょうがない。

ともかく、これであとは先生からファイルが返ってくるのを待つだけ。先生がどれくらい忙しいのか全然想像がつかないのだが、結果だけ言えば午前9時半に返ってきた。こういう小さな用事は見た瞬間に済ませることにしているのかも。

ともかく、これで僕のミスのカバーが完了した。サークル運営にかかわることでミスをすると他人に迷惑がかかるので、ちゃんとToDoリストを整備しておく必要がある。今回のミスは、公欠届申し込みの締め切りを設定したあとにそのことを別の場所にメモしていなかったことが原因。誓約書まで書き終えて安心して、サークルSlackを放置していた。

レポートを提出する。山の上の研究室まで行って提出しなければならないらしい。このオンラインのご時世に物理的なレポートを求める必要性はどこにあるのか？まあ求められたものはしょうがないので出しに行く。思い返してみれば、前期は結局山の上に行っていないはずだから、都合8か月ぶりの青葉山なのか。

数学系研究棟の近くの駐輪場に原付を停めて、研究室まで歩く。目的の研究室は理学研究科合同C棟という少し離れた建物に入っている。道路沿いに進めばすぐ着けるのだが、洒落っ気を出して大学の中、建物の間を縫って歩いて行こうとした。

迷子になった。

思ったより移動できない段差が多い。あと工事をしていていくつか道が通れなかった。とりあえず大きな道路に出たい。方向だけ定めて深さ優先探索（もしくは右手法）をしたところ、うっかり研究室の建物を大きく超えてもっと先にある地下鉄の駅の出口まで歩いてしまった。このあたりの話は青葉山キャンパスマップを見るとわかる。

たいぺーと待ち合わせていて、合流した。提出は間に合った。本当はもっと余裕があったはずなのだが……。

同じ建物にレストランが入っていたので、そこで昼食を食べようとしたが、なんだかミールカードが使えなさそう。あきらめていつもと同じ原付を停めたところの学食に行く。食べ終わって生協でけんちょんさんの本を買った。

帰ってきてハーメルンを読みつつAOJ-ICPCを埋めた。少しだけAtCoderもした。

bcでリアクティブ問題を解いてみたところ、特に出力回りをいじらなくともACできた。バッファリングは行われていないようだ。よく考えてみればbcは対話型の言語なので、当たり前の話かもしれない。

午後8時を回ったあたりで眠気が強くなる。うっかり椅子の上で意識を飛ばしてしまった。半ば寝落ちを覚悟して、午後9時半くらいに布団にダイブし、当然のように寝落ちした。これもう普通に寝てるだけじゃないの？と思いそうになるが、忘れてはいけない、寝る前にするべきルーティンを一切こなさずに寝ているからこその寝落ちなのだ。あと電気とかエアコンとかつけっぱなし。

11/05(木)

午前4時半、起きる。異常。どうしようもないので、今日はどこかでお昼寝をすることに決める。

今日は何もないし明日はICPC国内予選なので、ずっとAOJ-ICPCを埋めることにする。これまでも埋めてはいたのだが、日記に書こうとしても特に書くことはないため、文章にはあまり出現しない。今日もずっと埋めてたけど本当に書くことがない。

www.youtube.com

このサムネイルの画像がなんのゲームか探している、とのツイートがTLに流れてきた。僕はつなこさんの絵が好きなので見た瞬間にわかるのだが、これはつなこさんの絵。pixivにはなくて、サイトにもなかったので、「つなこ」で画像検索すると、似たキャラクターの画像が引っかかる。詳細を見ると、フェアリーフェンサーエフというゲームだった。公式サイトを見ると確かにこのキャラクターが登場している。

探していた人に教えたはいいものの、そもそもこの動画の詳細の部分にPicture : Fairy Fencer Fと書いてあったらしい。目がついていないことで有名。

つなこさんはデート・ア・ライブのイラストを担当しているイラストレーター。ラノベのイラストレーターなら少しはわかる。たいていは同じ人が同時期にいくつも担当していて、すごい。

ASCII Expressionに挑戦してみた。領域の上下左右だけ持てば余裕だろうと高をくくっていたのだが、そんなことはない。普段の構文解析と同様にするためには、問題文にあるbaseを調べておき、左端を参照で持って縮めていく必要がある。あとスペースの入り方を考えて関数からreturnする前に一つずらしたりなども普段とは違うところ。

結局80分かかった。しかも1WAしたあとテストケースを見ているので、実際にコンテストで出たらどれくらいかかるかは分かったものではない。まあミスは大したことない場所1か所なので、自力で見つけることが不可能ということはないだろう。べき乗の時に領域の外を見る可能性があったのだが、そこには基本'.'しかないだろうと思ったら文字列をはみ出して'\0'を見ていた。

そんなことをしていたらお昼寝のタイミングを逃しそうになった。午後8時、布団に入ってお昼寝する。午後11時に頭の痒みで起きた。無意識に頭皮をかきむしっていたらしく、枕カバーに抜け毛が大量についていた。確かに昨日からシャワーを浴びていないが、1日でここまで耐えがたい痒みに襲われるのはちょっと尋常ではない。眠気も少しあるが、それよりなにより頭が痒くて仕方ないので、急いでシャワーを浴びた。

Lowlinkのライブラリは、グラフが連結である場合にしか対応していなかったみたいだ。

週記（2020/09/14-2020/09/20） - kotatsugameの日記

僕の橋検出ライブラリはグラフが非連結のときにバグる（というか1つの連結成分しか見てくれない）というのは以前にも書いたかもしれない。

週記（2020/10/05-2020/10/11） - kotatsugameの日記

これを直す。引用するために過去の週記を漁ったのだが、こんなに昔の話だったのか。とりあえず螺旋本を読んでLowlinkの気持ちになる。直し方については、まあどう考えても最初のdfsのスタート頂点を0固定ではなくループを回して探すようにすればよい。dfsの時にカウンタ変数を参照渡ししていて、これの値をどう扱うかでちょっと考える必要があると思っていたが、別にそんなことはなかった。毎回リセットしてもよいだろうし、しなくても動く。

Library Checkerの二辺連結成分分解にACして、verify完了。多重辺と逆辺（無向グラフなので）の区別をどうするかちょっと困ったが、隣接リストを舐めるときに親が2回以上出現したら多重辺であると考えて問題はない。

親の顔より見た親の顔。

今日だけで550点を中心に16問も解いた。洗濯物を干したり日記を書いていたらいつの間にか午前4時半になっていた。この部分を書いている最中にFHCのTシャツに関してメールが来ているのを見つけたが、さすがにもう寝ないと明日が怖い。

11/06(金)

昼前に起きる。本当はもっとしっかり寝ておくつもりだったが、二度寝に失敗して起きる。金曜日なので課題が出ていた。

メールを確認したところ、急に12時半までのレポートが生えている。 週記（2020/10/12-2020/10/18） - kotatsugameの日記 これに関して、先週の金曜日は特に何も書かなかったが、2限の講義ではレポートが出なかった。今日はどうなるだろう、まだ出ていないが……と待ち構えていたのだが、どうやら今日は学祭の日で休講らしい。

週記（2020/10/26-2020/11/01） - kotatsugameの日記

これ。なんだかんだ言ってまだ3回目くらいのようだ。今日の課題は午前10時に投稿されていて、提出期限は17時だった。問題自体は自明も自明なものだったので、期限が延びているのはよくわからない。これからずっと17時期限なら、少しは許せる。いややっぱり当日に課題投稿するの許せないな。

あまりに自明だったので、問題が隠されていないかとか誤読をしていないかのチェックに少し時間を使った。

スキャンして提出し、学食に行く。学食と同じキャンパスの建物からICPC国内予選に出る予定。味噌汁が好きなので毎食味噌汁を注文するようにしているのだが、信じられないくらいしょっぱい。あまり客が来なくて、蒸発した結果濃縮されていると予想している。耐えられないので、生協の一言カードで苦情を入れた。

生協でお菓子と飲み物を買いつつ、マルチメディア棟の演習室に行った。数人人がいるが、サークルメンバーかどうかはわからない。オンラインなのでメンバーの顔を知らないまま活動している。昨日寝ながら考えていた500点問題を1問通しつつ、リハーサルもこなして、チームの集合を待つ。

これ以降コンテスト中の話に関しては参加記を書いたので、そちらを参照されたい。

kotatsugame.hatenablog.com

打ち上げの後の話は、文章量が多くなりすぎたので別の記事に分割した。

kotatsugame.hatenablog.com

部屋に戻ってしばらくはパソコンの前でボンヤリしていたが、午前9時くらいに寝た。

11/07(土)

午後5時くらいに起きる。HTTF予選が始まっていた。とりあえず1Byteの解と自明な解を投げる。すぐには方針が浮かばなかったし、ほかにやりたいこともいくつかあったので、HTTF予選に関してはこれで終わりということにする。

AOJ-ICPCが更新されていた。つい先日解いたばかりの問題が容赦なく除外問題に行っており、感慨深い。

昨日からずっと考えていたコードが1Byte縮んだ。

atcoder.jp

4^8全探索をするのだが、数値を4進数に変換するときに他の変数との兼ね合いでわざわざ4を掛けている。つまり、a桁目を見たいのだが、aが1-indexedなのでi/4^a%4とはできず、i/4^(a-1)%4あるいはi*4/4^a%4としなければならなくなっている。

このことは、4^9全探索をすることにすれば解消できるが、どれだけ試してみても時間制限に引っかかってしまう。内部のループを減らしたりもしてみたが、どうにもコードテストで2200msくらいかかってしまう。なんとも絶妙なところだ。

この問題では、以前まで僕のPerlが最短だったのを、ある人と僕によって都合6回Bashによる更新が行われた。上のコードはその6回目だ。5回目の更新を見て、もうだいぶ短縮合戦をしたのでこれは勝てないと思い、しばらくは別言語で縮まないか考えていた。結果そこそこ早い段階でRuby129Bのコードが完成し、さらにずっと時間を使って考えていたのだが、そこからはついぞ縮めることはできなかった。

このコードもいずれまた取り返されるのかもしれない。他の人のコードを縮めることより、自分のコードを縮めるのはよっぽど難しい。僕もこれ以上縮まないことを十分確認したつもりだが、やはり感覚としてチャレンジャー側で考えているのと防衛側で考えているのは違う。

yukicoderが2週間ぶんたまっていたので、ほどほどに解いておく。数学コンテストを銘打っているほうは問題のレベルが高いのであんまり解いていない。昨日行われたコンテストのほうは全問解けた。最後の問題はbitDPで解いて、面白かった。C問題は何となくそれっぽい解法をひねり出したけど、解説で1手交代のはずのお互いの行動をそれぞれ別々に考えているのが納得いっていない。あとはまあ、自明かな……。

ICPC国内予選の参加記を書いた。後ろのほうにお気持ち表明パートを付け加えようとしたけど、書きたいことがまとまらないうちに頭の中でどんどん話がずれていって、そのことに気づいた瞬間に書くのを諦めた。コンテスト終了直後は気が立っているのもあっていろいろ強い言葉を使いそうになったけど、1日置いた今、そこまでの熱意はない。ただ何も書かないのも腹ふくるるわざ、ということでツイートをする。

AOJ-ICPCに追加された問題を埋めようとした。最近の問題なので、コンテスト会場で読んだ覚えのある問題がたくさん並んでいる。ちょっと詰まってしまったので布団に寝転んだところ、寝落ちした。午前5時半くらいだった。

11/08(日)

正午、起きる。結構鮮明に夢を覚えていたので、文章にまとめてツイートする。覚えているうちに、と頑張ってガーッと書いたら8連投ぶんにもなってしまった。

昨日の続きでAOJ-ICPCを解いた。とりあえず400点問題までは再度埋めた。

明日月曜日の講義開始前までが期限のレポートがある。コンピュータグラフィックスという講義だ。普段の小テストとか演習は存在しないので、これまでノータッチだった。そろそろ始めないと間に合わなさそうだと感じてレポート問題を見ると、アフィン変換の行列を作ったり移動をシミュレートしたりするだけの簡単な問題が少し並んでいるだけだった。拍子抜けしたが、別に頭の中で三次元のアフィン変換をシミュレートできるわけではないので、ちゃんと検算もしておく。僕の好きなOctaveを使うと便利！と思っていたが、入力が面倒だった。

書き上げて提出する。夜のABCまで結構時間がある。ただし、眠いからと言ってお昼寝をするほどの時間はない。昨日と一昨日の分の日記を書くことにした。寝落ちとかでバタバタしていて書いていなかった。

日記の木曜日の部分を読んで、FHCのTシャツに関するメールをその後確認していなかったことに気づいた。慌てて確認したところ、「第三者からのメールが来週末までに届くので」と書いてあって安心。まだ届いていない。

午後6時、第4回PASTの受験期間が終了した。直後に問題が過去問として公開されるものだと思って、AtCoderのトップページをしばらく更新したりして見ていたが、全然公開されないので、あきらめて日記を書くことに専念した。

午後8時ごろにPASTの問題が公開されたので、解き始める。相変わらずコードゴルフには向かない問題だらけ。Iまで一息で解いたが、中央値ではなく最大値を求めていたり、答えのmodを取り忘れたり、グリッドの横幅のところで縦幅を使っていたりといくつかWAが出た。Jを読んで少し詰まったのでシャワーを浴びることにした。冷静になると明らかだったので、解く。そのあとKも解いて、ABC182が始まった。

全完4位だった。E問題で同じ処理が2回出現したときにコピペしたのだが、1か所HにすべきところをWのままにしていた。そもそもこういう問題ではH!=Wのサンプルも用意しておいてほしい。ただ、このペナルティがなくても2位のようだ。

全完した後コードゴルフをしていたのだが、A問題が1Byte縮んでかなり残念な気持ちになった。一応最初に解いてから少し時間を取って確認したはずだったのだが。さすがに30分経過しているし誰かが先に出しているだろうと思ったが、終わってふたを開けてみれば単独で最短コードが取れていた。

B問題なんかは、C++を使うべきではなさそう。Rubyのmax_byメソッドを使うべきシーンでは、ほかの言語で書くと少し面倒になりがち。比較のための値と、出力する値の2つを保持して計算する必要があるからだ。

Fはいつもの繰り上がりフラグを持つDPだと思って、それっぽい遷移を書いたらサンプルがあってそのままACしたので、あまりよく考えていない。解説を読むと、問題の言いかえだったり探索範囲の絞りこみだったりをしていて、かなり難しそうに見える。

ひとしきりコードゴルフをしているとコンテストが終了したので、一応各問題の最短コードを確認した後、PASTに戻った。残り4問。M問題の計算量をよく考えないまま通したこと以外は、ほとんど詰まることなく駆け抜けた。かなり簡単なように感じた。

M問題の解説を読んだところ、計算のスキップする部分でUFを使っていた。僕のコードに照らし合わせると、どうやらUFで経路圧縮をしない場合だと考えることができそうで、十分間に合う計算量であることが分かった。

最近睡眠が下手くそで、寝落ちした挙句早い時間に起きて二度寝できないことが多い。今も結構眠いので、とりあえず週記だけ早めに投稿しておくことにした。毎週月曜日の昼頃になって投稿しているのはあまりよくない。