ABC437 A,B:はい C:各iについて-Wiか+Piを選ぶとみなす。それらの総和が0以上になればよい。まず全部-Wiを選んでおく。-Wiから+Piに変えると総和は+(Wi+Pi)されるので、Wi+Piの大きい順に変えていく。 D:各iについてBj<Aiとなるようなjの個数,Bjの総和が求まれば、Ai-Bj>0であるものについての寄与が計
1
0
5
Replies
算できる。逆の方も同様。 E:数列が等しくなる頂点をまとめて引数に渡すようにして適当に再帰。 F:|x1-x2|+|y1-y2|=max(x1-x2,-x1+x2)+max(y1-y2,-y1+y2)=max((x1+y1)-(x2+y2),(x1-y1)-(x2-y2),(-x1+y1)-(-x2+y2),(-x1-y1)-(-x2-y2))だから、xi+yi,xi-yi,-xi+yi,-xi-yiの区間maxが分かればよい
1
0
1
G:各頂点R,G,Bで操作する回数が固定。各辺両端の色が一致しないようにマッチングさせることになり、工夫するとマッチングは最大流で求まる。マッチングが求まったら、各頂点に注目してどの順番で辺が処理されるかを見てトポソ。
0
0
1
No dev team? No problem. Caffeine turns your ideas into launch-ready apps — just by chatting. Start for free →
195
568
3K