AtCoder が提供しているABC（AtCoder Beginner Contest）275 のD問題をC++とPythonで解いてみました。ABC275は、2022年10月29日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Yet Another Recursive Function（Difficulty : 606）
問題はリンク先をご覧ください。
ABC275 D問題 Yet Another Recursive Function
メモ化再帰を使います。AtCoder Problems による Difficulty は、606 でした。ABC D問題としてはやや取り組みやすい問題です。ABC275 に限れば、C問題とD問題の Difficulty が逆転しています。
解答案
C++ プログラム例（ABC275D）
漸化式をそのまま実装する
まず、漸化式をそのまま実装してみます。入力 $N$ は、$0 \leqq N \leqq 10^{18}$ の範囲であるため、関連する変数は、unsigned long long int 型としました。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
ull f(ull n)
{
if (n == 0) {
return 1;
} else {
return f(n / 2) + f(n / 3);
}
}
int main()
{
ull n;
cin >> n;
cout << f(n) << endl;
return 0;
}入力例1から3に対して、すべて正解を出力しますが、提出すると TLE（Time Limit Exceeded）となります。実行時間が2秒を超える場合があるようです。
具体的に考えてみましょう。f(10) は、以下のように展開されます。
$$\begin{align*}
f(10) &= f(10/2) + f(10/3) \\
&= f(5) + f(3) \\
&= f(5/2) + f(5/3) + f(3/2) + f(3/3) \\
&= f(2) + f(1) + f(1) + f(1) \\
&= f(2/2) + f(2/3) + (f(1/2) + f(1/3)) \times 3 \\
&= f(1) + f(0) \times 7 \\
&= f(0) \times 9 \\
&= 9
\end{align*}$$
f の呼び出し回数が指数的に増えていくことが分かります。また、f は同じ引数で繰り返し呼び出されるていることも分かります。
メモ化再帰を使う
このような場合は、「メモ化再帰」を使います。呼び出した結果を覚えておいて、同じ引数で呼び出されたら、その結果を返すわけです。これにより、f の呼び出しを大きく減らすことができます。メモとして配列を使う場合がありますが、今回は引数の範囲が広いため、map を使います。C++ の map は、キーが存在しない場合、値 0 を返します。
以下は、メモ化再帰を使った C++ のプログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
map<ull, ull> m;
ull f(ull n)
{
if (n == 0) {
return 1;
}
if (m[n] == 0) {
m[n] = f(n / 2) + f(n / 3);
}
return m[n];
}
int main()
{
ull n;
cin >> n;
cout << f(n) << endl;
return 0;
}このプログラムは、無事にAC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC275D）
Python では、メモとして dict（辞書）を使います。Python 版は、おまじないが少ない分だけ、すっきりと見えます。
"""AtCoder Beginner Contest 275 D"""
m = {}
def f(n):
if n == 0:
return 1
if n not in m:
m[n] = f(n // 2) + f(n // 3)
return m[n]
print(f(int(input())))次に Python のデコレータを使ってみましょう。
デコレータとは、関数を引数にとり、なんらかの機能を追加した関数を返すモノです。次の例では、デコレータ functools.lru_cache は、f を引数に取り、その f に対して、メモ化再帰を追加した関数を返します。これを f に代入しているため、それ以降で、f を呼び出すと、メモ化再帰に対応した関数が呼び出します。
注）functools.cache は、自分のパソコン上では動作しました。ただし、AtCoder の評価では、RE（Runtime Error）が発生しました。
2022年11月9日追記
functools.cache は、Python バージョン 3.9 で追加されました。一方、AtCoder のバージョンは、3.8.2 でした（2022年11月9日時点）。このため、AtCoder 環境で functools.cache が動作しなかったようです。
"""AtCoder Beginner Contest 275 D"""
import functools
def f(n):
if n == 0:
return 1
return f(n // 2) + f(n // 3)
f = functools.lru_cache(f)
print(f(int(input())))デコレータは複雑な機能です。「Python デコレータ」などで検索して調べてみてください。
Python でデコレータを使う場合、”@” に続けてデコレータを指定して、その直後にデコレータを適用する関数定義を書く記法があります。以下は、この記法を使った Python プログラムです。すっきりと書けています。
"""AtCoder Beginner Contest 275 D"""
import functools
@functools.lru_cache
def f(n):
if n == 0:
return 1
return f(n // 2) + f(n // 3)
print(f(int(input())))すべて「AC」と判定されました。
最後に
この問題は、メモ化再帰を使う典型問題でした。Python 版の解答で初めてデコレータを使いました。Python は、関数をオブジェクトとして使えることが分かり勉強になりました。
ABC275 は、C問題とD問題の Difficulty が逆転していましたが、解きやすい回であったと感じました。
引き続き ABC の問題を紹介していきます。
