今日解いた競プロの問題。
ABC295-G: まず、初期状態でDAGであることが分かる。初期状態での種類2のクエリの答えをあらかじめ各頂点について計算するのは番号の大きい頂点から順に計算していけば容易。
そしてどの頂点も入次数1なので、u→vのパスが存在するとしてvから辿っていこうと思ったらそのパスは一意に定まる。u→vのパスが存在する状態でv→uという辺を張ったら、元のu→vのパス上にある頂点は全てまとめて相互に行き来可能ないわゆる強連結成分になり、強連結成分の中において種類2のクエリの答えは同一になる。種類1のクエリを処理していくと強連結成分がだんだんまとまっていく感じになることが分かる。値がまとまっていくことを考えるとUnionFindを使えば良さそうということが分かる。
これで一応正しい答えは出るが、種類1のクエリを処理するたびにパスを全て調べた場合、超パスが長い頂点同士に辺が張られまくるとTLEする。そこで、ある強連結成分の一番番号が小さい頂点(クエリ2の答えに等しい)に移動することにすればすでに連結させた部分のパスを飛ばすことができる。同じ辺を2回連結させることがなくなるので、UnionFindの結合操作は$O(N)$回に収めることができる。
久しぶりに絵を描いた。サークルで作っているゲームの素材。
簡単な落書き程度のつもりなのにひどく時間がかかってしまった。アニメ素材は時間がかかる。かなりコマ数多めになってしまったし、いい感じの手の抜き方とか覚えるべきなのだろう。
筋トレをした。今日はスクワット。この間テレビでたまたまコツの説明をしていたのでそれを思い出しながらやってみた。
「膝をつま先より前に出してはいけない」という話で、どうやったら出来るのか分かっていなかったのだが、すねを垂直にして尻を後ろに突き出す意識でやると良さそうだということが分かった。
あと、ブルガリアンスクワットを今まで膝を胸に付ける意識でやっていたのだが、「上半身を垂直に上下移動する」という意識でやってみたらこっちの方が効きそうな感じがした。正直どっちが正しいのか自信がないが、しばらくこれでやってみようと思う。
今日摂取したコンテンツ。
京大の卒業式でゼレンスキーの仮装をした人の卒論。思った以上に読み応えがある。
Categories: 未分類