第一回日本最強プログラマー学生選手権-予選- B - Kleene Inversion
学生対象だが10歳くらいオーバーしてるおっさんですまん。
初手の方針
今回はスムーズに方針立てられた、 以下2つの転倒数の和の合計を取る。
入力例3で説明する。
10 998244353 10 9 8 7 5 6 3 4 2 1
1個目のAの集合をA1={10 9 8 7 5 6 3 4 2 1}とすると、
1. A中に含まれる転倒数の合計 これは10->9 8 7 5 6 3 4 2 1, 9-> 8 7 5 6 3 4 2 1, 8-> 7 5 6 3 4 2 1...で合計は43
2. AkiとAkj,Akj+1...Akの転倒数の合計 は1個となりのA2={10 9 8 7 5 6 3 4 2 1}と比較して合計45
1.は集合がK個あれば
S1 = 43K
2.は初項43,公差43,項数K-1の等差数列の和と見なして
S2=k(k-1)/2
となりS=S1+S2が転倒数の合計となる。
Submission #9315505 - Japanese Student Championship 2019 Qualification
本日の気付き
方針を立てるのは比較的簡単だったのだがACを通すのはかなり苦労した。 というのもcppにおけるオーバーフローの挙動をよく理解していなかったからだ。 最終的な合計値を10^ 9+7で割れば良いと思っており(S1+S2)%10^ 9+7していたが、 注意しなければならないのはS1,S2それぞれもオーバーフローする可能性があるということだ。 加減乗についてはオーバーフローの可能性があるものについては%MODする、除については順番に気をつけるといったことが必要そうだ。
