Instantly share code, notes, and snippets.

Embed
What would you like to do?
IJPC 2012 Practice 解説

IJPC2012 Practice

講評

「IJPCで出題しうる問題タイプを網羅しよう」と考えながらこのようなセットを作りました。そのため、面白い反面、一般的なPracticeよりも難しい問題になってしまったと思います。

とはいえ、さすがにPracticeですから、以下では満点解法のみ解説します。

A. Welcome to IJPC

"IJPC"のうち、書き換えによって得る文字をあらかじめ定めて考えると、書き換える文字の組み合わせは"I.PC"や".JPC"や"..P."など16通り。それぞれについて、それがSの部分文字列かどうかを調べる。

DPを用いてもよい。

B. Prime Hazard

taroとjiroの両方で素数列挙をしておく。

taroは以下の数字をビット列にエンコードして送る。

  • Nが合成数なら、0
  • Nが小さい方からx番目の素数なら、x

C. Submission

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 としてよい。

D. Variance

分散の定義式は、「二乗の平均 - 平均の二乗」 つまり (a1^2 + a2^2 + ... + an^2)/n - ((a1 + a2 + ... + an)/n)^2 と変形できる。

そこで、この式に登場する総和計算を、Fenwick Tree (Binary Indexed Tree) などを使って高速化する。

なお、long long を使って計算したほうが安全だと思われるが、今回はdoubleを使用しても全く問題ない。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment