fastest codeを(一瞬だけ)取った話 - 競プロをはじめた家事手伝いロボットのブログ

忙しい人向けの内容

agc023.contest.atcoder.jp

非本質虚無定数倍高速化です
のしさんに抜かれました
以上です

問題概様&ネタバレ

agc023.contest.atcoder.jp

読みましょう
解けている人はこのへんを読まなくていいです

スコアが $K$ 以下のものが $f(K)$ 個あるとわかれば、答えは

${ \displaystyle (N-1)\times (N-1)! - \sum^{N-2}_{K=0}f(K) }$

であることがわかります。
スコアがちょうど $\displaystyle K$ であるものが $\displaystyle g(K)$ 個であるとしたら $\displaystyle f(K)=\sum^{K}_{i=0}g(i)$ なので、これと $\displaystyle f(N-1)=(N-1)!$ であることから上の式が正しいことが納得できると思います。

ここからは $f(K)$ を高速に求めるフェーズになります。

まず、スコアが $K$ 以下であるような順列はどのようなものでしょう?
この記事はネタバレ記事なので書いてしまうと、使わない機械 $N-K-1$ 個を決めてしまうことでえいとできます。
つまり、 $K$ 個の○と $N-K-1$ 個の×を機械に振り分けて、○のついた機械を先に、×のついた機械を後に起動させるような順列は、○のついた機械が全体を塗れるときかつそのときに限りスコアが $K$ 以下になります。(×がついた機械が稼働されることがないので)
○どうしが2つ以上離れているとき、○のついた機械だけでは全体を塗ることができません。また、最初と最後は○である必要があります。(最初に機械を全部1/2マス進めておくと私はイメージしやすかったんですけどどうですか)
これは必要十分なのでこれの場合の数を出せばよく、よく考えると"○"と"×○"を適当な数並べることを考えれば答えがでます。
さんすうをすることでこれは $\displaystyle \begin{pmatrix}K-1 \\ N-K-1\end{pmatrix}$ 通りあることがわかります。
これに○の機械の並べ方 $K!$ 通りと×の機械の並べ方 $(N-K-1)!$ 通りをかけることで $\displaystyle f(K)=\begin{pmatrix}K-1 \\ N-K-1\end{pmatrix}K!(N-K-1)!$ がでます。
ところで、場合の数のさんすうはバグらせやすいですが、今回できる見直し方法として $\displaystyle f(N-1)=(N-1)!$ を確かめるがあります。どうぞご活用ください。

高速化

まず、 $\displaystyle f(K)=\begin{pmatrix}K-1 \\ N-K-1\end{pmatrix}K!(N-K-1)!$ はもう少し楽になりそうな気がします。
第1項を計算すると $\displaystyle \begin{pmatrix}K-1 \\ N-K-1\end{pmatrix}=\frac{(K-1)!}{(2K-N)!(N-K-1)!}$ となって、いい感じに消えて $\displaystyle f(K)=\frac{K!(K-1)!}{(2K-N)!}$ になります。
$1!-N!$ とその逆元を何も考えずに実装するとfastestになりました。
とはいえ2位と3ms差(17msと20ms)、いつ抜かれてもおかしくなかったのでもっと早くしました。

constexpr

これまで手を出してこなかった†コンパイル時計算†に初めてまともに手を出しました。
今回の計算では、絶対に $1!-1000000!$ と $mod 10^{9}+7$ におけるその逆元しか出現しません。なので、それをコンパイル時計算で出します。
C++14以降のconstexprでは、構造体を作り、いいかんじの書き方でconstexprなコンストラクタを作るとconstexprなclassを作ることができます。
今回の実装では、1000000個の要素を持った配列を持ったクラスを二つ作って、一つ目には $i!$ を、二つ目には $i!^{-1}$ をもたせました。

もう少し早くしたかったのでもう少し式を睨むと、 $f(K)$ の式には $i!(i-1)!$ の形でしか分子には階乗が出てきません。
ここを前計算しておくとすこしだけ早くなって、5msまでCPU timeが落ち、私は安心して眠りにつきました。

その後

翌日自分の順位を確認しにAll Submissionをのぞいたら熨斗袋さんに抜かされていました。~~儚い天下でした...~~
差を見ると、
・long long intではなくてint_fast64_tを使っている
・一回だけ使う $(N-1)!\times(N-1)$ の前計算をしている
くらいしか見つけられなかったんですけど、のしさんの爆速なんですよね...なんででしょう

というわけで、みなさんもコンパイル時計算で虚無定数倍高速化をしてfastest codeをとりましょう！

以上です