問題 解法 1,..,N の順列を p1,..,pN として, 最大化したい関数は |A_p1 - A_p2| + .. + |A_pN-1 - A_pN| になる. 目的関数の絶対値を外したい気持ちになるので,そのためには数列の順序付けが必要になる. それを念頭に起きつつ最適解の必要条件を列挙してみ…

問題 解法 解説にある通り,上書きしていくような問題では操作列を逆に見ていって,そのマスで一番最初の操作で色が確定すると考えるのが良くて,そうするとそのマスに関してそれ以降の色の変化を考えなくて良くなる. さて,逆順に見ていったときの最初(つまり元…