「IJPCで出題しうる問題タイプを網羅しよう」と考えながらこのようなセットを作りました。そのため、面白い反面、一般的なPracticeよりも難しい問題になってしまったと思います。
とはいえ、さすがにPracticeですから、以下では満点解法のみ解説します。
"IJPC"のうち、書き換えによって得る文字をあらかじめ定めて考えると、書き換える文字の組み合わせは"I.PC"や".JPC"や"..P."など16通り。それぞれについて、それがSの部分文字列かどうかを調べる。
DPを用いてもよい。
taroとjiroの両方で素数列挙をしておく。
taroは以下の数字をビット列にエンコードして送る。
- Nが合成数なら、0
- Nが小さい方からx番目の素数なら、x
f(N,C)を、高々N回の失敗かつ高々C回の試行で判別できる範囲の大きさとする。すると、以下の漸化式が得られる。
- f(0,C) = 1
- f(N,0) = 1
- f(N,C) = f(N-1,C-1) + f(N,C-1)
この規則に従ってcompare(X)に使用するXを定めると、最も効率良く判別することができる。
なお、N=0,1,2,3,4で漸化式を解くと、以下のようになる。
- f(0,C) = 1
- f(1,C) = C + 1
- f(2,C) = (C^2 + C)/2 + 1
- f(3,C) = (C^3 + 5C)/6 + 1
- f(4,C) = (C^4 - 2C^3 + 11C^2 + 14C)/24 + 1
このとき、f(3,C) = 10^12 となるような C は18171.2だから、最初の状態で 3 <= N かつ M <= 10^12 であるため、常に C <= 18171 としてよい。
分散の定義式は、「二乗の平均 - 平均の二乗」 つまり (a1^2 + a2^2 + ... + an^2)/n - ((a1 + a2 + ... + an)/n)^2 と変形できる。
そこで、この式に登場する総和計算を、Fenwick Tree (Binary Indexed Tree) などを使って高速化する。
なお、long long を使って計算したほうが安全だと思われるが、今回はdoubleを使用しても全く問題ない。