G1 - Genuine Multiple Dependencies [Easy]

2 secs 1024 MB
uni_kakurenbo's icon uni_kakurenbo
Tweet
問題
提出
テストケース
解説

概要

考察重視の問題です．

問題原案：@uni_kakurenbo

解説

Ⅰ.Ⅰ. 愚直な実装

問題文の定義通りに関数 fn(x)f_n(x) を実装するところから始めてみましょう．

たとえば Python では次のようなコードで表現できます．
実装例_1

さらに，この式には足し算のみが登場しますので，あまりを取るという操作を計算の途中に行うことができます．(証明などは他サイト等へ委ねます．)
これを考慮すると以下のように書き換えることができます． 実装例_2

Ⅱ.Ⅱ. 再帰のメモ化と動的計画法

先述した愚直な実装における時間計算量を見積もってみましょう．

先の実装では，どんな入力に対しても最終的に 11 の足し算のみに分解されます．
つまり fN(X)f_N(X) を求めるために (fN(X)−1)(f_N(X) - 1) 回 11 が足されることになるのです．
したがって，テストケースあたりの時間計算量は O(fN(X))O(f_N(X)) になります．

試しに，サンプル項のビジュアライザを用いて fn(x)f_n(x) の値を計算してみると，いとも簡単に 10810^8 付近を突破してしまうことがわかるでしょう．
これでは N,X≤300N, X \leq 300 の入力に対して到底時間内に答えを出すことはできません．

1)1) メモ化

解決策の一つとして「メモ化」があります．

答えの求め方をよく考えてみると，何度も同じ引数で関数 fn(x)f_n(x) の値を計算していることがわかります．
たとえば

fN(X)=fN−1(1)+fN−1(2)+…+fN−1(X)=[fN−2(1)]+[fN−2(1)+fN−2(2)]+…+[fN−2(1)+…+fN−2(X)]=…⋮\begin{darray}{ll} f_N(X) &= f_{N-1}(1) + f_{N-1}(2) + \ldots + f_{N-1}(X) \\ &= [f_{N-2}(1)] + [f_{N-2}(1) + f_{N-2}(2)] + \ldots + [f_{N-2}(1) + \ldots + f_{N-2}(X)] \\ &= \ldots \\ &\vdots \end{darray}

のようになります．

よって，一度値を求めた組 (N,X)(N, X) についてはその答えを「メモ」しておくことで，大幅に計算量を削減することができます．
これを「メモ化」と呼び，メモ化がされた再帰を「メモ化再帰」と呼んだりもします．

また，複数のテストケースについての答えを求めるため，やはりメモ化によって計算量の大幅な削減が期待できます．

2)2) 動的計画法

実は，Python などの動作が比較的遅い一部の言語では，先述したメモ化再帰を用いて解くことができません．

代わりに動的計画法を用いて実装してみましょう．
「動的計画法」と聞くと難しい印象を受ける方もいらっしゃるかもしれませんが，本質は「より小さい問題の答えを用いて，大きな問題の答えを求める」ことです．

今回は，より小さい問題 (fn−1(x))(f_{n-1}(x)) の答えを用いて，大きな問題 (fn(x))(f_n(x)) の答えを求める方法を考えてみましょう．

実は，こちらも問題文に与えられている式を"そのまま"利用することができます．
Python での実装例を次に示します．
実装例_3

これをあらかじめ求めておけば，各テストケースについて O(1)O(1) で答えることができます．

これで [Easy] が解けました．

Ⅲ.Ⅲ. 漸化式の効率化

N,XN, X の最大値をそれぞれ LN,LXL_N, L_X とすると， 先述の解法では，問題全体を通して少なくとも O(LN×LX2)O(L_N \times L_X^2) 回は計算を行わなくてはなりません．
[Easy] では LN,LX≤300L_N, L_X \leq 300 が保証されているため十分に間に合いますが，[Hard] の制約下では TLE となってしまうでしょう．

そこで，もっと効率的に fn(x)f_n(x) の値を求めることはできないか考えてみましょう．

fn(x)f_n(x) の定義となっている漸化式を変形していきます．

fn(x)=∑k=1xfn−1(k)=fn−1(1)+fn−1(2)+…+fn−1(x−1)‾+fn−1(x)=∑k=1x−1fn−1(k)‾+fn−1(x)=fn(x−1)‾+fn−1(x)\begin{darray}{ll} f_n(x) &= \sum^{x}_{k=1} f_{n-1}(k) \\ &= \underline{f_{n-1}(1) + f_{n-1}(2) + \ldots + f_{n-1}(x-1)} + f_{n-1}(x) \\ &= \underline{\sum^{x-1}_{k=1} f_{n-1}(k)} + f_{n-1}(x) \\ &= \underline{f_n(x-1)} + f_{n-1}(x) \end{darray}

結果的に，fn(x)f_n(x) を fn(x−1),fn−1(x)f_{n}(x-1), f_{n-1}(x) の二つを用いて表すことができました．

これを先述したメモ化再帰や動的計画法で実装すればよいです．(Python の場合は依然として前者では間に合いません．)

これで [Hard] が解けました．

Ⅳ.Ⅳ. 発展

1)1) 類題

(難易度順)

実装例

C++
C++
Python