CODE FESTIVAL 2016 qual C : E - 順列辞書 / Encyclopedia of Permutations

code-festival-2016-qualc.contest.atcoder.jp

予選落ちたのが大変悔しかったので、
ちょっと背伸びして普段じゃ絶対に解けないだろう、
最後の問題を解いてみた。

当初の方針

ちんぷんかんぷん

解法を見て

????

自分に理解できるように噛み砕いていく。

まずある順列 s_0, s_1, ..., s_{N−1} が与えられたときに
・・・結局ページ番号は次の式のように表せます。

\sum_{i=0}^{N-1} (s_0からs_{i-1}までに現れないs_i未満の数の個数) \cdot (N-1-i)!

紙に書いてみるとその通りで、
例えばs:=(3, 2, 4, 1)だと以下のようになる。

f:id:arukuka:20161026112251p:plain

1.p_i \neq ?
s_iによる方はO(1)で簡単に計算できるので

タンマ


\begin{eqnarray}
\sum_{s} s_i - \sum_{j=0}^{i-1} (s_j < s_i) &=& \left( \sum_{s} s_i \right) - \left( \sum_{s} \sum_{j=0}^{i-1} (s_j < s_i) \right) \\
&=& K! p_i -  \left( \sum_{s} \sum_{j=0}^{i-1} (s_j < s_i) \right)
\end{eqnarray}

こういうことか

1a) p_j \neq ?
sによらず一定な部分なので全てのjを見ることでO(N)で計算できます

これはp_j \neq ?についてまとめて考えている。結局、


\begin{eqnarray}
\sum_{s} \sum_{j=0}^{i-1} (s_j < s_i) &=& \sum_{s_j \in s, s_j \neq ?} \sum_{j=0}^{i-1} (s_j < s_i) + \sum_{s_j \in s, s_j = ?} \sum_{j=0}^{i-1} (s_j < s_i) \\
&=& K! \sum_{p-?} \sum_{j=0}^{i-1} (p_j < p_i) + \sum_{s_j \in s, s_j = ?} \sum_{j=0}^{i-1} (s_j < s_i)
\end{eqnarray}

こういうことになる。
(数式で誤解なく表現する術を知らないのでこのようになっていますが、
要するにp_j >= 0, 0 <= j < iについてp_j < p_iの個数をカウントして、
それにK!をかけるということです。s_jが固定されている部分なので、
単体のケースについて計算して、ありうる順列の個数であるK!をかけてあげればいいです)

1bは、一番最初に引用した部分を理解してた(たぶん)ので、
なるほど納得できる。
これが、p_j = ?の個数分だけあるので、
直前までのp_j = ?の個数をかけてあげる必要がある。

2,p_i = ?
こちらもs_iによる方はpに出てこない値たちの総和を考えるとO(1)で計算できる

紙に書いてみると、pに出てこない値たちの総和 \times (K-1)!になる。

2a) p_j \neq ?
1b)と同様に計算できます。

~~~~?????

と思ったけど、これは、

pに現れない数のうち、s_jより大きいものの個数\cdot (K-1)!となる。
これをj < i \bigwedge p_j \neq ?について全部足していく。

2bについては納得。
これも1bと同様に、p_j = ?の個数分だけこの通りが存在するので、
直前までのp_j = ? の個数をかけてあげる。

材料がそろったのでこれで実装する。
バグらせやすそうなので、まずは部分点解法を狙い、
そのあと高速化する。

提出 → WA & TLE

Submission #950033 - CODE FESTIVAL 2016 qual C | AtCoder

なんでじゃ~~~

デバッグしてみると、引き算のところでMODの計算がおかしくなっていることに気づいたので修正。
TLEはs_iより小さい数や大きい数の個数を求めるところで、TreeSetのheadSet, tailSetを使っていて
それがO(N)かかっているぽかった。

ArrayListとCollections.binarySearchに直したり、思いつかないところは
あらかじめ計算できそうなところを計算しといて、提出。

Submission #950053 - CODE FESTIVAL 2016 qual C | AtCoder

部分点ゲット。


あとは、よく考えたら時前に計算できるところを計算したり、
オーバーフローするところをひたすら探して修正したりした
(無限にWA & TLEしました)。

苦労の末、ようやくAC。

Submission #950111 - CODE FESTIVAL 2016 qual C | AtCoder

時間がぎりぎりなので、ぴろずさんのFastScannerを利用させていただきました。

qiita.com

補足:BITの使いどころ

1aのところの高速化は、BITを使うことになりますが、
慣れていなかったので手こずりました・・・。

pとして、(3, 1, 4, 2)が入力されたとします。

f:id:arukuka:20161026123231p:plain

このように、BITには、対象の座標に1を代入して更新作業をさせます。
すると、j < i で p_j < p_i な個数が分かります。
これをあらかじめ計算しておいて配列に入れて、後で利用するといいです
(他の方のソースコードを見ていたらs_iのiterate中に更新作業する方もいました)。

終わって

疲れた・・・。解説をなんとか読み切ることができたという感じだけど、
使う知識・論理的思考や実装量が多くて、さすが最後の問題だなあ、と思いました。

初めての挑戦ということでやってみたけど、
しばらくはワンランク下の問題をさくっと実装できるぐらいになっておかないと、
とてもじゃないけど実装しきれない。

考察できるかは・・・。慣れだといいんですけど。