ABC245E マッチング問題．箱を大きい順に優先して使っていく． 入るチョコの内，なるべく大きい物を割り当てたい． 箱とチョコを両方まとめて入れ物 \(s\) に入れておく． 辞書順で大きい順に並べておく． \(s\) から順に取り出していく． チョコが出てくる…

ABC252E Dijikstra tree を求める問題． Dijikstra 法は，最短経路を求めるアルゴリズムよりも高性能で， 最短木を求めるアルゴリズム である． 実装普通に Dijikstra をして，直前の遷移するときの edge を記録しておけば Dijikstra tree が手に入る． 注意…

dp を累積和で高速化する． \(dp_{i,j} := [0,i)\) まで，last \(j\) のときの答えとする． 今を\(y \in M\)，直前を \(x \in M\) とすると， 遷移は\(dp_{i+1, y} += \sum_{x \in [l,r) } dp_{i,x} \)となるので，累積和で高速化できる． ABC253E 使ってい…

ABC257E 決め方の優先順位 \(x\)の桁数の max 桁数を固定したとき，使う値を大きくする 各桁に使う値の multiset を固定したとき，大きい順に並べる これらを優先順位の通りに求めればよい． 2つ目の条件，桁数を固定したときに使う値を大きくするのは， 9 …