昨日は遅くまで起きていたので今朝は寝坊してしまった。日課のラジオ体操や朝の読書とかも出来なかった。
サークルで使う資料作成作業を進めた。正直あまりはかどらなかったが、スケジュールを決めていたおかげで多少能率は落ちながらもゼロでない進捗を産めた。
少し昼寝をした。以前に30分と設定して見たら1時間以上寝てしまったので、今日は20分に設定してみた。何やらかなり上手くいった。自分は寝つきが悪いので20分で寝れるか微妙だったのだが、十分に睡眠不足だったからということなのか、ちゃんと20分で寝落ちて目覚めることができた。これはかなり有意義な収穫。
午後はあまりスケジュールを決めていなかったため、良く分からない時間になってしまった。一応競プロはしていたが。
スケジュールを決めたうえで少し達成できなかったならば、それは単に分かりやすい「ちょっとした乱れ」であってむしろある方が健全なくらいだと思う。が、スケジュール自体を決めかねていたのはちょっとな～と思う。
ここ数日朝にその日やることを決めているので、今日は寝坊が波及してしまった。寝坊した場合の1日の立て直し方みたいなのを考えた方がおそらく良いが、上手いのが思いつかない。
「朝食」「軽いストレッチ」あたりを最低限入れて次のスケジュールに間に合わせるとかが無難だろうか。
今日解いた競プロの問題。
ABC210-E: 最小全域木にしたいところだが、残念ながらNが大きいのでそのまま適用することはできない。
とりあえず一番コストの低い辺だけ使って全域木に出来るなら儲けものなので、とりあえずある同じ操作$(A_i, C_i)$だけ使って繋げられるだけ繋げてみることを考える。すると、それぞれ$N/gcd(A_i, N)$の頂点を持つ$gcd(A_i,N)$個の連結成分に出来ることが分かる。実験したら多分この式で合ってるだろうみたいな感じで出したので厳密な証明はしてない。これにかかるコストは$C_i \times (N/gcd(A_i, N) – 1) \times gcd(A_i, N)$である。
これらの連結成分は回転対称であって、こっからさらに別の操作を用いて繋げていくにしても、元の連結成分が$X$個ならばそれをつなげて$gcd(A_i, X)$個にすることができる。要するにNに対してどんどん$A_i$とのgcdをとっていって1にしようみたいな話になる。あとはそのための最小コストが求まれば良い。
dpなりダイクストラなりを使えば最小コストを求められる。連結成分の数は$N$の約数にしかなり得ない。Nは$\leq 10^9$と大きいが、約数は$O(\sqrt{N})$で列挙でき、約数の数それ自体は高々1400個程度である。なので$(Nの約数)$個の頂点と$M\times (Nの約数)$個の辺があると考えても十分間に合う。
なかなか気持ちの良い問題だったのだが、オーバーフローに気付かずWAを出しまくった。初歩的なミスに気付けないのもーやだ。
今日摂取したコンテンツ。
https://logmi.jp/tech/articles/326777
例のRustのイベントの大雑把なプレゼン内容。こんな感じのこと話してたのか。思ったよりWeb初心者向けの知識も紹介している感じ。
Actixは一度いろいろ使ってみて割と(HTTPクライアント周り以外は)分かりやすいなという感想だったのだが、そのときはミドルウェアとかDI周りはいじっていなかったな。
そもそもミドルウェアというものの良さを自分が良く分かっていないという面がある。自分が触った他のWebフレームワーク、Laravelとかdrogonとかもミドルウェアはあったが、自分は結局大して触っていない。なんか多分ある程度の規模のものを開発しないとありがたみが分からないんだろうな。
腕立てをやった。昼間に気力が湧かなかったので夕飯後になってしまった。
昨日のスクワットの筋肉痛が少しある。ちゃんと効いているっぽくて嬉しい。
Categories: 未分類