ここ数日午前が虚無になっている。やることが定まってないからな気がする。
散歩した。未探索のエリアを歩いていたら全く予想していなかった道の繋がりを見つけた。これは楽しい。
今日解いた競プロの問題。
競プロ典型90問
077 Planes on a 2D Plane: $(AX_i, AY_i)$の飛行機に対応する可能性がある飛行機は8通り以下なので、超点数=2N, 辺数≦8Nの2部マッチングで解ける。計算量は$O(VE)$であり、$16N^2=$6.4×10^9$になるので制約的に厳しいかと思ったのだが、ググって出てきたライブラリをそのままペタ！したらなんか余裕で通ってしまった。ちょっと罪悪感。実際に最悪計算量になることは少ないと聞いたことがあるからそういうのが影響しているのだろうか。解説を読んだところ、Dinicは二部マッチングなら$O(N\sqrt{N})$で通るらしい。
なんか嫌なので自力で小課題も多少解いた。小課題1は順列全探索してしまえばよい。8進数もやったがなんかバグって直せなかった。小課題2はAとBを一緒くたに並べてソートして、端から対応するものがあるかどうかを探していけば良い。
078 Easy Graph Problem: 全部調べればOK。$O(V+E)$なので入力が受け取れれば計算も間に合う。
079 Two by Two: 端っこを変えるには端っこに操作をするしかないので、そこから帰納的に全てのマスについて操作が確定してしまうやつ。端から全部やっていけば良い。それで無理ならどうやっても無理。
解説を読んだら「操作順序に拠らない」という話だった。言われてみればそれはそう。
今日摂取したコンテンツ。
面白い整理だなと思った。
http://garbage-coll.com/arasuji/overtherainbow.html
かなり面白かった。少しずつコメント数とかが増えていっているのとか芸コマ。
ちなみにTwitterで炎上していた西原氏の騒動の件で回ってきた。現実が追い付いてしまっている…
Categories: 未分類