ずっと放置していたNew Super Hook Girlの「QPICからの挑戦状」をクリアした。星にフックをひっかけられることに今さら気付いた。
裏スノーマンはまだ無理だなあ。時間制限が厳しすぎる。
ABC289に出た。2週間ぶりにプロコンとなる。黄perfだったので上々。
A: やるだけ
B: 若干悩んだがstackで解決
C: 制約が小さいので2^M通り全探索してよい。集合はビットマスクで管理すると便利
D: DはDPのD
E: 2人がいる位置を管理できればよいので、元のグラフにおける2頂点の組を頂点としたグラフを考えれば良い。遷移についても、元のグラフにおいて2人が通る辺の組を辺とみなせばよい。頂点数は$N^2$、辺の数は$O(M^2)$となるのでBFSすれば$O(N^2+M^2)$で間に合う。最初ダイクストラを持ち出しかけたがBFSで十分だった。
F: 手を動かしてみると分かるが、(tx,ty)に1回で辿り着けるような座標を集めると長方形になる。ただしx,yそれぞれにおいてtx,tyと偶奇の一致する座標のみの歯抜け長方形になる。2回でたどり着けるような座標も同様の歯抜け長方形になる。これは計算で出すことが出来るので、d回で辿り着ける長方形を順に計算していけば判定が可能。
手順の復元も理屈はそんなに難しくない。まず到達可能範囲の長方形を毎回記録しておく。d回で到達可能と判定された場合、(sx,sy)から1回でたどり着ける範囲の長方形と、(tx,ty)にd-1回で到達できる範囲の長方形がオーバーラップする範囲の長方形を割り出す。そしてこの長方形の中であればどこに移動しても良い。これを繰り返せば(sx,sy)から(tx,ty)に移動する方法が復元できる。
G: コンテスト終了後にちょっと冷静に考えたら$O(NM)$の解法は出来たが…CHTを使うやつらしく、残念ながら今の自分の発想にはなかった。多分時間をかけても解けなかったと思う。行かなくてよかった。
しかし、残り10分くらいだったとはいえ$O(NM)$解法くらいはコンテスト中に導きたかったなあ。
Vulkan入門の執筆が捗らないので、気分を変えてサイトデプロイ環境の整備をした。Githubが潰れてもいいように、オンプレのGiteaでリポジトリをホストすることにした。(Giteaを載せているConoHaのVPSが落ちない保証がどこにあるのだ？)
なんか書いたことを完全に忘れていたのだが、デプロイ環境を作る記事を過去に書いていたらしく、大変に参考になった。
ちょっと今日中に完備することはできなかったが、多分明日で終わるだろう。完成したイメージをもうちょっと具体的に持っておけば今日中に終わってた気がする…
筋トレをした。今日は腹筋。
Categories: 未分類