競技プログラミングって何？~青木先生~ | 東進ハイスクール武蔵小杉校大学受験の予備校・塾

ブログ

2023年 3月 16日　競技プログラミングって何？~青木先生~

1分でわかる今回のブログの内容

今回のブログでは最近私が力をいれている，競技プログラミングについて紹介します．また，競技プログラミングで必要なことや，なぜ私が競技プログラミングを始めたかについて説明しています．また，補遺では競技プログラミングを始めるときにどこから手を付ければいいか解説しています．

競技プログラミングとは?

ザックリ言えば，人間の力で解くことが大変な問題をコンピュータの力を使って制限時間内に解く，その速さと正確性を競うものです．実際の問題を見てみましょう．

AtCoder, Educational Dynamic Programming Contest (外部サイトへ遷移)

この問題はいわゆる，「ナップザック問題」と呼ばれるもので，少しでも情報系のことに興味がある人なら聞いたことがあると思います．簡単に言えば，

「遠足に持っていくお菓子には重さと予算があり，青木君は好きなお菓子の度合いが数字で分かっています．重さと予算，どちらもオーバーしないルールを守りながら，青木君が一番喜ぶお菓子の組み合わせを選んだ時，青木君はどのくらい喜びますか」

という問題です．勘の良い方はコンピュータならば全パターン試せば良いと思うかもしれませんが，そうは問屋が卸しません．この問題ではそれでは実行時間に間に合いません．今回は品物は

個程あるため全パターンは，常用対数を用いて考えると

通り程度あり，コンピュータは

秒間に

回程度しか計算できないことを考えると

年(

年)，全パターン調べるのにかかることが分かります．これでは到底間に合いませんね．このような問題をDynamic Programmingという考え方を用いれば

秒程度で解くことができます．これが競技プログラミングの魅力です．すなわち，私は，少し考え方を工夫すると高速に問題を解決することができることに惹かれました．具体的にはこのように考えます．

もう少し詳しく説明すると，

個目までの品物から選んだ時の価値の最大値は，

個目までの品物から選んだ時の重さ，価値がそれぞれ，

の状況で，

個目の品物(重さ

，価値

)を選んだ時(case 1)と，

個目までの品物から選んだ時の重さ，価値がそれぞれ

の状況で

個目の品物を選ばないとき(case 2)の大きいほうです．

なぜ競技プログラミングを高校生が始めるべきか

先ほど載せた図を見て，高校の漸化式のようだと思いませんか？高校で学んだことが役に立つではないですか！私が競技プログラミングに熱中している理由はこのように，高校の数学程度が分かっていれば，実際に役に役立つことができるではありませんか！高校の数学が何の役に立つかわからない高校生には，是非競技プログラミングを始めることをお勧めします．

それだけではありません．4月から高校2年生になる学年から共通テストに「情報I」が追加されます．実際にコーディングをしたことのあるなしで，大きく点数の差が生まれるのではないでしょうか？競技プログラミングはプログラミングを学校で勉強したが，特に何か作りたいものがあるわけではない人に，競技プログラミングは勝敗を競うので当面の目標を与えてくれます．AtCoderでは，プログラミングに全く触れたことのない人も競技プログラミングに参戦できるように十分な準備 (補遺2参照) がされています．受験勉強の傍らにでも，時間のある低学年のうちはプログラミングに触れてみてはいかがでしょうか．

補遺1

Pythonでの実装例を載せておきます．

こちらからも見られます(外部サイトへ遷移)

補遺2

もし，このブログを読んで競技プログラミングを始めたいと思ったが，プログラミングの経験がない場合は言語はC++をおすすめします．理由はほとんどの解説がC++で書かれていることと，初心者向けの教材がAtCoderのサイト上にある(AP4G(外部サイトへ遷移))ためです．一通りAP4Gを終えたら，AtCoder Beginners Selections(外部サイトへ遷移)の問題を解きながら，毎週土曜日もしくは日曜日にあるAtCoder Beginners Contestに参戦しましょう．順位表でharry_arbrebleuの名前を見たら「あ，こいつまたやってるな」と思ってください．

慶應義塾大学理工学部学門B (2023年度より物理情報工学科に進学) 青木陽

★明日の開館時間★

13:00~21:45

新年度招待講習2講座無料招待中！！！

申し込み締め切り期限迫る！あと4日