競プロの魅力について2

駄文日記1/17
駄文日記3回目です
駄文日記とは文章を書いてこなかった私Haruが一念発起し，一日一つ簡単な文章を書こうという企画ですルールとして一つ目標を決めその目標が達成できるように書きます

今日は競技プログラミングの魅力について
目標は「競技プログラミングは面白いと思わせる文章」です

前回、プログラミングの魅力について語りました
＜前回のリンク＞
今回はその続きで競技プログラミングの魅力について語ります
プログラミングはコーディング（プログラムを作ること）で求めたい数値を一瞬で求められるという面白さを説明しました
ではこれを競技プログラミングに拡張して話していきます

競技プログラミングは前回「数行から100行程度のコード（実は難易度が上がるともっと増える場合がある）を、アルゴリズムを使って書き競うプログラミングスポーツ」のことと説明しました
前回は説明しませんでしたがこれには条件があり、コードの長さと計算時間があらかじめ定められています
これが魅力に繋がります

＊ここから数学要素が出てくるので難しくなります
前回の問題は「偶数の時にyesと表示する」というものでした
これは余りを求めるだけなので計算が一回で済みます
しかし、問題によっては計算の回数が大きくなることがあります

例えば、「N枚のカードがありそのカードにそれぞれ番号が書かれているとき，合計がMという数字になる組み合わせが存在するときはyesと表示する」という問題があったとします

もしこの問題をそのまま解こうとするとN枚のカードの組み合わせを全て考えることになります
つまりそれぞれのカードにおいて、各々のカードを含む、含まないかを計算する必要が出てきます
すると組み合わせ（計算量）は2^Nという指数関数の式となります
（指数関数は同じ数を掛け合わせるという数学用語
2^3=2×2×2 を意味する）
するとN＝29の時、2^29=536,870,912 回
もの計算量となります

PCはおよそ10^9の計算量となっていますからN=29までしか1秒で計算できないことになります
指数関数の恐ろしいのは2倍4倍と増えていくのでN=60もすれば36年以上かかります

これを早くする方法はアルゴリズムと呼ばれています
いろいろ知られていてこの場合は動的計画法というものを使うと高速にできます
＊動的計画法は難しくなるので省略します

これを早く考えコードに書き込むのが競技プログラミングです
これはかなり奥が深いです
競技プログラミングに使われるのは簡単なものが多いですが、難しいものは現在研究が進み、今話題のAI（深層学習）にも使われることがあります
自分は競技プログラミングにはアルゴリズムの使い方に面白さが詰まっていると感じます

面白さは伝わりづらかったと思いますが興味が持てた方はAtcoder始め方で調べて一緒にやりましょう！
コードの書きかたはatcoderをやりながら勉強することができます（大変ですが）

今回は以上になります
興味を持たせるために具体例を説明しながら書くのは難しいですね
専門用語を知らない人には難しい文章になってしまいました
ここまで汚い文を読んでくれた方はありがとうございました

＜参考＞
数学とアルゴリズム　米田優峻著　2021　技術評論社
始めるには最適な書籍で、中級者にもおすすめです（愛読しています）

所要時間70分（明日は休みます）