競技プログラミング用 知識集積所
ABC437C - Reindeer and Sleigh 2
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
全パターンを探索すると明らかにTLE。
よって高速化が必要になる。
よって高速化が必要になる。
重さW1で力P1のトナカイ1と重さW2で力P2のトナカイ2、どちらかをソリに乗せることを考える。
トナカイ1を下ろしてトナカイ2を乗せると、重さがW2-W1増加して、力がP1-P2増加する。
したがって、(P1-P2)-(W2-W1)>0なら、この入れ替えはするだけ得、=0ならどちらでもよく、<0ならするだけ損ということになる。
これは、W1+P1>W2+P2と変形できる。
つまり、「重さ+力」が大きいトナカイを優先的に引く側にする貪欲法※が成立する。
トナカイ1を下ろしてトナカイ2を乗せると、重さがW2-W1増加して、力がP1-P2増加する。
したがって、(P1-P2)-(W2-W1)>0なら、この入れ替えはするだけ得、=0ならどちらでもよく、<0ならするだけ損ということになる。
これは、W1+P1>W2+P2と変形できる。
つまり、「重さ+力」が大きいトナカイを優先的に引く側にする貪欲法※が成立する。
解答例
注意点
力と重さが同じ場合、動く
なんとなく力が勝っていないといけなさそうなイメージをもつが、問題をちゃんと読むと同じでも動く。等号のつける/つけないを間違えないように。
重さ合計や力合計はlong long型を用いる
int型を超える計算が必要になるので注意。
