perogram

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が偶数の場合

f:id:peroon:20190915152424p:plain

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

f:id:peroon:20190915153223p:plain

Nが奇数の場合

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

f:id:peroon:20190915153735p:plain

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

学び

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

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

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