D. Inversion Value of a Permutation
自力AC。
実験したら、たとえば、
1 2 3 4 5 6 7
を、
4 5 6 7 1 2 3
にすると、4*3の値が加算される、というように、配列を分割すると、その分割したときの値＋小さい配列の場合の値になることが分かった。
それを使ってDPしてどんな値を作れるかを列挙し、DPの復元を行って答えを出した。
解法が分かっても結構難しい気がする。
実験するとき、解かれている人数が多かったので、全部の値を列挙して埋め込めるのでは？ などと思っていたけど、そういうわけでもないしねぇ……。
0 件のコメント:
コメントを投稿