AtCoder Beginner Contestの過去問から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
「競技プログラミング」を略して、「競プロ」などと呼ばれています。
#D - Yet Another Recursive Function
僕が作成、提出したコードは、以下のとおりです。
/* AtCoder Problems in C++ #D - Yet Another Recursive Function https://atcoder.jp/contests/abc275/tasks/abc275_d 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; map<ll,ll> m; ll F(ll n){ if(n==0){ return 1; }else if(m.count(n)>0){ return m.at(n); }else{ m.insert(make_pair(n,F(n/2)+F(n/3))); return m.at(n); } } int main(void){ ll n; cin>>n; cout<<F(n)<<endl; return 0; }
''' AtCoder Problems in Python #D - Yet Another Recursive Function https://atcoder.jp/contests/abc275/tasks/abc275_d 提出コードの解答例 https://neguse-atama.hatenablog.com ''' from functools import lru_cache @lru_cache def F(n): if(n==0): return 1 else: return F(n//2)+F(n//3) N=int(input()) print(F(N))
Pythonをあまり使わなかったのでわかりませんでしたが、C++と比べて関数がたくさんあるから、コードの実装がとても楽です。まさかメモ化再帰の関数まであるとは...。
AtCoder Beginner Contestは、オンラインジャッジによるプログラミングコンテストです。
日本語と英語に対応していて、週末ごとに実施されているみたいです。
https://practice.contest.atcoder.jp/tutorial
アカウントを登録すれば、誰でも参加できます。