https://atcoder.jp/contests/kupc2019/tasks/kupc2019_g ジャンル 構築 解説 https://atcoder.jp/contests/kupc2019/submissions/7962102 そういう作り方の構築は初めて見たかもしれない。 最小は4×4なので、とりあえずこれから作ってみるが、もう作ってあ…

https://atcoder.jp/contests/kupc2019/tasks/kupc2019_e 解説 https://atcoder.jp/contests/kupc2019/submissions/7961395 最後に相手ターンでスタート地点に戻せば、こちらの勝ちになる。 各木に一旦入ったら抜け出すまでは他の木は関係無くなるので、木に…

https://atcoder.jp/contests/kupc2019/tasks/kupc2019_c 解説 https://atcoder.jp/contests/kupc2019/submissions/7961542 最初の分銅は1gにする。 すると、1～Kgは測れる。 次に用意する分銅はK+1としたい所だが、(2K+1)gを用意すればいい。 例えば、K+1g…

https://atcoder.jp/contests/kupc2019/tasks/kupc2019_f 前提知識 二次元累積和 解説 https://atcoder.jp/contests/kupc2019/submissions/7958884 最適方針として、なるべく1人の勇者に攻撃を集中させるのが得策。 なんとなくDP感がするので、DPで考えてみ…

https://atcoder.jp/contests/kupc2019/tasks/kupc2019_a 解説 https://atcoder.jp/contests/kupc2019/submissions/7955954 あるテーマが選ばれる可能性を最大化したい場合は、そのテーマにX票すべて与えるのがいい。 よって、X票すべて与えたときに投票数が…

https://atcoder.jp/contests/kupc2019/tasks/kupc2019_b 前提知識 UnionFind DP 解説 https://atcoder.jp/contests/kupc2019/submissions/7956197 ナップサック問題の派生であるが、追加されてる条件について考えてみる。 aとbを一緒に入れる必要があり、b…

https://atcoder.jp/contests/kupc2019/tasks/kupc2019_d 前提知識 カタラン数 解説 https://atcoder.jp/contests/kupc2019/submissions/7958349 順列を2グループに分けていく問題であるが、小さいほうから確定させていくことを考える。 01を作る場合は 千| …