217.1

久し振りに全部解けたセット。一発完動ではないけれども。リアルタイムで出ていたら前二問解いておしまいだけれど、他の人達がザクザク三問目解いてしまう、という感じだろうか？

250

要素数が等しい整数配列が与えられるので、前者を並び替えて、後者とi番目の要素を比較したときに、大きくなる要素の値の和の最大値を答えよ、という問題。

後者の配列の要素を大きい順に調べて、それよりも大きい要素で一番大きいものをぶつけていく、というのをgreedyにやれば良い。こうすると前者の配列の中で、後者の配列の要素よりも大きくなり得るものは、後者の配列の要素の中から自分より小さいもののうち最大のものを取り出すことになる。

これ＋αの問題をどこかのmiddleの問題で見たような気がする。

600

x軸上に等間隔に並んでいる点が0度

900

複数の荷物を目的地に運ぶ時、任意の数を任意の場所に運ぶコストと、一つの荷物を単位距離運ぶコストが与えられるので、実現するのに必要な最小コストを求めよ、という問題。

多分ありがちな問題なんだろうと思いつつ、DPをしてみた。目的地順にソートして、最後に任意移動を行った地点と、運び終えた地点の二次元。一つずつ運ぶ場合には単純に最後に任意移動した点から運ぶだけ。任意移動するときは、直前の任意移動よりも今の任意移動に同行させた方が良い荷物がいくらかあるので、その分を補正するだけ。

で、問題自体は簡単なんだけれど、DPのテーブルをlong精度にしないとあふれるのと、long精度にしても初期値をある程度適切な値(longがあふれないけれど、計算中に超えない)にしないと変な値になってうまくいかなかった。