AtCoder

ABC275 D問題(Yet Another Recursive Function)を解く

AtCoder_ABC275_D

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 を解いていきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA