tooh’s diary

半角全角、常体敬体が入り乱れるカオス

2/26 AtCoder(絶対値を外す際の全探索)

こんにちは。競プロ合宿1日目のとーです。

 

AtCoder

解くに至った問題(3問)

ARC:081D/100D

Tenka 1 Programmer Beginner Contest:C

 

ARC100D

x_i,y_i,z_iがN個の要素として与えられて、(x_iの絶対値のM個の合計)+(y_iの絶対値のM個の合計)+(z_iの絶対値のM個の合計)を最大化する問題

 

要素がプラス、マイナスどちらの形式でも与えられているのが厄介

 

純化して考えると、例えばx_i+y_i+z_iのM個の合計を最大化したいのであれば、これは簡単でx_i+y_i+z_iの合計をソートしてM個上から採用すればよい

 

これを応用して、結局絶対値を外す作業はプラスマイナスを逆にする作業なので、絶対値の合計として求めるならば、opt = ['+','-']として、例えば+x_i+y_i-z_iを値の大きい順にソートし、上からM個の合計をとれば、z_iが負の値ならばそれを正の形に変換したことになる(もちろんz_iが負になるとは限らないので、これが正だったら答えから外れる(マイナスすれば和が小さくなるので))。これを、optについて全探索(8通り)して、最も大きいものが答えとなる

 

解けなかった問題

ABC:087D/092C/097D