今日解いた競プロの問題。

いろはちゃんコンテストDay1-J: 超がんばって力業で解いた。

Nが偶数の時: $n=N/2$、$S=A_1+…+A_n$と置いて超がんばって計算すると、転倒数は$2S(n-S)$という数式で表されることが分かる。$2S(n-S)=k$とおくと、これは二次方程式なので、$n,k$が定まればSは1通りまたは2通りに定まる。これを頑張って解き、$_nC_S$を計算すれば答えが求まる。

Nが奇数の時: $n=(N-1)/2$、$S=A_1+…+A_n$と置いて超がんばって計算すると、転倒数は$(n-S)(2S+A_{n+1})+(1-A_{n+1})S$という数式で表されることが分かる。$A_{n+1}$が0の場合と1の場合で場合分けし、それぞれの場合について二次方程式を解いて$_nC_S$を計算して合算すれば答えが求まる。

二次方程式を解くところだが、Sは[0,n]の整数でなければならないことから、判別式が平方数かどうかを判定しなければならない。どうするか悩んだが、1～2Nくらいまでの数の二乗を全て計算して平方数テーブルを作ることでなんとかした。

とにかく解けたは解けたが、いろいろな数値を入れてみた感じ、かなり多くの場合で答えが0になる。実はもっと美しい解法があるのではないかという気がするが分からない。

---

やっと煮詰まっていたレポートを倒したので多少精神が回復した。

火曜なので胎界主読むか～と思ったら休載だった。つらい。毎週コンスタントに描き続けていることの方がやばいのだが。