問題 atcoder.jp 解法 k=0における転倒数はBITで求められる。 $a_i$にkを足してmodNをとるという操作は、数列の先頭の要素が削除されて最後尾に追加されるという操作と等しい。 $a_i$ が削除されると転倒数が$a_i$減り（$a_i$を転倒数として数えられるのは、…

問題 https://atcoder.jp/contests/typical90/tasks/typical90_h 解法 DPで解く。基本的な考え方はナップサック 問題と同じで、dp[i][j]:=i番目まで見て、状態jとなる個数の数え上げとする。 文字列t="atcoder"とした時、遷移先は以下の２通り。 dp[i+1][j]+…

問題 atcoder.jp 解法 各桁をどの順番で足し合わせても答えは変わらない 桁を2つ選んで足し合わせたとき、繰り上がりが起きない場合は桁が一つ減り、起きる場合は桁はそのままで桁和が9減る。 桁上がりが起きる回数は(桁和-1)/9回 コード int main(){ int n;…