今週の胎界主を読んだ。純子の最悪度が高まってる…
他人のもの勝手に捨てるのはかなりアウトだろと思うが、他人(自分)だから微妙になんとも言えん感がある。たまきの状態はなんかこう…なんだこれ？語尾ワホって。元気そうではあるが、妹はあまりいい気分ではなさそう。そういえば一応胎界主ということだった気がするが、今も悪魔的には胎界主にカウントされるんだろうか。
腹をなでるのもまたなんかの暗喩な気がするがなんだろうな。自分の弱いところを他者にさらけ出して触らせる行為、って考えるとかなり意味深長な気がするが、どうつながってくるのか見えない。
純子の好き判定もなんなんだ。
今日解いた競プロの問題。
ABC251-F: 素朴な発想として、T1は頂点1からすべて1本につながっていたらOK、T2は頂点1にすべての頂点が付いていたらOKと考えられる。が、どのグラフでも可能ではない。ということで、ちょっと変形して以下のようなDFSを考えてみるとどんなグラフでも成り立つことがわかる。
T1: 頂点1から始めて、ある頂点を見ているとき、隣接頂点の中でまだ頂点1と連結になっていないものがあったら接続し、その頂点に移動して同様の操作をする。全ての隣接頂点について操作をしたら戻る。
T2: 頂点1から始めて、ある頂点を見ているとき、まず全ての隣接頂点について、頂点1と連結になっていないものがあったら接続する。それから接続を行った各隣接頂点について、そこへ移動し同様の操作をする。
T1が問題ないことのざっくり証明。仮に親子関係にない頂点A,Bの間に採用されていない辺があるとする。頂点A,BのLCAを頂点C、頂点Cの隣接頂点のうち頂点A,Bの祖先になるものをA’, B’とする。頂点CでのDFSにおいて、A’のDFSが完了しているのならBもたどれる筈なので、A’とBは親子になっていなければならない。しかし実際にはそうなっていないので矛盾が導かれる。
T2が問題ないことのざっくり証明。仮に親子関係にある頂点A,Bの間に採用されていない辺があるとする。Aが祖先、Bが子孫とする。AのDFSにおいて、Bとつながる辺があるならば採用されているはずである。なので矛盾。
DFSによる分割統治法自体にそこまで苦手意識はないのだが、こういう分割統治法をやると全体としてこういう性質が保たれるみたいなのを考えるのはむずすぎる。というか、解説を読んだところこれは考察問ではなく知識問らしい。DFS木とBFS木というのがあるとか。
今日はすさまじい日射ではなかったので久々に散歩に出た。新たな大通りの一つを攻略。自宅回りの地理について、東西方向についてはかなりの広範囲が頭に入ってきた気がする。一方南北方向はあまり探索できていないことに気付いた。ちょっと探索範囲を変えてみるか。
Categories: 未分類