AtCoder Regular Contest 059 - プログラミング備忘録

AtCoder Beginner Contest 043 と同時開催。
k-ashiya-code.hateblo.jp

コンテストページ

arc059.contest.atcoder.jp

解法メモ

E問題

$\sum_{c_1+\cdots+c_N=C} \sum_{x_1=A_1}^{B_1} \sum_{x_2=A_2}^{B_2} \cdots \sum_{x_N=A_N}^{B_N} x_1^{c_1} x_2^{c_2} \cdots x_N^{c_N}$ を計算する。
まず、 $c_i$ が定数であると仮定すると、
$\sum_{x_1=A_1}^{B_1} \sum_{x_2=A_2}^{B_2} \cdots \sum_{x_N=A_N}^{B_N} x_1^{c_1} x_2^{c_2} \cdots x_N^{c_N} = (\sum_{x_1=A_1}^{B_1} x_1^{c_1})(\sum_{x_2=A_2}^{B_2} x_2^{c_2})\cdots(\sum_{x_N=A_N}^{B_N} x_N^{c_N})$
と分解できる。したがって、各 $i$ に対して $\sum_{x_i=A_i}^{B_i} x_i^{c_i}$ を $c_i = 0, 1, \cdots, 400$ について前計算しておく。
次に、動的計画法で、 $dp[i][j] = i$ 番目までの園児にキャンディーを $j$ 個配ったときの積の総和となるように式を立てて実行する。

F問題

小文字 a,b,c,... は0、1のいずれか、B はバックスペースを表すとする。キーボード入力が abcBdBef ならば、エディタに表示されている文字列は abef となるはずである。このとき、a,b,e,f が表す文字列の組み合わせは $2^4=16$ 通りであり、a,b,e,f としてどの組み合わせが与えられても、abcBdBef の形のキーボード入力は $2^2=4$ 通りあることがわかる。
N文字の入力でK文字の出力となるような入力の数を $f(N,K)$ と表すことにすると、 $f(0,0) = 1$ , $f(1,0) = 1$ , $f(1,1) = 2$ である。
次に、 $i \geq 2$ について、 $j=0$ のときは $f(i-1,0)$ と $f(i-1,1)$ の文字列の後ろにBを足せばよいから $f(i,0) = f(i-1,0) + f(i-1,1)$ 。
$1 \leq j \leq i-2$ のときは、 $f(i-1,j-1)$ の文字列の後ろにa（0か1）を、 $f(i-1,j+1)$ の文字列の後ろにBを足せばよいから $f(i,j) = 2f(i-1,j-1) + f(i-1,j+1)$ 。
$f(i,i-1)$ は $f(i-1,i-2)$ の文字列にaを足せばよいから $f(i,i-1) = 2f(i-1,i-2)$ 。 $f(i,i)$ は $f(i-1,i-1)$ の文字列にaを足せばよいから $f(i,i) = 2f(i-1,i-1)$ 。
以上のようにして $f(N,N)$ まで求めたあと、 $f(N,|s|)/2^{|s|}$ を出力する。

フェルマーの小定理

途中の過程で $10^9+7$ で割った余りを求めているから、単純に $2^{|s|}$ で割ることはできない。そこで、フェルマーの小定理を用いる。

$p$ を素数とする。 $a^{p-1}$ を $p$ で割った余りは1である。

証明はWikipediaに譲る。これを利用すると、 $2^{|s|}$ で割ることは $2^{10^9+7-1-|s|}$ をかけて $10^9+7$ で割った余りを求めることと同値。

二分累乗法

$10^9+7-1-|s|$ は確実に9桁以上の10進数になるから、ふつうに累乗していこうとするととても時間がかかる。そこで、二分累乗法というテクニックを使う。
まず、求めたい累乗を格納する変数 $p$ 、底を格納する変数 $b$ 、指数を格納する変数 $e$ を用意する。最初は $p=1$ 、 $b=2$ とする。
$e$ が奇数ならば、 $p$ に $b$ をかけ、 $e$ の偶奇によらず $e$ を2で割った商に書き換えて、 $b$ を2乗する。 $e$ が奇数ならば、 $p$ に $b$ をかけ、…ということを繰り返していけば、かなりの時間短縮になる*1。
プログラム上では2で割るとか偶奇の判断をするとかよりも、ビット演算で1の位のビットが立っていれば掛け算する、 $e$ を1つ右シフトする、という操作の方が早いのかもしれない。

キーワード

E問題

動的計画法

F問題

フェルマーの小定理、二分累乗法

*1:線形時間らしいけど本当にそうなのかがわからない。