A - A Recursive Function Editorial by physics0523
競プロの問題文、言葉遣いについて解説の機能が高機能になり、 Writer や Tester がユーザー解説を執筆した際に「公式解説」となってしまう問題が解消されるなどのアップデートが行われました。
今回はそれを記念して、競プロの問題文の取り扱い方を初級者向けに説明してみたいと思います。
今回の A 問題の問題文を振り返ってみましょう。
非負整数 \(x\) に対し定義される関数 \(f(x)\) は以下の条件を満たします。
- \(f(0)=1\)
- 任意の正整数 \(k\) に対し \(f(k)=k \times f(k−1)\)
このとき、 \(f(N)\) を求めてください。
数学に詳しくない方にとっては、かなり分かりにくく感じたかもしれません。それもそのはずで、競技プログラミングの問題文は「(数学的に)厳密であること」を重視するケースも多いです。
今回の問題文を順を追って読んでいくことで、練習してみましょう。
1文目
- 整数 … \(-3,0,123\) のように、「小数点以下がない」数です。厳密には、 \(0\) から \(1\) を足すか \(1\) を引くかを何度か繰り返して到達できる数全体のことを指します。
- 非負整数 … \(0\) 以上の整数のことです。
- 関数 … \(x\) の値を決めるとそれに対応して \(f(x)\) の値が決まる時、 \(f(x)\) を \(x\) の関数であると言います。 (参考: 中学数学)
- 今回の問題の場合は、例えば \(x=3\) と決めると \(f(3)=6\) と決まります。
「非負整数 \(x\) に対し定義される関数 \(f(x)\) 」を解釈していきます。
関数 \(f(x)\) が「非負整数 \(x\) に対し定義される」とは、 \(x\) を決めて \(f(x)\) が決まるという流れのうち、 \(x\) を決める時に \(x\) が非負整数である場合しか考えないということです。
今回の問題では、 \(x=3\) と決めて \(f(3)=6\) と決まることや \(x=0\) と決めて \(f(0)=1\) と決まることは許されていますが、 \(x=-1\) と決めて \(f(-1)\) を考えることは許されていません。
このように、ある関数が定義される範囲を 定義域 と呼びます。
逆に、関数 \(f(x)\) の値として決まりうる値の範囲のことを 値域 と呼びます。
例えば、非負整数 \(x\) に対し \(f(x)=\) ( \(x\) を \(3\) で割った余り) とすると、 \(f(x)\) の値域は \(0 \le f(x) \le 2\) です (「 \(0,1,2\) のいずれか」と表現してもよいです。)
条件 2 つ目
- 正整数 … \(1\) 以上の整数のことです。
- 任意の正整数 \(k\) に対し~
任意の ○○ という言い回しは、 ○○ であるもの全てを考えることを言います。
例えば、「任意の正の \(5\) の倍数」と言えば \(5,10,15,\dots\) と、正の \(5\) の倍数全てを考えることになります。
今回の場合は、任意の正整数 \(k\) と言っているので、正整数 \(k\) 全てを考えます。つまり、全ての正整数 \(k\) について \(f(k)=k \times f(k−1)\) が成り立つということを言っています。
制約欄
制約とは、コンテストの参加者がその問題を解くべき範囲のことを指します。
プログラムに与えられる入力は制約欄にある条件を全て満たします。逆に、この 制約を満たすような入力はどんなものでも与えられる可能性があります。 (逆に、万一入力が制約を満たしていなかった場合は問題の不備です。)
例えば制約に \(N \le 10\) とあれば、 \(N\) が \(10\) 以下であるどんな入力についても正解するコードを書かなければなりません。
入力欄
「標準入力」が指すものはプログラミング言語によって違いますが、 この問題 で取り扱い方を把握することができるでしょう。
他に、今回のコンテストでも使われている「競プロによく出る言い回し」を調べてみましょう。といっても、基本的には数学上での定義と同じです。
列 … モノを並べたものです。
数列 … 数を並べた列です。「○○からなる数列」と言えば、その列には ○○ を満たす数しか含まれません。例えば数列 \((10,15,20)\) は 「正整数からなる数列」、「 \(5\) の倍数からなる数列」ではありますが、「 \(2\) の倍数からなる数列」ではありません。
集合 … モノの集まりです。列とは違って順序の違いを考慮しません。
\(\Rightarrow\) (D問題) … この矢印は「ならば」を意味します。「文章A」 \(\Rightarrow\) 「文章B」 のような形で用いられ、 文章A が成立する時に必ず 文書B が成立する( すなわち、「 文章A ならば 文章B 」) ことを指します。 (例: 「 \(n\) が \(6\) の倍数」\(\Rightarrow\) 「 \(n\) が \(2\) の倍数」、「 \(i\) が偶数」 \(\Rightarrow\) 「入力 \(A_i\) が偶数」)
- この矢印は \(\Leftarrow\) の向きで使うことも許されます。
\(\Leftrightarrow\) … 「文章A」 \(\Rightarrow\) 「文章B」 と「文章A」\(\Leftarrow\) 「文章B」が同時に成立することを指します。このことを 文章A と 文章B が 同値である と言います。 (例: 「\(n\) が \(2\) の倍数」 \(\Leftrightarrow\) 「\(n\) の末尾が偶数」)
要素(E問題) … 列や集合を構成するそれぞれのモノのことを指します。
○○は相異なる (F問題) … ○○ が全て異なる(distinct) 、重複がないことを指します。「数列 \(A\) の要素は相異なる」のように用いられます。
\(\sum\) (Ex問題) … 「総和記号」です。記号の右に書かれたものを全て足したものを表します。
\(\prod\) … 「総乗記号」です。記号の右に書かれたものを全て掛けたものを表します。
他にもいろいろな言い回しが出てきますが、基本的には中学数学や高校数学の範囲です。競技プログラミングをやり込むのにあたって、中学数学や高校数学を復習すると役に立つでしょう。
posted:
last update: