今日やった競プロの問題。
競プロ典型90問
011 Gravy Jobs: 単純に階乗全探索$O(N\cdot N!)$で$N\leq 8$はクリア、そしてbitDPで$O(N\cdot 2^N)$に高速化し$N\leq 20$をクリア。ここまではまあ知ってるという感じだが、$N\leq 5000$は分からん。制約エスパーすると多分$O(N\max D)$のDPか貪欲みたいな感じので行けるんだとおもうが、検討が付かない。区間スケジューリングの匂いはするが、どう使えばいいか思いつかず。
解法を見たらソートした後DPだった。なーるほど。そうするとどの仕事をやった～やってない～というのを個別具体的に管理しなくてよくなるのか。区間スケジューリングは知っていたが、DPと組み合わせるのは初めて認識した。
気付いたけどこれ問題設定として「締め切り」を与えてるから有情だな…「$D_i$日目までに始めなさい」だと解けるもんも解けなくなる人続出する気がする。
012 Red Painting: UFやって終わり。簡単だがあまり見かけないタイプな問題に感じるので(グリッドとUFの組み合わせだからか？)、詰まる人は詰まるんだろうなーという気がする。教育的。
013 Passing: 両側から全点間距離算出して終わり。これはどの道も双方向に繋いでいるので、初心者でも気付ける人は気付けるだろうが、これが例えば有向辺とかだったら途端に凶悪になる気がする。逆辺張るだけだが。
014 We Used to Sing a Song Together: 直感的にソートしたくなるのでソートして終了。証明としては「入れ替わってる部分があったら自明に改善できる」という感じ。こいつは非常に簡単なパターンだったので一瞬で出来たが、交換で改善可能・不可能というのを軸とした貪欲法の証明はちょっと難しくなると自分は途端に出来なくなる。上位の競プロerにはみんな同じに見えてるんだろうか。
サークルのブログ記事とかを書いていた。文章を書こうとすると何かにつけ無限に凝ってしまうのでよくない。
たまたまLiveSplitについて調べていたのだが、あるブログ記事が大昔に作った洞窟物語用のAuto Splitterを紹介していてはちゃめちゃに嬉しくなってしまった。なんだかんだで自分の作ったものが誰かに触れられていると嬉しい。
しかしこんなの洞窟プレイヤー以外がどこから辿り着いたんだ？
今日摂取したコンテンツ。
https://togetter.com/li/1263478
昨日は夜更かしして今朝も早起きして昼寝も二度寝もしなかったので、今日は早く寝る。
Categories: 未分類