ABC310F 部分和 DP. \(M := 10\) とおく． \(s \subset [0,M] \) を作れる数全体とする． 今のさいころの出目 \(x\) によって場合分け． \(x \in [1,min(a_{i}, M)]\) の場合:作れる数の集合が \(t := s \cup \{y+x \ \vert \ y \in s\}\) に変わる． \(dp_{…

ABC312F 3つタイプがあるが，いずれも貪欲に取れる． どれか一つを全探索しよう． 缶切りを使わない缶全体， 缶切りを使う缶全体， 缶切り全体 をそれぞれ \(a,b,c\) とおく． \(a,b,c\) を全てソートしておく． \(a\) を全探索する． \(i \in size(a)\) に…

ABC312E 何を全探索するかを考えるのが基本． 座標の範囲 100 と小さいので，3次元で全探索しても \(O(100^{3})\) で間に合う． よって，それを軸に考える． 座標で全探索するということは，境目になる面を全探索しているのと同じ． しかし，面を全探索する…

ABC312D DP で全探索．\(dp_{i,x} := \) \([0,i)\) まで調べ終わって，値が \(x\) の場合の数．ここで，( を +1, ) を -1 として，先頭から調べて累積和をとる． かっこ列になる必要十分条件は，常に和が 0 以上かつ，最後に和が 0になること． 遷移は，今調…