https://atcoder.jp/contests/abc160/tasks/abc160_c 解説 https://atcoder.jp/contests/abc160/submissions/11325671 ある家iから出発してすべての家を回る最短経路はi -> i+1 -> i+2 -> ... -> N -> 1 -> 2 -> ... -> i-1という感じになる。 つまり、1パタ…

解法 簡単に書いておく。 貪欲法で解ける。 先頭から埋めていくことを考えると使える要素がどんどん少なくなっていく。 だが、末尾から埋めていくことを考えると使える要素がどんどん多くなっていく。 多くなる方がうまくいく場合が多いので、そっちでまず考…

前提知識 O(3N)のbitDP 解説 簡単にまとめておく。 サイコロで出せる合計の目の上限は2Dなので、Tが2Dを超えていたら、その部分は絶対余る。 なので、Tは2Dまでを考えればいい。 すると、bitDPができることに気が付く。 dp[msk] := 残っているペナルティトー…

https://atcoder.jp/contests/abc160/tasks/abc160_f 前提知識 全方位木DP 解説 https://atcoder.jp/contests/abc160/submissions/11325358 全方位木DPが分かっていないと解けない。 この問題で全方位木DPを学ぶには少し問題がややこしい。 入門問題としては…

https://atcoder.jp/contests/abc160/tasks/abc160_e 解説 https://atcoder.jp/contests/abc160/submissions/11320313 今回の問題では、2種類の取り組み方をブレンドして解く。 C個の無色のリンゴの中で使う個数を「全探索」し、そのパターンで「貪欲」にリ…

https://atcoder.jp/contests/abc160/tasks/abc160_d 解説 https://atcoder.jp/contests/abc160/submissions/11318810 今回の問題で最も重要なのは、制約に気が付くところにある。 Nは最大2000なので、O(N2)が通る。 計算量は107くらいを上限にしてとりあえ…