C - Align

Quiz

https://atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_c

Submission

https://atcoder.jp/contests/tenka1-2018-beginner/submissions/7508948

ジグザグに配置

• editorialに書いてあるとおり、1, 3, 5と置くより1, 5, 3と置いたほうがよく、ジグザグ（上がる下がるを繰り返す）に置くことになる

Nが偶数の場合

• 上記画像の場合、上のラインは足される側、下のラインは引かれる側
• 端点のみ係数が1
• 係数が2のものから数字を割り当てていく
• A = [1, 2, 3, 4, 5, 6]なら、上ラインの係数2の部分に一番大きい値（5, 6）、下ラインの係数2の部分に一番小さい値（1, 2）を置けばよい
• Nが偶数の場合は、係数の対称性より、N型のみ考えればよく、「Nの上下反転型」は考えなくてよい

Nが奇数の場合

• M型とW型がある
• M型の場合
  • 引かれる数の方が多い（A=[1,2,3,4,5]なら1,2,3を引かれる数に割り当てる
  • 端点2つも引かれる数から割り当てる

• W型の場合
  • M型と同様に求める
• M, W型それぞれから値を求め、そのmaxが答え

学び

• ジグザグになる
• 絶対値を外すと係数が出てくる
• 係数を見ながら割り当てる

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?